Problem Solving 썸네일형 리스트형 BOJ 2342 - dance dance revolution 문제 링크https://www.acmicpc.net/problem/2342 문제 해결 1. dp[l][r][stage] : 현재 stage에서 왼발이 l, 오른발이 r에 위치할 때 사용한 최소의 힘 주의할 점 || 생각해볼 점 1. 그리디라고 생각할 수 있지만 항상 현재 해가 최적이 될 수 없다. 아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost. 아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost. 그리디로 해결할 수 없다. 그러므로 DP를 이용해서 해결해야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 6086 - 최대 유량 문제 링크https://www.acmicpc.net/problem/6086 문제 해결 1. 기본적인 Maximum Flow 문제다. 주의할 점 || 생각해볼 점 1. 시간 복잡도 O(VE^2)을 위해서 BFS를 이용한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 5675 - 음주 코딩 문제 링크https://www.acmicpc.net/problem/5676 문제 해결 1. 수열의 크기, 쿼리 모두 최대 이므로, segment tree를 이용한다. 2. segment tree를 initialize할 때, 양수면 1, 음수면 -1, 0이면 0을 tree[node]에 넣어준다. 주의할 점 || 생각해볼 점 1. 값을 구하는 쿼리에서 범위를 넘어가게되면 1을 출력한다. 왜냐면 1은 양, 음, 0 에 영향을 끼치지 않기 때문이다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 codeground practice - 극단적인 수 문제 링크 로그인을 해야만 볼 수 있다. 문제 해결 1. K번 째 극단적인 수를 구하는 문제. K의 범위가 10억이므로 자료구조에 담아서 해결하기에 부적합. 2. 극단적인 수를 길이로 나눠보면 길이가 1 늘어날 때, 2배씩 늘어남을 알 수 있다. 이를 이용해서 K번 째 극단적인 수의 길이를 먼저 구한다. 3. K번 째 극단적인 수의 길이가 L이라고 하자. 44...44 부터 77....77 까지는 부터 번 째라고 할 수 있다. 4. 같은 길이의 극단적인 수를 오름차순으로 정렬하면, 맨 앞자리 부터 절반씩 4 또는 7로 나뉘게된다. 그러므로 이분탐색을 이용해서 mid 보다 작으면 4를 출력하고 아니면 7을 출력한다. 주의할 점 || 생각해볼 점 1. 이분탐색을 할 때 끝점을 으로 설정하고, (시작점+1) .. 더보기 BOJ 14621 - 나만 안되는 연애 문제 링크https://www.acmicpc.net/problem/14621 문제 해결 1. "모든 정점이 연결되어야한다", "도로의 합이 최소가 되어야한다" → 최소신장트리(MST) 문제를 크루스칼 알고리즘(Kruskal Algorithm)으로 해결 주의할 점 || 생각해볼 점 1. 최소 경로를 해결하는 Dijkstra 알고리즘을 사용할 수 없다. 실제 정점끼리의 최소 거리랑 신장된 트리에서의 거리는 다를 수 있다. 2. 이분 그래프로 해결하려면 까다롭다. 그래서 정점마다 W or M 을 저장해서 서로 같다면 연결에서 제외했다. 3. 만약 모든 정점이 연결되지 않으면 -1을 출력하는 것을 잊으면 안된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1495 - 기타리스트 문제 링크(Link)https://www.acmicpc.net/problem/1495 문제 해결(Solution) 1. dp[i][j] : i번 곡에서 j만큼의 볼륨을 가질 수 있는 지에 대한 여부. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 재귀함수 안에서 볼륨 j가 0보다 작은 지 또는 M보다 큰지 제일 먼저 확인해줘야 한다. 2. 만약 볼륨 값이 범위를 넘어가게 되면 의미없는 수를 반환해야한다. 그렇지 않으면 그 값이 계속해서 다른 재귀함수에 사용된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1884 - 고속도로 문제 링크https://www.acmicpc.net/problem/1884 문제 해결 1. 다익스트라에서 돈이라는 개념이 들어간 문제. 주의할 점 || 생각해볼 점 1. dist[i][j] : 정점 i 에서 j만큼 돈을 소모한 상태일 때의 거리. (원래 다익스트라에선 일차원 배열로 선언한다.) 2. 정점 N을 만나면 바로 종료한다. ① 정점 N에서 바로 종료하지 않았을 때. ② 정점 N에서 바로 종료했을 때 시간과 메모리 모두 확연하게 줄어든다. 참고 - KCM Travel (이 문제와 비슷하다) : https://www.acmicpc.net/problem/10217 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2568 - 전기줄 - 2 문제 링크https://www.acmicpc.net/problem/2568 문제 해결 1. 한 전봇대의 줄을 정렬하고 반대편의 가장 긴 증가하는 수열(LIS)을 구한다. 주의할 점 || 생각해볼 점 - 참고 - LIS : https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EC%A6%9D%EA%B0%80_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1038 - 감소하는 수 문제 링크https://www.acmicpc.net/problem/1038 문제 해결 1. 전체 감소하는 수는 1023개밖에 안되기에 전체 탐색이 가능하다 2. recursive하게 돌아볼 수 있다. 주의할 점 || 생각해볼 점 1. 9,876,543,210 은 int 범위를 넘어가기에 long long으로 선언해야한다. 2. 0번째 감소하는 수가 0이므로 set.size()가 N+1 같거나 커야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 5558 - 치 ~ 즈 문제 링크https://www.acmicpc.net/problem/5558 문제 해결 1. 최소 시간으로 치즈를 모두 먹어야한다. 상하좌우로 움직일 수 있으므로 BFS (넓이 우선 탐색)를 사용한다. 2. 번호 순서대로 치즈를 먹기 위해서 왔던 길도 되돌아가야하므로 BFS를 응용해야한다. 3. 한 번에 해결하기 보다는 (시작점 → 1번 치즈), (1번 치즈 → 2번 치즈), (2번 치즈 → 3번 치즈) ... 순으로 문제를 나눠서 해결하는 것이 좋다. 주의할 점 || 생각해볼 점 1. 방문했던 곳을 매번 false로 초기화시켜줘야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 2 3 4 5 6 7 8 9 다음
