https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 최근 백준 open Contest에서 그리디 + 구현 문제를 만났는데 아이디어는 바로 생각했으나 구현을 못해서 못풀었다. 구현력을 늘리고자 이 문제를 풀었다. 각 행과 열에는 최소 하나 이상의 경비병이 있어야한다. 최소로 경비병을 세우려면 몇명을 더 추가로 배치해야하냐는 문제이다. 필자는 2차원 배열을 받은 후에 전치행렬(행과 열을 바꾼 행렬)을 만들어서 문제를 해결하였다. 처음 원래 ..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 처음 보면 그래프 문제라고는 생각하기 힘들수도 있지만, 범위를 보면 하나씩 다 채울만 하겠다 라는 생각이 든다. 숫자가 0부터 9999까지 밖에 없으므로 이전에 했던 과정을 저장하면서 4가지의 과정을 노가다로 다 저장하면 된다. 처음에는 "" 빈 문자열이고 숫자를 받으면 그에대해서 D, S, L, R을 각각 실행한다. 그럼 실행한 숫자까지 필요한 과정으로 각각 D, S, L, ..

https://www.acmicpc.net/problem/12383 12383번: Diamond Inheritance (Large) The first line of the input gives the number of test cases, T. T test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, N. The classes are numbered from 1 to N. N lines fo www.acmicpc.net 구글 Code jam에 출제된 문제이다. 그래프의 한 노드에서 시작해서 다른 노드에 도착하는 경로의 가짓수가 최..

https://www.acmicpc.net/problem/2879 2879번: 코딩은 예쁘게 첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수 www.acmicpc.net 최소 횟수로 현재 탭 개수에서 맞춰야하는 탭 개수로 바꾸라는 그리디 알고리즘 문제이다. 그리디 알고리즘이라는게 특별한 알고리즘이 있는게 아니라 그냥 어떻게 하면 최적의 경로로 문제를 해결할까? 생각하고 구현하는 문제이다. 방법은 간단하다. 현재 위치에서 탭을 줄여야한다면, 양옆까지 확인해서 줄여야하는 탭은 같이 줄여준다. 대신 줄이는 횟수가 다를수 있으므로 줄여야하는 탭 중에서..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제를 읽었을 때는 ~압축한다 라고 나와있어서 좌표압축 문제로 착각할 수 있지만, 좀만 더 읽어보면 분할정복이라는 것이 보인다. 특정 공간이 0또는 1로만 이루어지면 그 공간 전체를 0 또는 1로 압축한다고 하고, 전체를 압축한 결과를 내라는 문제이다. 종이의 개수나 색종이 만들기 문제와 비슷하지만 괄호를 어느 부분에 넣어야되냐가 생각하기가 조금더 어렵기 때문에 실버1의 난이도로 배정..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제를 보자마자 오큰수하고 똑같은 문제라고 생각했다. 예전 포스팅에서 오큰수문제를 다뤘었는데 그때 deque를 사용하여 숫자를 하나씩 빠르게 비교할수 있다는 것을 배웠다. 만들 숫자를 stack에다가 하나씩 넣으면서, 넣어야될 숫자가 먼저 들어간 숫자보다 크면 원래 있던 숫자를 지우고 스택에 숫자를 추가했다. 당연히 들어가고 나서는 그 앞의 숫자들하고도 비교해주어야 하기 때문에 while을 이용하여 똑같은 과정을 반복했다. 마지막에 비교가 끝나고 한번도 비교를 안하게 되면 ..