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][..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17679# 리뷰 문제유형: 구현, 그래프 탐색 실수한 부분 블록이 떨어지고 난 뒤 구현 완료 후 2개의 테스트 케이스가 틀려서 해결하지 못한 상태로 그냥 넘어갔었다. 아마 실제 시험이었다면 틀림 처리 당했을 것이다. 내가 실수한 부분은 블록이 '터지고 난 뒤' 위에서 아래로 차곡차곡 쌓이는 부분이다. 바로 위 인덱스로만 덮어씌웠기 때문에, 몇 가지 예제가 틀렸던 것이다. 2x2 블록을 형성한 부분과 겹침을 허용하면서 2x2 블록을 확인하기 2x2 블록이 다른 2x2 블록과 겹쳐서, 7개 혹은 6개를 만들 수 있었다. 나는 이러한 중복 카운팅을 제거하기 위해, BFS이후 2x2 블록에 해당하는 x..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17686# 리뷰 문제 유형: 구현, 문자열 처리, 정렬 주어진 두 문자열을 정렬하기 위한 커스텀 함수를 작성할 때 복사-붙여넣기 이후 수정하는 과정에서 동기화가 안 되었다. 조그마한 부분을 찾아내는 것이 힘드므로, 중복되는 부분은 약간의 생각 이후 함수화하는 것이 편리함을 깨달았다. 핵심 연속한 문자열에서 문자와 숫자를 구분해낼 수 있는가 → sstream, strind indexing 후 += chararcter 연산 혹은 push_back 문자열을 사전 순으로 정렬할 수 있는가 → tolower를 사용할 수 있는가(프로그래머스 레퍼런스를 참고하면 되는데, std::transform을 이용한 ..

문제 https://www.acmicpc.net/problem/15686 리뷰 문제 유형: 구현, 백트래킹(브루트포스) 구현 문제에 백트래킹이 결합된 문제다. 백트래킹을 오랜만에 접해서 그런지, 쉬운 활용이었지만 생각해내기 어려웠다. N개의 치킨 집 중 M개를 선정해야 하는데, 기준은 도시 치킨 거리를 최소화하는 M개이다. 먼저 N개 중 M개를 선택하기 위해서는 Recursive방식을 선택해야 한다(백트래킹). 재귀적으로 호출하며, end condtition으로 cnt == M 일때 원하는 계산을 수행하면 된다. 백트래킹의 단점은 stackoverflow를 발생시킬 수 있다는 것인데, 이를 방지하기 위해서는 몇 가지 장치가 필요하다. A, B, C, D, E 중 3개를 선택하는 조합을 확인한다고 하면, ..

문제 https://www.acmicpc.net/problem/16235 리뷰 문제 유형: 구현, 시뮬레이션, 자료구조 격자를 이용하지만 그래프 탐색을 이용하지는 않는다. 문제를 천천히 이해하다보면, 계절에 따른 시퀀스만 잘 구현하면 된다는 것을 어렵지 않게 파악할 수 있다. 주의해야할 점은, Spring → Summer로 넘어가는 시점에서 나무의 나이 > 양분 일 경우 죽는 나무를 파악하기 위한 과정에서 반복문의 조건을 건드리게 되는 경우가 발생할 수 있다. // 예시 for(int i=0; i 양분) vectorB[i].erase .... else .... } // answer ... vectorB.clear() vectorB = vectorC 위와 같이 vector B에 대해 반복하는 for 문 내..

문제 https://www.acmicpc.net/problem/16234 리뷰 문제 유형: 구현, 시뮬레이션, 그래프 탐색, 자료구조 그래프 탐색의 약간의 변형문제이다. 그래프 탐색을 진행할 때는 보통 DFS의 재귀, BFS의 큐 방식을 이용하고, 재귀 혹은 큐를 위한 '조건'을 설계한다. 문제에 따라서 해당 조건은 예를 들어, 해당 지점보다 작은 값으로 or 방문하지 않았던 곳으로 or 해당위치와 같은 값을 갖는 곳으로 ... 등등등의 조건이 생성된다. 해당 문제도 동일하다만, '조건'을 설계하고 plus, 전체적인 반복 시퀀스를 구성해야 한다는 점이 다른 점이다. '전체 x, y 좌표'를 x++, y++ 해 가면서 그래프 탐색을 응용해 문제를 해결해나가야 함을 파악하기 어려웠다. 유형이 동일함을 파악..

문제 https://www.acmicpc.net/problem/3190 리뷰 문제 유형: 구현, 시뮬레이션, 자료구조 격자 위에서 그래프 탐색 방식과 비슷하게 x, y 축 이동 방향을 회전시키면서 이동하다가, 사과를 발견하면 몸통의 길이를 늘려주고, 범위 밖으로 나가거나 혹은 자기자신과 부딪히면 종료되도록 만들어야 한다. 이 때 필요한 시퀀스를 정리해볼 필요가 있다. 입력값에 따라 이동 방향을 회전 시키기 → dir[4][2] 의 반복 아이템을 먹었을 경우 늘어나는 몸통 좌표 기억하기 / 먹지 않았을 경우 줄어드는 꼬리 부분 → 뱀의 몸통 좌표들을 기억하는 큐:머리가 back, 꼬리가 front가 되어 pop and push로 구현할 수 있다. 범위를 나가거나 → InRange 함수로 구현 가능 자기 자..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92341 리뷰 차량 번호와 소요시간을 계산해서, 주어진 공식에 맞게 계산한 값을 차량번호가 작은 순서대로 리턴하면 된다. "들어갔다 나가지 않았다면" 을 보다 간단하게 "기록이 홀수 개라면" 이라고 조건을 생각할 수 있을 것이고, (굳이 map을 만들어 false, true로 구분할 필요는 없다) 주차한 시간에 대한 계산은 hour min 구분은 필요 없으므로 min 단위로 바꿔 계산하면 편할 것이며, (굳이 min이 작은 경우 hour에서 1을 빼고... 하는 사람이 하는 계산 처럼 구현할 필요는 없다) 차량번호가 작은 순서대로 리턴하는 것은 차량 번호를 int로 하는 vector를 선언해서 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49993#fn1 리뷰 주어진 skill의 character 순서에 맞는 skill_trees 인지를 구분하는 방법을 찾는 데 오랜 시간이 걸렸다. 처음에는 skill_trees의 string과 비교하면서 같은 문자일 경우, 이전 idx보다 작은 위치라면 false, ... 의 방식으로 indexing 으로만 해결하려고 하였다(그랬더니 2~3개의 예외 케이스에서 자꾸 실패했다) 실패하는 예외케이스를 생각할 수 없어 그 다음에는 배열을 만들어 비교하려고 하였으나, 엉성해서 성공하지 못했다. 어떠한 알고리즘을 사용해야 하는지 쉽게 떠올리지 못했고, 다소 빠르게 해결하고자 마음이 급했다. 포인트 str..

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