코딩스토리

백준 2447번 - 별 찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 이 문제는 재귀 알고리즘 문제이다. 단계별로 풀어보기 문제들 중에서 안 풀었던 문제가 있길래 풀려고 보니 별 찍기.. 쉬울 거 같아서 빨리 풀어야겠다 하고 풀었는데 2시간 넘게 고민해도 답이 안 나오네?? 결국 구글링을 통해 알아낸 사실은 2차원 배열을 사용하는 것!! 이 문제의 핵심은 저거였다.. 그것도 모르고 몇 시간을 고민했..

백준 14266번 - 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 이 문제는 BFS문제(다이나믹 프로그래밍을 사용한)이다. 최근 풀었던 BFS문제중에 가장 어려웠다. 처음에는 가볍게 queue에 pair로 현재 이모티콘 숫자와 클립보드의 개수를 받아서 풀어보려 했는데 문제의 조건 중 '클립 보드에 복사'라는 조건이 자꾸 걸렸다. 생각해보다가 2차원 배열을 사용하면 될 것 같아서 써봤는데 바로 틀렸습니다.. 디버깅해보니 너무 많은 ..

백준 12852번 - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이 문제는 BFS, 다이나믹 프로그래밍 문제이다. 처음에는 top-down 방식으로 문제를 해결하려 했다. 문제의 조건에 맞게 코드를 짜 보았는데 마지막 출력에서 살짝 맘에 안 들었다. 출력 부분을 보면 n부터 내림차순으로 출력하는데, top-down 방식으로 해결하려면 dp[x]에는 x*3 또는 x*2 또는 x+1 이 들어가 있기 때문에 한번 vector나 배열에 다 넣고 오름차순 정렬을 해줘야 한다. 코드는 몇 줄 차이 안 나겠지만 시간 복잡도 면에서 botto..

백준 2206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 이 문제는 BFS(너비 우선 탐색) 문제이다. 해결 방법은 3차원 배열을 사용하는 것이다. 보통의 쉬운 수준의 BFS 문제들과 달리 '벽'이라는 장애물이 존재한다. 즉 벽을 부순 횟수를 기억해야 하는데 모든 위치에서 기억해야 하므로 3차원 배열을 사용해야 한다. 다행이 벽을 부술 수 있는 횟수가 1번 이므로 3차원 배열의 크기는 ..

백준 11000번 - 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 이 문제는 우선순위 큐를 사용한 문제이다. 처음 문제를 풀 때 실수했던 점은 입력을 받을 때 정렬되서 들어온다고 생각한 것이였다. (사실 생각한게 아니고 아무 생각없이 그냥 알고리즘만 생각해서 풀었따ㅎ) 그래서 한번 입력받을 때마다 우선순위 큐의 top과 비교해서 정답을 도출했는데 당연히 틀렸다. 고민하다가 생각난 풀이법이 우선순위 큐(Priority queue)를 두 개 사용하는 방법이다! 첫 번째 큐에는 모..