Problem Solving (135) 썸네일형 리스트형 [ 프로그래머스 - 동굴 탐험 ] 해설 및 코드 https://programmers.co.kr/learn/courses/30/lessons/67260 목적 두 방의 경로(path)와 순서(order)가 주어질 때, n개의 방을 모두 방문할 수 있는지 구하자. 접근법 트리 형태로 구성된 동굴을 0번 방 부터 dfs 방식으로 방문한다. 도중에 순서(order)로 인해 계속해서 아래로 갈 수 없는 방은 매달아 둔다. 그리고 가능한 시점에 방문을 계속한다. (아래 코드 참조) #include using namespace std; const int MAXN=2e5; bool vis[MAXN]; int prior[MAXN],hang[MAXN]; vector edge[MAXN]; void visit(int v){ if(vis[v])return; if(!vis[pr.. [ BOJ 백준 1126번 - 같은 탑] 해설 및 코드 https://www.acmicpc.net/problem/1126 목적 N개의 블록을 이용해 두 탑의 높이를 같도록 쌓는 여러가지 방법 중, 최대 높이를 구하자. 접근법 1. 두 탑의 높이 차를 이용한 DP를 사용하자. 2. s[i][j]를 i번째 블럭을 이용해 높이차가 j인 두개의 탑을 쌓았을 때의 최대 높이라고 정의한다. 예를 들어, i번째 블럭을 이용해 높이 차가 5이 두 탑을 쌓았다고 가정하겠다. 그러면 왼쪽 탑이 높든 오른쪽 탑이 높든 높이 차 j라는 하나의 경우로 처리할 수 있다. 또한, 탑의 높이를 [L, R]와 같이 표현하면, [10, 15]나 [25, 20]를 s[i][5]=25 라는 값으로 처리할 수 있다. 3. i+1번째 블럭을 이용하는 경우는 어떻게 처리하나? 각 j의 값에 따라 세.. [ BOJ 백준 2473번 - 세 용액 ] 해설 및 코드 https://www.acmicpc.net/problem/2473 목적 용액의 특성값들이 N개 주어질 때, 3가지의 특성값을 더해 절대값이 0에 가장 가까운 용액의 특성값들을 구하자. 접근법 첫 번째 용액이 정해진 상태라면, 나머지 두 개의 용액을 선택하여 절대값이 0에 가깝도록 하는 것은 투 포인터 알고리즘으로 구할 수 있다. (투포인터 알고리즘에 대한 설명은 다음 글 참조 [백준 2470 - 두 용액]) 첫 번째 용액으로 선택할 수 있는 용액의 수는 총 N-2개이며, 이 용액의 특성값을 더하여 절대값이 0에 가까운 값을 만들기 위한 나머지 두 개의 용액만 구하면 된다. #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; typede.. [ BOJ 백준 2470번 - 두 용액 ] 해설 및 코드 https://www.acmicpc.net/problem/2470 목적 용액의 특성값들이 N개 주어질 때, 특성값을 2개를 더해 절대값이 0에 가장 가까운 용액의 특성값들을 구하자. 접근법 투 포인터 알고리즘으로 구현이 가능하다.(완전 탐색이나 이분 탐색보다 빠르고 간단하다.) 투 포인터 알고리즘은 다음과 같이 정렬된 배열이 있다면, 배열의 처음과 끝을 가리키는 L과 R을 서로가 가까워지도록 이동하는 방식으로 동작한다. 초기 상황을 제외하고 최대 N-2번의 포인터 이동이 있는데, 각 턴마다 두 포인터가 가리키는 수의 합이 0에 수렴하도록 한 개의 포인터를 이동해야 한다. 즉, 수의 합이 양수일 때는 R을 이동하여 합을 줄여주고, 음수일 때는 L을 이동하여 합을 늘려준다. 동시에 절대값의 최소값을 갱신해주.. [ BOJ 백준 17780번 - 새로운 게임 ] 해설 및 코드 https://www.acmicpc.net/problem/17780 목적 다음과 같은 체스판에서 말들을 규칙에 따라 이동하여 게임을 진행할 때, 게임이 끝나는 턴의 번호를 출력하자. 접근법 이 프로그램의 동작은 다음과 같은 일련의 과정이 종료조건(4개의 말이 쌓이는 경우 or 턴 번호가 1000을 넘어가는 경우)을 만족할 때까지 반복된다. 1. 말의 이동 가능 여부 확인 말은 번호 순으로 이동 하는데, 만약 이동시킬 차례의 말이 다른 말 위에 올라가 있는 상태라면 이동할 수 없으며, 차례를 건너 뛰게 된다. (해당 상태는 말의 이동을 처리하는 함수에서 설정하자.) 그리고 이동하려는 위치를 검사해야 한다. 만약 체스판의 범위를 벗어나거나, 칸이 파란색이라면 진행 방향을 반대로 하여 이동하게 된다. 2. 말.. [ BOJ 백준 1328번 - 고층 빌딩 ] 해설 및 코드 https://www.acmicpc.net/problem/1328 목적 빌딩의 개수 N, 가장 왼쪽 또는 오른쪽에서 봤을 때 보이는 빌딩의 수 L과 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하자. 접근법 1. 빌딩을 세우는 과정을 크기가 큰 빌딩부터 작은 빌딩을 하나씩 추가하는 방식으로 진행해보자. 다음과 같이 10개의 빌딩이 세워져 있다. 왼쪽과 오른쪽에서 볼 때 각각 3개, 2개가 보인다. 이러한 경우에 크기가 제일 작은 빌딩 하나를 추가하여 세울 수 있는 경우의 수는 11가지가 된다. 하지만 N,L,R만 고려하면 세가지 경우가 나오게 된다. 가장 왼쪽에 배치하면 이전 경우의 L이 1증가하는 경우가 1개 만들어지고, 가장 오른쪽에 배치하면 이전 경우의 R이 1증가하는 경우가 1개 만들어진.. [ BOJ 백준 13398번 - 연속합 2 ] 해설 및 코드 https://www.acmicpc.net/problem/13398 목적 n개의 정수 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하자. (수를 하나 제거할 수 있다.) 접근법 1. 백준 1912번 - 연속합 문제에서 수 제거 조건만 추가된 문제이다. 점화식을 조금만 수정하면 된다. 2. s[i]를 a배열의 i번째 요소를 끝으로 하는 최대 연속합으로 정의하면, s[i]는 a[i] + max(s[i-1], 0) 이다. 3. t[i]는 a의 i번째 원소까지의 최대 연속합에서 1개의 원소를 뺀 최대값으로 정의하면, t[i]는 max(s[i-1], t[i-1] + a[i]) 이다. 4. 구해야 하는 값은 s[1]~s[n], t[1]~t[n]중 최대값이다. 1 2 3 4 5 6 7 8 .. [ BOJ 백준 1912번 - 연속합 ] 해설 및 코드 https://www.acmicpc.net/problem/1912 목적 n개의 정수 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하자. 접근법 1. s[i]를 a배열의 i번째 원소를 끝으로 하는 최대 연속합이라고 정의할 때, s[i]는 a[i] + max(s[i-1], 0)이다. 2. 최종적으로 구하고자 하는 것은 s[1] ~ s[n]중 최대 값이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,ans,prev,curr; cin>>n>>ans; prev=ans;.. 이전 1 2 3 4 ··· 17 다음
