PS (182) 썸네일형 리스트형 [백준] 별자리 만들기 (C++) https://www.acmicpc.net/problem/4386 좌표로 주어진 그래프를 노드그래프로 바꾼 후 크루스칼 알고리즘을 사용하면 쉽게 풀리는 문제. 다만 소수점을 주의해야한다. 크루스칼 알고리즘은 유니온 파인드와 그리디를 섞은 최소 스패닝 트리를 구할 수 있는 알고리즘이다. #include#include#include#includeusing namespace std;pair points[101];vector>> edges;bool visited[101];int par[101];int Find(int x) { if(par[x] == x) return par[x]; else return par[x] = Find(par[x]);}void Union(int x, int y){ int .. [백준] 17609번 회문 (C++) https://www.acmicpc.net/problem/17609 회문이란?좌우대칭인 문자열을 의미한다. ABAABBA 같은 문자열이 회문이다. 해당 문제는 문자 하나까지는 봐줄 때 회문인지를 판단할 수 있는지를 물어보는 문제이다. 풀이방향1. 회문인지 파악하는 방법문자열의 시작과 끝에서 서로 비교하면서 틀린것이 없다면 회문 (시간복잡도 N) 2. 하나 생략을 하는 방법1번 로직을 진행하다가 하나만 더 진행시키면 된다. 예를들어 ABCBDA 를 하고 있었다면 B(1)와 D(5)가 다를 때, 왼족 인덱스만 1 증가 시키거나 오른쪽 인덱스만 하나 감소 시키면 된다.3. 그렇다면 이것은 같은 방식을 계속 다시 써야할 것 같다.회문파악을 계속하면서 두 값이 다를 때만 인덱스를 변화시키므로 재귀를 돌면 될 것 .. [백준] 1459번 걷기(C++) https://www.acmicpc.net/problem/1459 오랜만에 PS를 해봤다. 꾸준히 해야되는데 일과 병행하는 것은 정말 쉽지 않다. 최소비용을 구하는 문제이다. 두가지 풀이법이 생각난다. BFS 대각선이동, 좌우이동이 가능한 BFS를 사용하면 예제는 풀릴 것이다. 그러나X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고라는 문구를 보고 BFS는 접어야함을 알 수 있다. 왜냐하면 BFS의 시간 복잡도는 행렬그래프에서는 O(M ^(N * N)) 이기 때문이다. (M은 가능한 방향) 즉 여기서는 좌우이동, 대각선이동까지 총 8방향이 가능하기 때문에 시간복잡도가 엄청나게 커진다. Greedy해당 문제는 좌우이동과 대각선의 비용이 다르다. 즉, 0,0 에서 1,1로 이동할 때.. [백준 2616번/Java] 소형기관차 https://www.acmicpc.net/problem/2616 [문제 분석] 길이 N의 수열을 M개씩 3개로 묶을 때 최댓값을 구하는 문제이다.[알고리즘]1. 연속된 수열을 가져와야하기 때문에 누적합을 사용하여 시간을 단축한다.2. 이 문제는 결국 모든 경우의 수를 살펴봐야하는데 그것을 얼마나 효율적으로 메모이제이션하느냐에 따라 달려있다. DP[i][j] = i번 열차가 j번 수열까지 도달했을 때 최대 값 이 점화식은 배낭문제에서 아이디어를 가져올 수 있다. 다만 배낭문제는 각 배낭에 각 객체를 넣을 수 있을지 없을지 확인하는데 이것은 연속된 객체를 삽입할지 말지 결정해야하는 다른점이 있다. 그렇다면 점화식은 어떻게 구성해야할까 먼저 예제로 시뮬레이션 해보자. N = 7, M = 235 40 50 .. [백준 2240번] 자두나무 (C++) https://www.acmicpc.net/problem/2240 최댓값을 구하는 문제로 가장 먼저 그리디, 완전탐색, DP가 떠오르는 것이 일반적이다.어떻게 풀 수 있을까? 먼저 최대 자두가 떨어지는 숫자는 1000이고 움직일 수 있는 횟수는 30이다. 1. Greedy탐욕법으로 풀 수 있을까? 탐욕법이 성립하기 위해서는 지금 선택하는 조건이 이후의 선택에 영향을 주어선 안된다.즉, 2번에서 자두가 떨어질 때 이동하여 잡는 이 선택이 뒤에서 영향을 주어선 안되는데 조금만 생각해도 당연히 영향을 줄 수 밖에 없는 구조이다. 그러므로 탐욕법으로는 풀 수 없다.2. 완전탐색완전탐색으로는 정확도만 풀이가 가능하다. 한 지점에서 취할 수 있는 경우의 수는 두가지다. 이동하거나, 가만있거나 그러므로 2^30의 시.. [백준 2169번] 로봇 조종하기 (C++) https://www.acmicpc.net/problem/2169 꽤 생각할 것이 있는 다이나믹프로그래밍 문제였다. 먼저 이 왜 다이나믹 프로그래밍인가? 1. N이 약 1000으로 백트래킹으로 모든 경우의 수를 다 진행할 시 당연히 시간초과에 걸린다.2. 한 지점에 도착할 수 있는 경우의 수가 정해져있다.3. 2번에 의해 큰 문제를 작은 문제로 쪼갤 수 있다. 이 근거로 다이나믹 프로그래밍이라고 유출할 수 있겠다. 그렇다면 어떻게 풀어야할까? 처음에는 0,0 에서 시작하는 재귀 + DP를 생각했다. 그러나 문제가 있었다. 이 문제는 왼쪽과 오른쪽으로 이동을 할 수 있다. 1 2 34 5 67 8 9 라고 할 때 재귀를 진행하면 1번에서 2번으로 이동하면 2번은 다시 1번으로 이동할 수 있다. 그.. [백준 17298번] 오큰수 (C++) https://www.acmicpc.net/problem/17298 O(N^2)으로 풀면 쉽게 풀리지만 그러면 골드난이도가 아닐 것이다. N이 크기 때문에 O(N) 혹은 O(N Log N)으로 풀어내야한다.어떻게 최적화 할 수 있을까? 2, 9, 10, 2, 11 예제를막대로 그려보면 다음과 같다. 그리고 각 A, B, C, D, E의 꼭대기에서 오른쪽으로 갈 때 가장먼저 부딫히는 막대의 크기를 출력해야하는 문제다. 아하.. 그렇다면 맨 오른쪽에서부터 막대를 새우면서 진행하면 될 것 같다. 1. 11 막대를 새운다.2. 2막대를 새우고 11과 비교한다. 오큰수: 113. 10 막대를 새우고 2와 먼저 비교한다. 앗.. 2보다 10이 더 크다. 즉, 이제 2는 절대로 누군가의 오큰수가 될 가능성이 없다. .. [백준 1949번] 우수 마을 (C++) https://www.acmicpc.net/problem/1949 이전에 비슷한 문제의 유형을 풀어본적이 있기 때문에 트리에서 다이나믹 프로그래밍 문제라는 것을 알 수 있었다. 사실 말은 거창하지만 DFS + DP 와 다를 것이 없다. 문제를 살펴보자 '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.뭔가 조건이 많아보이는데 사실 1,2번을 만족하면 3번은 자동으로 될 수밖에 없다... 이전 1 2 3 4 ··· 23 다음
