Probelm Solving/BOJ19 BOJ1777 순열복원 1777번 순열복원 순열의 길이 N과 inversion sequence가 주어지면 이를 복원하여 원본 순열을 찾는다. inversion sequence의 i번째 원소 = 원본 수열에서 i보다 뒤에 위치하고 i보다 작은 수의 개수 i보다 작은 수의 개수를 알고 있으니, 큰 수부터 원본 수열에서의 위치를 찾아주면 된다. 주어진 예시로 파악해보자 (inversion sequence = 반전 수열이라고 하자) N=8, 반전 수열 = 0 1 0 2 2 1 2 0 1. 반전 수열의 여덟 번째 원소 0이 의미하는 바는 원본 수열에서 8보다 뒤에 위치하고 8보다 작은 수는 0개라는 뜻 따라서 원본 수열에서 8은 가장 마지막 위치에 있는, 여덟 번째 원소이다. ⇒ 원본 수열 = _ _ _ _ _ _ _ 8 2. 이제 반.. 2022. 8. 18. BOJ2020 부분 염기서열 2020번 부분 염기서열 주어진 염기서열을 문자열로 볼 때, 문자열의 모든 부분 문자열에 대해 m번 이상 나타나는 부분 문자열의 개수를 구하고 1)길이 2)사전식 으로 나열했을 때 k번째의 부분 문자열을 구한다. 두 가지 방법이 있다. 1. BFS 2. Suffix, Prefix 활용 두 방법 모두 길이 순으로 부분 문자열을 찾는다는 게 그나마의 공통점인 듯 1. BFS 길이가 len인 어떤 문자열 s가 m번 이상 등장한 경우 문자열 s를 prefix로 하고 길이가 len+1인 문자열 s'를 찾아 탐색하면서 길이가 짧은 순으로 문자열을 탐색할 수 있다. 아래 두 자료구조를 사용한다. queue Q; map M; 먼저 길이가 1인 부분 문자열을 찾아야 한다. for (int i = 0; i < n; i++.. 2021. 8. 25. BOJ7812 중앙 트리 7812번 중앙트리 트리와 각 간선의 가중치가 주어질 때 한 꼭짓점에 대해 모든 꼭짓점과의 거리 합이 최소일 때의 그 값을 구한다. 즉 중앙 정점과 모든 꼭짓점과의 거리 합을 구한다. DFS, DP 당연히 모든 점에 대해 거리를 다 계산해볼 순 없고 트리이므로 DFS, 중앙 정점이 될 수 있는 점을 DP로 찾아가며 푼다. 처음에 DFS 두 번에 푸는 방법으로 해결했는데, 한 번만으로도 충분했다. 일단 간선은 벡터 E에 간선을 { 자식 노드 , 가중치 } 로 저장한다. DFS 두 번 하는 방법: 트리 먼저 만들고, 중심을 옮길지 말지 결정 0을 기준으로 모든 정점의 거리 합을 계산한 후 0보다 하위인 정점이 중앙 정점이 될 수 있는지 판단 1. 0에서 DFS, 모든 정점과 0사이의 거리 합 계산 이때 각 .. 2021. 7. 30. BOJ2549 루빅의 사각형 2549번 루빅의 사각형 4×4 격자판이 있다. 행을 한 개 골라 아래쪽으로 k번(1≤k≤3) 움직이거나 열을 한 개 골라 오른쪽으로 k번(1≤k≤3) 움직이는 것을 한 번 움직인다고 한다. 격자판의 숫자가 주어질 때, 최소 횟수로 격자판을 움직여 1부터 16까지 순서대로 배열된 격자판으로 만드는 횟수(≤7)와 방법을 출력한다. 일단은, 되는대로 BFS를 돌려봤지만 역시 메모리 초과로 통과할 수 없었다. 한 번 움직이는 경우의 수는 8(행/열 개수)*3(k 개수)였고 아무리 정답이 7번 이내로 나온다 해도 24^7개의 경우를 확인하려니 당연히,, 몇 가지 최적화로 가짓수를 줄여봤지만 그래도 메모리초과였다. 방법 1. BFS + 양방향 탐색 + map BFS로 찾되 양방향으로 탐색하기로 했다. 주어진 상태.. 2021. 7. 25. BOJ3830 교수님은 기다리지 않는다 3830번 교수님은 기다리지 않는다 1번부터 N번까지의 샘플에 대해 두 샘플의 무게 차이 정보가 주어질 때 교수님이 요구한 두 샘플의 무게 차를 구할 수 있으면 출력하고 구할 수 없으면 UNKNOWN을 출력한다 Disjoint Set Union & Find를 이용하는 문제인데 edge에 cost가 있다. 분리집합 문제는 여러 개 풀었었는데 가중치가 있는 건 처음 풀어봐서 꽤 헷갈리고 오래 걸렸다. scanf,printf보다 cin,cout이 훨씬 빠르고 편했다. par[N] N개 샘플의 부모 (set number) w[N] N개 샘플의 set 내 무게 (부모 무게를 0으로 했을 때의 무게) ! a b c : b가 a보다 c그램 무겁다. a와 b를 union한다. 1. a,b의 부모 para,parb를 구.. 2021. 6. 19. BOJ1949 우수 마을 1949번 우수 마을 N개의 마을로 이루어진 트리 형태의 나라에서 우수 마을인 두 마을이 인접하지 않고 우수 마을이 아닌 마을은 적어도 한 우수 마을과 인접해야 할 때 우수 마을로 선정된 마을 주민 수의 최댓값을 구한다. Tree + DP 2535번과 비슷하다. 다만 2535번에서는 v가 선택될 때/아닐 때 두 가지만 고려하면 됐는데 여기서는 v의 자식노드까지 생각해야 한다. 좀 더 상위버전인 듯. 우수마을을 선정하는 조건을 파악하자 1. 우수 마을인 두 마을이 인접하지 않는다. v가 우수마을이면 v의 모든 자식 노드는 우수 마을이 될 수 없다. 2. 우수마을이 아닌 마을은 적어도 한 우수 마을과 인접하다. v가 우수마을이 아니라면 v의 자식 노드 중 하나가 우수 마을이거나, v의 부모 노드가 우수 마을.. 2021. 6. 10. BOJ1014 컨닝 1014번 컨닝 N*M크기의 직사각형 교실에서 컨닝을 방지하도록 앉힐 수 있는 최대 학생 수를 구한다. 현재 위치를 기준으로 동일 행의 좌우(←→), 윗 행 좌우 대각선(↖↗) 위치의 답지를 베낄 수 있다. 비트마스킹 + DP 학생이 앉은 상태, 앉을 수 없는 자리 등을 bit로 표현하고 i행에서 k의 상태로 앉을 수 있는 학생 수의 최댓값을 i-1행을 고려해 구한다. * 3줄 요약 cnt[ k ] 행의 상태가 k일 때 해당 행에 앉는 학생의 수 (= k를 이진수로 나타낼 때 1의 개수) dp[ i ][ k ] i행에 k의 상태로 앉을 때의 최대 학생 수 dp[ i ][ k ] = dp[ i-1 ][ up ] + cnt[ k ] (up은 i행의 상태가 k일 때 i-1의 상태로 가능한 것 중 dp값이 가장.. 2021. 5. 19. BOJ3716 도로 네트워크 3716번 도로 네트워크 1부터 N까지의 도시를 연결하는 N-1개의 도로가 주어지고 서로 다른 두 도시 D, E가 주어지면 D와 E를 연결하는 도로 중 가장 짧은 것의 길이와 긴 것의 길이를 구한다. 이때 모든 서로 다른 두 도시간 경로는 한 개만 존재한다. ⇒ 주어진 그래프가 트리이다. LCA문제임은 빠르게 파악할 수 있었다. 다만 공통조상뿐 아니라 공통조상까지의 도로의 길이 중 최댓값/최솟값도 알아야 했고 여기저기 헷갈린 탓인지 여러 차례 틀려서 힘들었다ㅠ 1. Get P 먼저 각 도시의 1, 2, 4, 8, ...번째 조상을 조사한다. 1을 root로 하여 BFS로 탐색하고, 조상을 탐색하며 도로 길이의 최소/최대를 구한다. P[ i ][ k ] r = 도시 i의 $2^{\mathrm{k}}$번째 .. 2021. 4. 23. BOJ1086 박성원 1086 박성원 길이 50 이하의 자연수가 N(≤15)개 주어질 때 주어진 모든 자연수를 한 번씩 사용하여 이어 붙여 만든 자연수가 100이하의 자연수 K로 나누어 떨어질 확률을 구한다. example. (A) N=3 K=27 { 104, 4, 90 } 104490 104904 410490 490104 901044 904104 여섯 개 중 세 개만 나누어 떨어지므로 1/2 출력 (B) N=3 K=13 { 12, 2, 2 } 1222 1222 2122 2212 2122 2212 여섯 개 중 두 개만 나누어 떨어지므로 1/3 출력 * s[0]="12", s[1]="2", s[2]="2"일 때, s[0]+s[1]+s[2]="1222"와 s[0]+s[2]+s[1]="1222"를 모두 세야 한다. (순열 방식이 .. 2021. 4. 21. BOJ13141 Ignition BOJ13141 Ignition 그래프가 주어지고, vertex 중 한 개에 불을 질렀을 때 그래프가 모두 타는 최소 시간을 출력 불은 1초에 1만큼 태울 수 있고 어디에 불을 붙여도 그래프가 반드시 전체 다 탈 수 있는 경우만 주어지며 시점과 종점이 같은 edge도 주어지고, 같은 시점과 같은 종점 사이 여러 개의 edge가 존재할 수 있다. 두 가지가 필요하다. 1. 한 vertex에 불이 도달할 수 있는 최소 시간 2. 두 vertex 간 edge가 모두 타는 시간 1의 경우 같은 vertex라도 불을 어디에 붙이느냐에 따라 값이 다르다. 결국엔 all vertex → all vertex의 최단거리를 구해야 하므로 floyd-warshall로 구한다. 2의 경우 두 vertex 간 가장 긴 edge.. 2021. 3. 17. 이전 1 2 다음
