20, 시작, 새로운.

문제 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://www.acmicpc.net/problem/11066 동적계획법을 사용해서 푸는 문제. 가능한 조합을 전수조사해서 그 중 minimum 값을 구해 dp 배열을 채워나가면 된다. 점화식을 세우는 과정에서 많은 어려움이 있는 문제이다. 점화식 조건이 어려울 뿐 아니라, 단순히 dp의 이전 인덱스들과의 단순 연산보다 조금 더 심화되었다. 나의 문제 풀이 시도 및 발생한 문제점 가능한 모든 조합을 찾아야 한다는 점을 빠르게 캐치하지 못했음(dp 점화식 설계 실패) 문제를 쪼개서 해결해야한다는 점은 이해하고 있었지만, 점화식 설계가 틀렸다. 나의 접근은, 2차원 dp 배열에서 i 인덱스는 '어디까지 보았는가', j 인덱스는 '몇 개를 더했는가' 였고, dp 배열을 업데이트 할 때, 이전의..

문제 설명 https://www.acmicpc.net/problem/1325 A->B 라는 방향이 주어지는 그래프이며, 이 관계에서는 B가 A를 신뢰한다, B 입장에서 A를 해킹할 수 있다, 즉 B가 기준이 되는 문제이다. B 기준에서 연결된 노드의 개수가 몇 개인가, 노드별로 구분해서 카운트하고 정렬하는 문제이다. 방향 그래프 + 탐색 + 정렬 의 간단한 응용문제이나, 기계적으로 문제들을 풀었다면 사소한 부분들에서 헷갈리기 쉬운 문제이다. 문제풀이 시도 1 도착지점의 노드가 중요한 문제이므로, A B 라는 인풋이 주어졌을 때, A를 기준으로 graph를 그리지 않고, B를 기준으로 그래프를 그렸음(push_back을 거꾸로 했다는 의미) B 기준에서 연결된 노드의 개수를 세는 문제와 동일하다. B 기준..

문제 설명 https://www.acmicpc.net/problem/2294 Dynamic Programming의 정석과도 같은 문제 유형 중 하나이다. 주어진 동전의 가치로 목표 가치를 달성하기 위해 필요한 최소의 동전 개수를 계산하기 위해 다이나믹프로그래밍으로 접근해야 한다. 문제에 따라서 완전탐색 등의 다른 방식으로도 접근이 가능하나, 해당문제는 조건에 의해 시간복잡도를 계산해서 제한 시간 안에 계산이 가능한지 확인한 후, 완전탐색으로는 불가능하다는 점을 인식해야 한다. 문제 풀이 시도 및 문제점 고찰 첫 번째 아이디어: 목표 가치(ex. 15)까지의 크기를 갖는 배열을 생성한 후, 0부터 해당 목표 index까지의 최소 동전 개수를 하나씩 계산해서 배열을 채워나가는 방식을 구상하였으나, 주어진 동..