20, 시작, 새로운.

Greedy 알고리즘 개념 Greedy Algorithm 정의 탐욕, 욕심쟁이 알고리즘이라고도 불리며, 현재 상태에서의 최적의 해가 최종적으로도(전체적으로도) 최적의 해가 될 것이라고 가정하고 접근하는 알고리즘이다. 그리디 알고리즘은 대부분의 문제에서 해답에 대한 '근사적인' 솔루션을 도출해 낼 수 있다는 장점이 있고, 그리디로 풀 수 있는 문제는 다음과 같은 두 가지 조건을 만족시켜야 한다. 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않아야 한다. 최적 부분 구조: 문제에 대한 최종 해결 방법은 sub problem들의 optimal solution들로 구성된다. 주의할 점 모든 문제가 그리디 알고리즘으로 풀리는 것이 아니기 때문에, 이 알고리즘으로 풀리는 문제인지 아닌지 구분하기가 매..

브루트포스(완전탐색) 개념 문제를 해결하기 위한 솔루션을 모든 영역에서 탐색한다고 하여 완전탐색이다. 경우의 수를 모두 고려하는 방식이기 때문에 문제의 영역이 크다면 시간초과의 가능성이 있으므로, 조건을 잘 고려하여야 한다. 단순한 완전탐색 문제는 간단히 해결할 수 있고, DFS, BFS, 백트래킹 등의 알고리즘으로도 해결할 수 있다. 특정 문제들의 경우(N개 중에서 M개를 가지고 문제를 해결해야 할 때 등) 재귀적인 형태로 문제를 해결해나갈 수 있다. 주의할 점 - 백트래킹을 써야 하는지 알기 어렵다. 재귀를 이용한 탐색 방법이 여전히 익숙하지 않고 어색하다. 문제를 딱 봤을 때 어떤 알고리즘을 사용해야하는지 감을 잡기 어려운 경우가 종종 있는데, 그 중 하나가 백트래킹이다. 주어진 N 개 중 K개를 ..

Tree Algorithm LCA(Lowest Common Ancestor) 가장 낮은 공통 조상 구하기 문제: 두 정점 사이의 최단 거리를 빠르게 찾을 수 있다. 선형탐색(O(N))의 방식과 이분탐색(O(logN))의 방식이 있음. 선형 탐색은 두 노드의 깊이를 같게 한 뒤 선형적으로(차례로) parent A == parant B 인지 확인하는 방법. parent[노드 A]를 1차원 배열에 저장하여 선형적으로 탐색한다. 이분탐색은 노드별 parent 정보를 2차원배열에 저장하는 것. parent[노드번호 A][노드 A의 2의 k승 거리에 있는 부모노드] 즉, parent[A][T] = 노드 A의 2^T 번째 조상. ex. parent[13][0] = 9, parent[13][1] = parent[9][..

이분 탐색, 매개변수 탐색 정의 이분탐색(Binary Search) 정의 이분 탐색(Binary Search)은 순차 탐색의 시간복잡도 O(N)에서 O(logN)으로 탐색 시간을 줄여 탐색하는 방법으로, 정렬된 배열 안에서만 사용이 가능하다. 단순한 '탐색'은 코딩테스트에 출제되지 않는다. 이를 활용한 문제가 나온다. mid == target이면 탐색을 종료해도 상관없다는 게 매개변수 탐색과 다른 특징이다. 매개변수 탐색(Parametric Search) 정의 조건에 맞는 최대/최소값을 찾을 때 파라미터를 주로 사용하며, 이 파라미터는 이분 탐색을 이용해서 left, right, mid(=parameter) 를 계산하여 구하는 문제이다. 파라미터를 변수로 값을 True/False를 리턴하는 어떠한 함수 ..

문자열 입력 받기 getline 입력 문자열이 스페이스 바 혹은 '\n' 이 있는 문자열일 경우, cin >> string 으로는 처리하기 힘들다. getline으로 처리할 경우 손쉽게 처리할 수 있다. cin의 getline 이 있고, string의 getline이 있다. 나는 string 의 getline 이 편했다. 입력받는 문자열에 대해 deliminator 전까지를 하나의 string으로 처리해준다. getline(istream& is, string str); getline(istream& is, string str, char dlim); 보통 istream으로는 cin 을 쓰고, 저장하고자 하는 변수 str를 지정해주면 된다. 주의사항 이전 입력에서 '\n'이 처리되지 않았을 경우(buffer..

투포인터 알고리즘 개념 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작한다. 이때문에 투포인터 알고리즘이라 부른다. 알고리즘 설명 및 특징 완전탐색으로 해결하면 시간 초과가 나는 문제를 투포인터 알고리즘으로 시간복잡도를 줄여 문제를 해결할 수 있다. (완전탐색의 경우 for 문을 중첩해서 2개 이상 형성해야하는 반면, 투포인터는 반복문 1개로도 가능하게 된다) 1차원 배열의 완전탐색에서 n제곱 꼴의 시간복잡도를 n 의 1제곱 으로 줄일 수 있다. 알고리즘 대표 유형문제 - 2003 수들의 합 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트 해보면 구간 합을 구간 배열로 O(1)만에 구..

동적 계획법 정의 동적계획법(Dynamic Programming) 개념 동적계획법이란, 큰 문제에 대한 해답을 얻기 위해 해당 문제를 크기가 더 작은 문제들로 쪼개어, 작은 문제들을 먼저 해결한 뒤 그 결과들을 이용해서 원래의 큰 문제를 해결하는 기법을 의미한다. 정리하면, Dynamic Programming에서의 핵심은 문제를 잘개 쪼개 조그마한 단위에서의 해결 방법을 구해(점화식) 그것이 최종적인 솔루션과 같은 형태로 구성될 수 있도록 설계하는 것이다. 동적계획법 문제풀이의 예시 - 점화식 동적계획법은 점화식만 구하면 된다. 아주 간단한 피보나치 수열의 경우로 예를 들어보자. n-1번째 수와 n-2번째 수의 합이 n번째 수가 되므로, 재귀를 이용하거나 배열에 저장하는 형태로(즉 초기에 답을 구해놓은 ..

그래프 탐색 개념 및 유형 그래프 탐색 문제 기본 해결 방법 문제가 NxM 형태의 격자 형태를 띄거나, 노드 & 간선의 형태로 그래프 및 트리의 형태를 갖게 되는 경우 그래프 탐색 및 최단경로 탐색 알고리즘을 문제 해결 알고리즘으로 염두에 두어야 한다. 관련 유형 문제로는 아래와 같은 예시를 들 수 있다. 프로그래머스 코딩테스트 페이지를 참고하자. 알고리즘 Breadth First Search를 통해서는 노드를 탐색할 때 같은 깊이의 노드들을 같이 탐색하므로(큐를 이용하기 때문), answer을 탐색할 때 최소깊이/최소간선 수 를 보장하지만, 그래프의 깊이가 깊고 큰 그래프의 경우 공간복잡도가 커질 우려가 있다. 코딩테스트 선에서는 크게 고려할 필요는 없다. 격자 형태를 띄는 문제에, 시작 지점으로부터 ..