컴퓨터/알고리즘 (7) 썸네일형 리스트형 [코딩테스트][알고리즘] 7. 투 포인터(Two Pointers) 이 알고리즘은 소프트웨어 마에스트로 11기 온라인 코딩 테스트에서 출제되었다. 투 포인터는 1차원배열에서 서로 원소를 가르키는 2개의 포인터를 이용하는 알고리즘이다. 아래 문제는 투포인터의 대표적인 유형이다. https://www.acmicpc.net/problem/2003 1차원 배열의 구간합(M)을 구하는 문제인데 푸는 방식은 이러하다. 1차원 배열 arr과 구간합의 시작과 끝을 가르키는 포인터 (s,e)를 준비한다. arr = { 1 , 3 , 5 , 2 , 1 , 2 , 3 , 4 } 1. 초기값은 s=e=0 이다. 2. 항상 s i; ++i) { arr[i] = Integer.parseInt(st.nextToken()); } int s = 0; int e = 0; int temp = 0; whi.. [코딩테스트][알고리즘] 6. BFS (Breadth First Search) 너비 우선 탐색 BFS 역시 DFS와 마찬가지로 코딩 테스트에 자주 나오는 유형이다. BFS는 아래 그림과 같이 진행되는 탐색 알고리즘이다. 시작점으로부터 같은 이동거리에 있는 점들 순차적으로 탐색하는 방법이고, 동심원을 그리며 탐색을 하는 것으로 생각할 수도 있다. 시작점으로부터 이동거리 순으로 탐색을 하기 때문에 최단경로를 구하는데 유용하게 사용된다. BFS는 자료구조 Queue를 사용해서 구현할 수 있다. 코딩 테스트를 위한 BFS는 미로와 같이 x, y 좌표를 이용하는 문제에 자주 사용되는 것 같다고 생각되어 미로 문제를 통해 BFS를 어떻게 코드로 표현하는지 알아보려고 한다. bfs의 구현을 말로 설명하자면 다음과 같이 진행된다. 1. 탐색할 위치의 좌표를 queue에 넣고 방문처리 한다. 2. queue에서 .. [코딩테스트][알고리즘] 5. DFS (Depth First Search) 깊이 우선 탐색 DFS는 코딩테스트에서 자주 출제되는 유형이라고 하니 잘 익혀두는 것이 좋을 것 같다. DFS는 그림과 같이 탐색을 진행하는 알고리즘이다. 갈때까지 가다가 더 이상 진행 할 곳이 없으면 돌아가서 다음 방법을 찾는 것이다. 미로를 탐색한다고 생각할때 오른벽에서 손을 떼지 않고 계속 전진하면 출구를 찾을수 있다는 아이디어가 바로 DFS 탐색법이라고 말 할 수 있다. 다시 말해 가장 깊은 곳까지 가는 것을 우선시 하며 탐색하는 것이다. dfs는 stack 혹은 재귀함수로 구현 할 수 있다. 재귀함수로 구현하는게 매우 간단하기 때문에 재귀함수로 구현하는 것을 추천한다. dfs는 다음과 같이 구현 할 수 있다. public static void dfs( int here ) { System.out.print(her.. [코딩테스트][알고리즘] 4. DP( Dynamic Programming) 다이나믹 프로그래밍 다이나믹프로그래밍의 기본적인 아이디어는 한 번 풀었던 문제를 다시 풀지 말자! 라는 것이다. 풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 된다. 이러한 과정을 메모이제이션(Memoization) 이라고한다. 이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해진다. DP는 분할정복기법( 해결했던 문제도 다시 계산 )을 개선 한 것 인데, 대표적인 예가 피보나치수열을 구하는 것이다. 피보나치 수열은 1 1 2 3 5 8 13 21 34 - - - 와 같이 D[i] = D[i-1] + D[i-2] 의 공식에 의해 진행되는 수들의 나열이다. 분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같다.. [코딩테스트][알고리즘] 3. Greedy(그리디) Greedy 알고리즘은 현시점의 최적해를 찾는 것을 통해 문제의 최적해를 구하는 것이다. 문제 P 를 여러 단계로 나누어서 해결해보자. 각 단계는 P1 , P2 , P3 .... P이라고 한다면 그리디 알고리즘으로 문제를 풀기 위해서는 P1, P2, P3 에 적용한 조건들이 모든 P에 대해서 똑같이 적용되어야 한다. 문제를 보고 가장 먼저 떠오르는 방법(가장 쉽게 떠올릴수 있는 방법)이 그리디알고리즘 일 확률이 높다. 추천문제 : 1. https://www.acmicpc.net/problem/15655 2. https://www.acmicpc.net/problem/1080 3. https://www.acmicpc.net/problem/1969 4. https://www.acmicpc.net/problem.. [코딩테스트][알고리즘] 2. Backtracking(빽트레킹) Backtracking 이란 알고리즘은 거창하게 보이지만 사실 별거 없다. 하지만 backtracking 알고리즘이 사용되는 문제는 몇 문제를 제외하고는 난이도가 엄청 높다고 한다. Backtracking은 완전탐색을 진행하다가 조건에 맞지 않는 경우 탐색을 중단하고 이전 단계로 돌아가는 방법이다. 빽트레킹의 경우에 시간복잡도를 계산하기는 힘든 경우가 많다. 얼마나 많은 조건을 추가하느냐에 따라서 실행속도가 달라진다. 추천문제 : 1. https://www.acmicpc.net/problem/15655 2. https://www.acmicpc.net/problem/9663 3. https://www.acmicpc.net/problem/2580 4. https://www.acmicpc.net/problem.. [코딩테스트][알고리즘] 1. Brute Force(브루트포스 , 완전탐색) brute force는 완전 탐색이라고도 불리며, 모든 경우의 수를 직접 대입해보는 방법으로 가장 간단하게 문제를 풀 수 있는 방법이다. 풀이법이 잘 생각나지 않는 문제라면, 완전 탐색을 이용해 코딩을 한 후 최적화하는 과정을 사용한다면 문제를 해결에 도움을 받을 수 있을 것이다. 완전 탐색의 시간 복잡도는 주로 O(N!), O(2^N)이다. 시간 복잡도를 알고 있으면, 문제의 조건을 보고 필요한 알고리즘을 유추하는 방법도 있다고 하니 시간 복잡도에 대해 알아놓으면 좋을 것 같다. 완전 탐색은 반복문을 이용하는 방법, 재귀 함수를 이용하는 방법이 있는데 보편적으로 사용되는 것은 재귀 함수라고 한다. 반복문의 경우 길이가 변하는 문제를 다룰때 구현이 복잡해진다는 단점이 있다. 초보자의 경우에는 재귀함수가 .. 이전 1 다음
