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를 리턴하는 어떠한 함수 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17680 리뷰 자료구조 및 알고리즘 Least Recently Used → 벡터와 같은 자료구조에서 Hit일 경우 remove and push back을 통해 '리뉴얼' 함으로써 삭제를 방지 문제 풀이에서의 핵심 포인트 Hit/Miss에 대한 case 구현하기: 굳이 몇 번 Hit되었는지 count할 필요 없이, Hit일 경우 remove and push back 대/소문자 구별 없이 처리하기: - cpp reference가 사용가능하다면 아래와 같은 함수(ToLower) 제작 - 사용이 안 된다면 #include strcasecmp(a.c_str(), b.c_str()) == 0 을 이용 Ca..

문자열 입력 받기 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)만에 구..