탐색
-
[이진 탐색] 개념정리Algorithm/개념정리 2021. 11. 18. 10:25
순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 '보통 정렬되지 않은 리스트'에서 데이터를 찾아야 할 때 사용함 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 시간 복잡도: O(N) → 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요함 이진 탐색 : 반으로 쪼개면서 탐색하기 조건: 배열 내부의 데이터가 정렬되어 있어야 함 → 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음 특징: 탐색 범위를 좁혀가며 데이터 탐색 가능함 이진 탐색은 위치를 나타내는 변수 3개를 사용함(탐색하고자 하는 범위의 시작점, 끝점, 중간점) 찾으려는 데이터와..
-
[DFS/BFS] 개념정리3 - DFS과 BFSAlgorithm/개념정리 2021. 7. 17. 14:29
그래프 탐색이란? → 하나의 정점을 시작으로 다수의 정점을 방문하는 것 DFS(Depth First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘임 사용 자료구조 : 스택 동작 과정 : 탐색 시작 노드를 스택에 삽입하고 방문 처리함 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리 함 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함 —> 방문 처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않..
-
[DFS/BFS] 문제 이름 : 미로 탈출Algorithm/유형별 문제 풀기 2021. 7. 8. 11:34
문제 설명 N x M 크기의 직사각형의 미로가 주어질 때, 주인공의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸식 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시되는데, 이때 주인공이 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 1. 사용 알고리즘 그래프 탐색 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 2. 문제 해결 아이디어 주어진 문제는 미로를 탈출하기 위한 최소 칸의 개수를 구하는 것이므로, 탐색 시 더 이상 길이 없다면 다시 되돌아오게 되고 그러면 이때까지 잘못된 길로 갔을 때의 이동횟수..
-
[DFS/BFS] 문제이름 : 음료수 얼려 먹기Algorithm/유형별 문제 풀기 2021. 7. 5. 11:59
문제 설명 N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상 하 좌 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 1. 사용 알고리즘 그래프 탐색 - BFS & DFS 2. 문제 해결 아이디어 주어진 좌표의 위치와 해당 위치의 상하좌우에 대해 구멍이 뚫려서 연결되어 있는지 탐색하면 된다. 이때 주어진 2차원 배열을 그래프 형태로 생각하면, DFS와 BFS 알고리즘을 적용해 해결할 수 있다. 3. 코드 구현방식1) BFS(너비 우선 탐색)를 사용해 가까운 좌표부터 확인하기 각 좌표가 상하좌우에 대해 움직일 수 있는 ..