전체 글
[대전] 대흥동 해피치즈스마일
대흥동 카페 모먼트에 들른다음에 한 300~400미터 걸어가면 있다. 주택건물? 같이 생긴 건물에 있다. 사실 떡볶이에 돈까스라면 절대 실패하지 않는 메뉴이다. 궁동에도 있던데 체인점이니 맛이 비슷하겠지 궁동도..? 배가 부를때 가서 많이 먹지는 못했는데 담엔 배고플 때 가서 많이 먹어야 겠다. 첨에 실수로 치즈추가를 주문했는데 까먹으셔서 금방 다시 해주셨다. ㅎ
[대전] 대흥동 모먼트
대흥동에 있는 크로플 맛집이다. 브라운 치즈 크로플을 무조건 먹어야 한다. 2피스면 조금 더 싸지는데 다음에 가게 되면 두피스를 먹어야겠다. 옆에 있는 블루베리 빵도 엄청 맛있다. 내부는 엄청 심플하게 생겼다. 막 사람이 엄청 많이 들어갈 수 있지는 않다. 내가 갔을 때에는 막 기다리거나 그러지는 않았는데 운이 나쁘다면 기다려야 할지도... 그리고 오른쪽은 서비스 받았다 ㅎㅎ
[백준] 구슬 탈출 2
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net bfs를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 5 5 ##### #..B# #.#.# #RO.# ##### 다음과 같이 row, column이 첫줄에, 그리고 이후로는 구슬이 움직이는 공간이 2d array로 주어집니다. 이 때, 상하 좌우로 구슬을 기울여 빨간 구슬이 빠져나오게 하는 최소 횟수를 구해야 합니다. 이 때, 10번 ..
[백준] 사전
https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 간단히 요약하면, a의 갯수 M, z의 갯수 N이 주어질 때, 사전형태로 나열 했을 경우, K 번째 문자열을 return 해야 합니다. 메모리제한이 생각보다 작게 걸려 있어서 combination을 저장해서 하는 방식에서는 메모리 초과가 나왔는데 두가지 방법 모두 설명해 보겠습니다. 우선 조합을 이용하기 위해 피보나치 수열을 dp table로 구성해서..
[백준] 1로 만들기 2
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 요약하면, 3으로 나누거나, 2로 나누거나, 1을 빼는 총 3종류의 연산을 할 수 있을 때, 연산을 해서 1을 만들 수 있는 횟수의 최솟값을 return 해야 합니다. 또한 이렇게 최소 횟수로 진행되는 경우에 등장하는 숫자도 return 해야 합니다. 이 문제는 숫자를 return해야 하는 과정이 조금은 까다로운데 설명해 보도록 하겠습니다. Dynamic programming의 코드를 작성 할 때는 2가지의 방법을 이용하는데 top-down, b..
[백준] 내리막 길
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS와 다이나믹 프로그래밍을 사용하는 문제입니다. 문제부터 간단하게 요약하면, 다음과 같이 2d array에서 각 숫자들은 높이를 의미합니다. 가장 왼쪽 위에서 가장 오른쪽 밑으로 도달하는 경로의 수를 구해야 하는데, 이 때, 높이가 높은 곳에서 낮은 곳으로 이동하는 경우의 수를 return 해야 합니다. .우선 아이디어는 다음과 같습니다. 특정 칸에 도착을 했다고 가정해봅시다. 이 때, 그 이후에 ..
[백준] 동전 1
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍을 사용하는 문제입니다. 메모리를 많이주지 않아, 불필요한 할당을 하니 처음에 메모리 초과가 나왔는데 둘다 설명해 보도록 하겠습니다. 우선 문제부터 요약하면, n가지 종류의 동전으로 가치합을 k로 만드는 경우의 수를 return 해야 합니다. 1,2,5의 가치를 가진 동전으로 10의 가치를 만드는 경우는 10가지 이므로 10을 return 해야 합니다. 우선 아이디어는 다음과 같습..