백준 알고리즘 문제6 [알고리즘 이론] 10. 투포인터 투포인터 선형 시간으로 알고리즘을 풀 수 있게 만들어주는 알고리즘이다. 연속적인 값들을 이용해 푸는 문제에 적합하다. 원리 배열의 하나의 인덱스를 가리키는 start 점과 end 점 두 개를 만든다. 처음 start 와 end 는 0으로 초기화. start 부터 end까지 합을 구해서 sum에 저장한다. -> 처음엔 0이 저장 배열을 도는데 세 가지 조건으로 돈다 sum == 찾고자 하는 값 -> 찾고자 하는 값이 나왔으니 count를 1 늘려주고, sum 값에서 start 인덱스 값을 빼주고 1을 늘려준다. 그리고 end 값을 1 더한 후 그 인덱스의 값을 sum에 더해준다. -> 문제를 풀어보면 이해할 수 있다. sum sum이 더 작으니까 start값은 그대로 두고, end.. 2023. 5. 9. [알고리즘 이론] 4. DFS, BFS DFS (Depth-First Search) 루트 노드(다른 임의의 노드도 가능)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색한다. 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. -> 재귀 or 스택 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부르 반드시 검사해야 한다. 이를 검사하지 않으면 무한루프에 빠질 수 있다. EX) visit[node] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더이상 갈 수 업게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하.. 2023. 5. 5. 이전 1 2 다음
