mojo's Blog

문제 링크 => 9527번: 1의 개수 세기 (acmicpc.net) 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 수학을 이용한 문제이다. 먼저 규칙성을 발견하면 다음과 같다. (1) 2^0 ~ 2^1 - 1 일 때 1의 개수의 합 : 1 = 1 + 0 (2) 2^1 ~ 2^2 - 1 일 때 1의 개수의 합 : 3 = 2 + 1 (3) 2^2 ~ 2^3 - 1 일 때 1의 개수의 합 : 8 = 4 + 4 (4) 2^3 ~ 2^4 - 1 일 때 1의 개수의 합 : 20 = 8 + 1..

문제 링크 => 10942번: 팰린드롬? (acmicpc.net) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 문제가 약간 이상한 느낌인게 칠판에 적는 숫자가 항상 1의 자리 숫자인 것 같다. 예를 들어서 1, 23, 232, 1, 232, 32, 1 에 대한 palindrome 처리를 할 때 [2, 3] 에 대한 Query 는 true 가 나와야 함에도 불구하고 통과한 코드는 false 처리를 한다는 것이다. 그래서 모든 input 을 1의 자리로 생각하고 풀었더니 굉장히 간단해졌다. Optimal Substruc..

문제 링크 => 6087번: 레이저 통신 (acmicpc.net) 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS 문제이다. 사실 이런 유형의 문제는 몇번 풀어봤지만 아직도 부등호를 정확하게 어떻게 잡아야 할지에 대해서는 여러번 디버깅을 통해서 찾고는 한다. int 타입의 check 배열을 선언함으로써 해당 위치에 대한 거울을 놓을 수 있는 최소 갯수를 판단하기 위한 용도가 필요하다. 또한 이전에 어떠한 거울로 인해서 가르키는 방향에 대한 정보도 필요하다. 시작 지점부터 끝 지점까지 BFS 를..

문제 링크 => 1958번: LCS 3 (acmicpc.net) 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 알고리즘 수업때 배웠던 LCS 에서 문자열이 하나 더 추가되어 총 3개의 문자열의 LCS를 구해야 한다. 문자열 X, Y, Z 가 있다고 할 때 Optimal Substructure은 다음과 같다. 이때 LCS(X, Y, Z) 를 X, Y, Z 문자열들의 Longest Common Subsequence 값이라고 할 때, Xn == Yn == Zn 일 경우 => LCS(Xn, Yn, ..

문제 링크 => 1922번: 네트워크 연결 (acmicpc.net) 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리 문제이다. 간선에 대한 정렬은 merge Sort를 이용하였다. 그리고 Union-Find 알고리즘을 이용하여 Cycle이 발생하지 않도록 확인해주었다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include struct Edge { int from, to, dist; }; int parent[100001]; int N, M, cnt; Edge E[100001], tmp[100001]; void mergeSort(int le..

문제 링크 => 11066번: 파일 합치기 (acmicpc.net) 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 이 문제는 알고리즘 시간때 배웠던 행렬 곱 연산을 최소로 만드는 그 문제와 비슷해서 한번에 풀렸다. T(i, j) = 파일 i 번째에서 j 번째까지를 하나의 파일로 합칠 때 최소 시간 S(i, j) = 파일 i 번째에서 j 번째까지를 합치는 과정에서 걸리는 최소 시간 예를 들어서 20, 50, 30 이 있다고 하자. S(1, 1) = 20, S(2, 2) =..