![]()
문제https://www.acmicpc.net/problem/12101풀이* 첫째줄에 정수 n과 k가 주어진다.* n을 1, 2, 3의 합으로 나타내는 방법 중 사전 순으로 k번째에 오는 것을 출력해야 한다. (k번째로 오는 식이 없으면 -1 출력)1. 정수 n과 k를 입력받는다.2. DFS를 이용해 모든 조합을 생성하고, 조합이 완성되면 +로 문자열을 연결해 result 리스트에 저장한다.3. k번째 경우를 반환하는데, 없으면 -1을 출력한다. 코드 및 설명
문제 https://www.acmicpc.net/problem/10974 Algorithm 깊이 우선 탐색(DFS)과 백트래킹을 이용하여 모든 가능한 조합을 탐색한다.현재까지의 순열을 temp 리스트에 저장한다.모든 숫자를 하나씩 시도하며, 이미 사용된 숫자는 제외한다.순열이 완성되면 출력하고, 다른 가능한 순열을 찾기 위해 마지막 숫자를 제거한다(백트래킹). Coden = int(input())temp = []def dfs(): if len(temp) == n: print(*temp) return for i in range(1, n + 1): if i not in temp: temp.append(i) dfs()..
문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)풀이K보다는 작으면서 가장 큰 동전을 선택한 다음, 그 다음으로 큰 동전을 선택하면서 현재 채운 값과 사용한 동전 수를 업데이트하며 K를 모두 채웠을 때 출력한다.코드N, K = map(int, input().split())coins = [int(..
![]()
문제https://www.acmicpc.net/problem/2525풀이* 첫째줄에는 현재 시간(시간, 분)이, 둘째 줄에는 요리하는데 필요한 시간이 주어진다.* 현재시간에서 오븐 구이가 끝나는 시간을 출력해야 한다.1. 자연수 h, m 그리고 d를 입력받는다.2. 끝나는 시간을 계산하기 위해 변수 x를 만들고, 분으로 변환한 후 범위 내 출력을 생각해 1,440으로 나눈다.3. 시와 분을 구하기 위해 필요한 연산을 하고, 제시한 대로 출력한다. 코드 및 설명
![]()
문제 https://www.acmicpc.net/problem/10872 Algorithm반복문을 사용해서 1부터 N 까지 곱해준다. Coden = int(input())result = 1if n > 0: for i in range(1, n+1): result *= iprint(result)
문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.풀이N부터 시작하는 위치를 deque에 넣고, visited배열로 각 위치의 방문 여부(-1로 초기화)와 최소 시간을 업데이트 해나간..
![]()
문제 & 링크https://www.acmicpc.net/problem/1916 풀이1. 정점(도시)의 개수 n과 간선(버스)의 개수 m을 입력받는다.2. 그래프를 인접 리스트의 형태로 저장한다.3. 최단 거리 배열인 cost를 큰 값으로 초기화한다.4. 다익스트라 알고리즘을 사용하여 최단 거리를 탐색한다.5. 우선 순위 큐를 사용해서 최소 비용부터 탐색한다.6. 모든 인접 정점을 처리하며 최단거리를 갱신한다. 코드#include #include #include #include using namespace std;int cost[1001];vector> V[1001];void dijkstra(int a) { priority_queue, vector>, greater>> pq; pq.push(ma..
![]()
문제 https://www.acmicpc.net/problem/17608 Algorithm첫 줄에 막대기의 개수 n을 입력 받는다둘째 줄부터 n개의 막대기 길이를 입력받는다.스택의 마지막을 1로 설정하여 마지막 막대기보다 긴 막대기가 있으면 count += 1을 하고 막대기의 길이를 가장 긴 막대기로 새로 저장한다. Codeimport sysinput = sys.stdin.readlineN = int(input())stack = []for _ in range(N): stack.append(int(input()))last = stack[-1]count = 1for i in reversed(range(N)): if stack[i] > last: count += 1 ..
![]()
문제https://www.acmicpc.net/problem/15649풀이* 한 줄에 자연수 N, M이 주어진다. (1 ≤ M ≤ N ≤ 8) * 1부터 N까지 자연수 중에서 중복 없이 M개의 수를 고른 조합을 모두 구한 후, 사전 순서대로 증가하는 조합을 출력해야 한다.1. 자연수 N, M을 차례로 입력받는다.2. 1부터 N까지의 자연수로 리스트를 생성, 그 리스트에서 길이가 M인 모든 수열을 변수에 저장한다.3. 문제에서 제시한대로 정렬하고 숫자, 공백으로만 출력한다. 코드 및 설명for문 내의 구조가 조금 다를 뿐 두 코드 모두 잘 작동함.
문제N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.입력첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.출력첫째 줄에 지나야 하는 최소의 칸 ..
![]()
문제 https://www.acmicpc.net/problem/15874 Codek, n = map(int,input().split())k %= 26s = list(input())for i in range(n): x = ord(s[i]) if 65
![]()
문제정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.입력의 마지막 줄에는 0이 두 개 주어진다.출력각 테스트 케이스에 대해서, 섬의 개수를 출력한다.예제 입력 1..
