개발 블로그

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 1. 문제 설명 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다. 상근이의 집에서 ..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 문제 설명 2. 문제 풀이 구현 해야 할 것 N X N 크기의 리스트를 받아 집, 치킨가게의 위치를 각각의 리스트에 받는다. M개의 치킨집을 골라야 하므로 조합을 이용하여 visited 배열을 만들어 M개의 자리에 true 값을 넣는다. 조합이 완성이 되면 각각의 집에서 고른 치킨집중에서 가장 가까운 거리를 총 거리에 더해준다 완성된 총 거리들중 가장 가까운 거리를 구한..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 문제 설명 2. 문제 풀이 구현 해야 할 것 보드에서 상어 위치 찾기 먹을 수 있는 물고기의 거리와 자리를 넣은 리스트 만들기 (bfs) 그중 거리, x축, y축으로 정렬하여 가장 근접한 물고기 찾고 상어 위치 바꾸기 바꿀 때마다 거리를 초로 계산해 더해주어 답 구하기 3. 코드 import java.io.BufferedReader; import java.io.IOException; ..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 문제 설명 예제 입력 5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6 예제 출력 0 2 3 7 INF 2. 코드 import java.util.ArrayList; import java.util.Iterator; import java.util.PriorityQueue; import java.util.Scanner; public c..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 설명 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 복사 8 예제 출력 1 복사 92 2. 문제 풀이 파이썬으로 전에 풀었던..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 1. 문제 설명 2. 문제 풀이 2차원 배열로 만들어 1. 백트래킹을 이용해 가로선을 만들고 2. 만든 가로선으로 i번 세로선의 결과가 i번이 나오는지 체크한다. 3. 코드 import sys def check(): # i번 세로선의 결과가 i번이 나오는지 체크 for i in range(n): temp = i # 이동하는 세로선 위치 for j in range(h): if graph[j][te..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 1. 문제 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 문제 설명 (0, 0) 에서 (n-1, m-1) 까지 이동할 수 있다면 거리를, 없다면 -1을 출력하는 문제인데 문제는 벽을 하나 부술 수 있다라는 것이였다. 1. 첫 시도 처음은 그냥 bfs를 시도한다. 그리고 벽을 하나씩 0으로 만들고 시도한후, 다시 1로 만든다. bfs를 시도할때마다 (n-1, m-1)를 리스트에 넣고 최댓값을 뽑는다. 최댓값이 0이라면 못가는..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제설명 동적 계획법(Dynamic Programming, DP)은 최적화 문제를 해결하는 알고리즘으로서, 아래의 내용을 항상 명심해야 한다. '전체의 문제'를 '부분 문제'로 잘 나누었는가? 그렇다면 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가? 부분 문제들을 해결하며 얻는 결과값을 메모이제이션하는가? 부분 문제의 점화식은 부분 문제들 사이의 '관계'를 빠짐없이 고려하는가? 22..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 문제 설명 양팔 저울을 이용해 주어진 추로 특정 무게를 만드는 문제이다. 추를 사횽해 무게를 만드는 방법은 3가지 이다. 추의 무게를 더한다. 추의 무게를 뺀다. 추를 사용하지 않는다. 위 3가지 규칙으로 만들 수 있는 모든 무게를 dp에 저장한다. 재귀를 사용해서 코드를 작성했다. 2. 코드 설명 n = int(input()) weight = list(map(int, input().split..