2024년 5월에 푼 프로그래머스 코딩문제("코딩테스트 공부 목적")
본 글은 프로그래머스와 백준에서 푼 문제를 정리한 글입니다.
1. [Lv1: 탐욕법(Greedy)] 체육복(정답률: 53%)
[문제 설명]
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
[제한사항]
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
[입출력 예]
| n | lost | reserve | return |
| 5 | [2, 4] | [1, 3, 5] | 5 |
| 5 | [2, 4] | [3] | 4 |
| 3 | [3] | [1] | 2 |
[코드]
def solution(n, lost, reserve):
memory = [[1 for i in range(n)] for j in range(n)]
for i in reserve:
memory[0][i-1] += 1
memory[1] = [-1 if i in lost else 0 for i in range(1, n+1)]
memory2 = []
for j in range(n):
memory2.append(memory[0][j] + memory[1][j])
for k in range(n):
if k==0:
if memory2[k]==0 and memory2[k+1] >=2:
memory2[k]=1; memory2[k+1] -= 1
elif k==(n-1):
if memory2[k]==0 and memory2[k-1] >= 2:
memory2[k]=1; memory2[k-1] -= 1
else:
if memory2[k] == 0 and memory2[k-1] >= 2:
memory2[k]=1; memory2[k-1] -= 1
elif memory2[k] == 0 and memory2[k+1] >=2 :
memory2[k]=1; memory2[k+1] -= 1
answer = 0
for l in memory2:
if l >= 1:
answer += 1
return answer2. [백준: 시뮬레이션] 공 넣기(정답률: 52.652%)
[문제]
도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다.
도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다.
공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.
둘째 줄부터 M개의 줄에 걸쳐서 공을 넣는 방법이 주어진다. 각 방법은 세 정수 i j k로 이루어져 있으며, i번 바구니부터 j번 바구니까지에 k번 번호가 적혀져 있는 공을 넣는다는 뜻이다. 예를 들어, 2 5 6은 2번 바구니부터 5번 바구니까지에 6번 공을 넣는다는 뜻이다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ N)
도현이는 입력으로 주어진 순서대로 공을 넣는다.
[출력]
1번 바구니부터 N번 바구니에 들어있는 공의 번호를 공백으로 구분해 출력한다. 공이 들어있지 않은 바구니는 0을 출력한다.
n,m = map(int, input().split()); answer = [0 for i in range(n)]
for _ in range(m):
i,j,k = map(int, input().split())
for step in range(i-1,j):
answer[step] = k
for l in answer:
print(l, end=" ")3. [백준: 구현] 히스토그램에서 가장 큰 직사각형(정답률: 27.013%)
[문제]
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.
[입력]
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.
[출력]
각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.
[첫번째 코드풀이] -> 시간 초과 문제
while True:
value = list(map(int, input().split()))
if value[0] == 0:
break
n = value[0]
h = value[1:]
max_margin = 0
for i in range(n):
if i==0:
min_height = h[i]
for j in range(i, n):
min_height = min(min_height, h[j])
max_margin = max(max_margin, (j - i + 1) * min_height)
print(max_margin)
[두번째 코드풀이] -> 스택 구조를 사용함으로써 해결
answer = []
while True:
value = list(map(int, input().split()))
if value[0] == 0:
break
n = value[0]
h = value[1:]
stack = [] # 높이를 저장하는 스택
max_margin = 0
for i in range(n):
while stack and h[i] < h[stack[-1]]:
height = h[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_margin = max(max_margin, height * width)
stack.append(i)
# 스택에 남은 높이들에 대한 계산
while stack:
height = h[stack.pop()]
width = n if not stack else n - stack[-1] - 1
max_margin = max(max_margin, height * width)
answer.append(max_margin)
for i in answer:
print(i)4. [백준: 다이나믹 프로그래밍] 설탕 배달(정답률: 37.357%)
[문제]
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
[출력]
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
[코드]
n = int(input())
a,b = divmod(n,5)
answer = []
for i in range(1, a+1):
n_5 = i
n_3,c = divmod(n-5*n_5,3)
if c==0:
answer.append(n_5+n_3)
d,e = divmod(n,3)
if e==0:
answer.append(d)
if not answer:
print(-1)
else:
print(min(answer))5. [백준: 그래프 이론]DFS와 BFS(정답률: 37.774%)
[문제]
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
[입력]
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
[출력]
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
[코드]
n, m, v = map(int, input().split())
adj_ = [[] for i in range(n+1)]
for _ in range(m):
start, end = map(int, input().split())
adj_[start].append(end)
adj_[end].append(start)
adj_[start].sort()
adj_[end].sort()
visited_DFS = [False]*(n+1)
visited_BFS = [False]*(n+1)
def DFS(graphs, v, visited):
visited[v] = True
print(v, end = ' ')
if graphs[v]:
for i in graphs[v]:
if not visited[i]:
DFS(graphs, i, visited)
from collections import deque
def BFS(graphs, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end = ' ')
if graphs[v]:
for i in graphs[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
DFS(adj_, v, visited_DFS)
print()
BFS(adj_, v, visited_BFS)
5. [백준: 그래프 이론] 미로 탐색(정답률: 44.246%)
[문제]
N×M크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
[입력]
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
[출력]
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
[코드]
n,m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
from collections import deque
def miro_dfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x,y = queue.popleft()
### 현재 위치에서 네 방향 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
## 미로 공간을 벗어나는 경우는 무시
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
## 벽인 경우도 무시
if graph[nx][ny] == 0:
continue
## 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
return graph[n-1][m-1]
print(miro_dfs(0,0))6. [백준: 구현(1019번)] : 책 페이지(정답률: 42.620%)
[문제]
지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.
[입력]
첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
[출력]
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.
[코드 1] -> "시간 초과 문제 발생"
n = int(input())
answer = [0 for i in range(10)]
for i in range(1,n+1):
for j in str(i):
answer[int(j)] += 1
for k in answer:
print(k, end=' ')
[코드 2]
N = int(input())
arr = [0]*10
num = 1
def make_nine(N):
while N%10 != 9:
for i in str(N):
arr[int(i)] += num
N -= 1
return N
while N > 0:
N = make_nine(N)
if N < 10:
for i in range(N+1):
arr[i] += num
else:
for i in range(10):
arr[i] += (N // 10 + 1) * num
arr[0] -= num
num *= 10
N //= 10
for i in arr:
print(i, end = ' ')
7. [백준: 다이나믹 프로그래밍(1463번)] : 1로 만들기(정답률: 32.970%)
[문제]
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
[입력]
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
[출력]
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
[코드]
x = int(input())
d = [0]*1000001
## d[0] = 0 & d[1] = 0 ## 각 수를 1로 만드는데 필요한 횟수'
for i in range(2, x+1):
d[i] = d[i-1] + 1
if i%2==0:
d[i] = min(d[i], d[i//2] + 1)
if i%3==0:
d[i] = min(d[i], d[i//3] + 1)
print(d[x])8. [프로그래머스: Lv2] : 당구 연습(정답률: 20%)
[문제]
프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.
머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.
오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.
머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.
당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. "원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.
[입출력 예시]
| m | n | startX | startY | balls | result |
| 10 | 10 | 3 | 7 | [[7, 7], [2, 7], [7, 3]] | [52, 37, 116] |
[코드(1)]: 내가 푼 풀이
def calc(x1,x2,x3,y1,y2,y3,n,m):
if x3==0:
if (y3==0) or (y3==n):
a,b = line(x2,x3,y2,y3)
x2 = -x2; y2=a*x2 + b
else:
x2 = -x2
if x3==m:
if (y3==0) or (y3==n):
a,b = line(x2,x3,y2,y3)
x2 = -x2; y2=a*x2+b
else:
x2 = 2*m - x2
if x3==((x1+x2)/2):
if y3==n:
y2 = 2*n - y2
if y3==0:
y2 = -y2
return (x2-x1)**2 + (y2-y1)**2
def line(x1,x2,y1,y2):
a = (y2-y1)/(x2-x1)
b = y1 - a*x1
return a,b
def wall_(x1,x2,y1,y2,n,m):
coord = [[0,(y1+y2)/2], [(x1+x2)/2,n], [m, (y1+y2)/2], [(x1+x2)/2,0]]
if (x1==x2):
if (y1>y2):
coord.remove([(x1+x2)/2,0])
if (y1<y2):
coord.remove([(x1+x2)/2,n])
if (y1==y2):
if (x1>x2):
coord.remove([0,(y1+y2)/2])
if (x1<x2):
coord.remove([m, (y1+y2)/2])
return coord
def solution(m, n, startX, startY, balls):
## 꼭짓점 -> 반대방향 -> 4가지 고려 가능.
wall1 = [[0,0], [m,0], [0,n], [m,n]]
line1 = [line(startX,wall[0],startY,wall[1]) for wall in wall1]
answer = []
for ball in balls:
wall2 = []
for i,j in enumerate(line1):
a,b = j
if ball[1] == (a * ball[0] + b):
if (i==0) & (startX < ball[0]):
wall2.append(wall1[i])
if (i==1) & (startX > ball[0]):
wall2.append(wall1[i])
if (i==2) & (startX < ball[0]):
wall2.append(wall1[i])
if (i==3) & (startX > ball[0]):
wall2.append(wall1[i])
wall2.extend(wall_(startX, ball[0], startY, ball[1],n,m))
value = []
for wall in wall2:
value.append(calc(startX,ball[0],wall[0],startY,ball[1],wall[1],n,m))
answer.append(min(value))
return answer
[코드(2)]: 다른 사람 풀이
- 내가 푼 코드는 반복되는 부분이 존재한다. [코드(2)]는 내가 푼 코드보다 더 간결하게 풀었다.
def solution(m, n, startX, startY, balls):
answer = []
def getDist(x1, y1, x2, y2):
return (x1 - x2)**2 + (y1 - y2)**2
for (ballX, ballY) in balls:
distU = getDist(startX, startY, ballX, ballY + 2*(n-ballY))
distD = getDist(startX, startY, ballX, -ballY)
distL = getDist(startX, startY, -ballX, ballY)
distR = getDist(startX, startY, ballX + 2*(m-ballX), ballY)
if startX == ballX:
if startY > ballY:
distD = int(1e9)
else:
distU = int(1e9)
if startY == ballY:
if startX > ballX:
distL = int(1e9)
else:
distR = int(1e9)
dist = min((distU, distD, distL, distR))
answer.append(dist)
return answer9. [백준: 구현(5373번)] : 큐빙(정답률: 38.678%)
[문제]
루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다.
큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다.
이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다.
루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스는 다음과 같이 구성되어져 있다.
- 첫째 줄에 큐브를 돌린 횟수 n이 주어진다. (1 ≤ n ≤ 1000)
- 둘째 줄에는 큐브를 돌린 방법이 주어진다. 각 방법은 공백으로 구분되어져 있으며, 첫 번째 문자는 돌린 면이다. U: 윗 면, D: 아랫 면, F: 앞 면, B: 뒷 면, L: 왼쪽 면, R: 오른쪽 면이다. 두 번째 문자는 돌린 방향이다. +인 경우에는 시계 방향 (그 면을 바라봤을 때가 기준), -인 경우에는 반시계 방향이다.
[출력]
각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란색은 y, 빨간색은 r, 오렌지색은 o, 초록색은 g, 파란색은 b.
[코드]
9번 문제는 두 개의 참고자료를 활용하여 풀었다.
"" 참고자료 ""
[Idea 1]. 반시계 방향은 시계 방향으로 3번 돌린 것과 같다.
[Idea 2]. [Figure 1]과 같이 전개도로 생각해서 푼다.
[Idea 3]. 우리가 고려해야 할 것은 돌아가는 도면(["면"])과 돌아가는 도면에 붙은 면들이다.
[Idea 4]. 회전을 하면 3칸이 움직인다.
앞면("빨간색 면")을 예시로 들고자 한다.
- 빨간색 면
$$\begin{pmatrix}18 & 19 & 20 \\21 & 22 & 23 \\24 & 25 & 26 \end{pmatrix} \to \begin{pmatrix} 21 & 18 & 29 \\24 & 22 & 20 \\25 & 26 & 23 \end{pmatrix} \to \begin{pmatrix}24& 21 & 18 \\25 & 22 & 19 \\26 & 23 & 20 \end{pmatrix}$$
이를 코드로 구현하면 다음과 같다.
def moveDimension(cube,index):
for _ in range(2):
temp = cube[index][0][0]
cube[index][0][0] = cube[index][1][0]
cube[index][1][0] = cube[index][2][0]
cube[index][2][0] = cube[index][2][1]
cube[index][2][1] = cube[index][2][2]
cube[index][2][2] = cube[index][1][2]
cube[index][1][2] = cube[index][0][2]
cube[index][0][2] = cube[index][0][1]
cube[index][0][1] = temp
- 빨간색 면과 붙어있는 면(12개의 값)
빨간색 면과 붙어있는 면들은 [Figure 3]와 같이 움직일 것이다.
이를 코드로 구현하면 다음과 같다.
if direction == 'U':
## 앞면을 돌리는 경우, 앞면에 붙어 있는 또 다른 면들도 돌아감.
temp = cube[0][0]
cube[0][0] = cube[4][0]
cube[4][0] = cube[5][0]
cube[5][0] = cube[3][0]
cube[3][0] = temp
## 앞면 돌리기
moveDimension(cube,2)
다른 면에 대해서도 똑같이 적용하면 아래 함와 같다.
def move(cube, direction):
if direction == 'U':
## 앞면을 돌리는 경우, 앞면에 붙어 있는 또 다른 면들도 돌아감.
temp = cube[0][0]
cube[0][0] = cube[4][0]
cube[4][0] = cube[5][0]
cube[5][0] = cube[3][0]
cube[3][0] = temp
## 앞면 돌리기
moveDimension(cube,2)
elif direction == 'D':
temp = cube[0][2]
cube[0][2] = cube[3][2]
cube[3][2] = cube[5][2]
cube[5][2] = cube[4][2]
cube[4][2] = temp
moveDimension(cube,1)
elif direction == 'F':
temp = cube[2][2]
cube[2][2] = [cube[3][2][2], cube[3][1][2], cube[3][0][2]]
cube[3][0][2], cube[3][1][2], cube[3][2][2] = cube[1][0]
cube[1][0] = [cube[4][2][0], cube[4][1][0], cube[4][0][0]]
cube[4][0][0], cube[4][1][0], cube[4][2][0] = temp
moveDimension(cube,0)
elif direction == 'B':
temp = cube[2][0]
cube[2][0] = [cube[4][0][2], cube[4][1][2], cube[4][2][2]]
cube[4][2][2], cube[4][1][2], cube[4][0][2] = cube[1][2]
cube[1][2] = [cube[3][0][0], cube[3][1][0], cube[3][2][0]]
cube[3][2][0], cube[3][1][0], cube[3][0][0] = temp
moveDimension(cube,5)
elif direction == 'L':
temp = [cube[0][0][0], cube[0][1][0], cube[0][2][0]]
cube[0][0][0], cube[0][1][0], cube[0][2][0] = cube[2][0][0], cube[2][1][0], cube[2][2][0]
cube[2][0][0], cube[2][1][0], cube[2][2][0] = cube[5][2][2], cube[5][1][2], cube[5][0][2]
cube[5][0][2], cube[5][1][2], cube[5][2][2] = cube[1][2][0], cube[1][1][0], cube[1][0][0]
cube[1][0][0], cube[1][1][0], cube[1][2][0] = temp
moveDimension(cube,3)
elif direction == 'R':
temp = [cube[0][0][2], cube[0][1][2], cube[0][2][2]]
cube[0][0][2], cube[0][1][2], cube[0][2][2] = cube[1][0][2], cube[1][1][2], cube[1][2][2]
cube[1][0][2], cube[1][1][2], cube[1][2][2] = cube[5][2][0], cube[5][1][0], cube[5][0][0]
cube[5][0][0], cube[5][1][0], cube[5][2][0] = cube[2][2][2], cube[2][1][2], cube[2][0][2]
cube[2][0][2], cube[2][1][2], cube[2][2][2] = temp
moveDimension(cube,4)
[Idea 1: 반시계 방향은 시계 방향으로 3번 돌린 것과 같다.]를 적용한 함수이다.
def go(cube,comm):
direction, count = comm
count = 1 if count == '+' else 3
for _ in range(count): move(cube,direction)
최종 코드
n = int(input())
for _ in range(n):
m = int(input())
comm = list(input().split())
## cube 초기화
cube = [[] for _ in range(6)]
for _ in range(3):
cube[0].append(['r','r','r'])
cube[1].append(['y','y','y'])
cube[2].append(['w','w','w'])
cube[3].append(['g','g','g'])
cube[4].append(['b','b','b'])
cube[5].append(['o','o','o'])
while comm:
go(cube, comm.pop(0))
for i in range(3):
for j in range(3):
print(cube[2][i][j], end ='')
print()10. [프로그래머스: Lv2] : 빛의 경로 사이클(정답률: 16%)
[문제]
각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.
- 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
- 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
- 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
- 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.
예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.
이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.
격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.
[입출력 예]
| grid | result |
| ["SL","LR"] | [16] |
| ["S"] | [1,1,1,1] |
| ["R","R"] | [4,4] |
[코드]
def solution(grid):
m, n = len(grid), len(grid[0])
# 각 방향에 대한 이동 설정 (상, 우, 하, 좌)
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def move(x, y, d):
# 한 칸 이동
x = (x + directions[d][0]) % m
y = (y + directions[d][1]) % n
return x, y
def turn(c, d):
if c == 'L': # 좌회전
d = (d - 1) % 4
elif c == 'R': # 우회전
d = (d + 1) % 4
return d
visited = [[[False] * 4 for _ in range(n)] for _ in range(m)]
result = []
for i in range(m):
for j in range(n):
for d in range(4):
if not visited[i][j][d]:
count = 0
x, y, cur_d = i, j, d
while not visited[x][y][cur_d]:
visited[x][y][cur_d] = True
count += 1
cur_d = turn(grid[x][y], cur_d)
x, y = move(x, y, cur_d)
result.append(count)
return sorted(result)11. [프로그래머스 Lv2] 유사 칸토어 비트열(정답률: 21%)
[문제]
수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0, 1]부터 시작하여 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어집니다.
남아는 칸토어 집합을 조금 변형하여 유사 칸토어 비트열을 만들었습니다. 유사 칸토어 비트열은 다음과 같이 정의됩니다.
- 0 번째 유사 칸토어 비트열은 "1" 입니다.
- n(1 ≤ n) 번째 유사 칸토어 비트열은 n - 1 번째 유사 칸토어 비트열에서의 1을 11011로 치환하고 0을 00000로 치환하여 만듭니다.
남아는 n 번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.
n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해주세요.
[입출력 예]
| n | l | r | result |
| 2 | 4 | 17 | 8 |
[입출력 예 설명]
2 번째 유사 칸토어 비트열은 "1101111011000001101111011" 입니다. 음영 표시된 부분은 폐구간 [4, 17] 이며 구간 내의 1은 8개 있습니다.
[첫번째 코드]: 시간 초과 문제
def solution(n, l, r):
d = [""]*(n+1)
d[0] = "1"
d[1] = "11011"
if n>=2:
for i in range(2,n+1):
for v in range(0, len(d[i-1]), len(d[i-2])):
if d[i-1][v:v+len(d[i-2])]==d[i-2]:
d[i] += d[i-1]
else:
d[i] += "00000"*len(d[i-2])
answer = 0
for i in d[n][(l-1):r]:
answer += int(i)
return answer
[두번째 코드] -> ""재귀함수"" 사용
- 결국, 특정 구간 내에서 '1'의 개수를 계산하는 알고리즘을 사용하는 것이 중요
def solution(n,l,r):
def count_ones(n, l, r):
if n==0:
return 1
len_prev = 5 ** (n-1)
total_ones = 0
for i in range((l-1)//len_prev, r//len_prev + 1):
start = max(l, i*len_prev+1)
end = min(r, (i+1)*len_prev)
if i==2:
continue
elif i in {0,1,3,4}:
print()
total_ones += count_ones(n-1, start - i * len_prev, end - i*len_prev)
return total_ones
return count_ones(n,l,r)- n번째 비트열의 길이는 $n^2$
- n번재 비트열은 n-1번째 비트열로 만들어진다.
- n번째 비트열의 각 구간이 주어진 구간 [l,r]에 포함되는지 확인하고, 포함되는 구간만 재귀적으로 탐색
- 중간 구간(두번째 구간)은 항상 '0'으로만 이루어져 있으므로 이를 건너뜀.
12. [백준: 다이나믹 프그래밍(9095번)] 1, 2, 3 더하기(정답률: 64.573%)
[문제]
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
[출력]
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
[코드]
T = int(input())
answer = []
for i in range(T):
answer.append(int(input()))
d = [0]*13
d[1:4] = [1,2,4]
n = max(answer)
for i in range(4,n+1):
for j in range(1,4):
d[i] += d[i-j]
for n2 in answer:
print(d[n2])
13. [백준: 다이나믹 프로그래밍(1003번)] 피보나치 함수(정답률: 33.299%)
[문제]
다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return fibonacci(n‐1) + fibonacci(n‐2);
}
}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
- 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
- fibonacci(0)은 0을 출력하고, 0을 리턴한다.
- fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
- 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
[출력]
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
[코드]
T = int(input())
input_list = []
for i in range(T):
input_list.append(int(input()))
n = max(input_list)
d = [[0,0] for i in range(42)]
d[0] = [1,0]
d[1] = [0,1]
for i in range(2,n+1):
d[i][0] = d[i-1][0] + d[i-2][0]
d[i][1] = d[i-1][1] + d[i-2][1]
for j in input_list:
print(d[j][0], d[j][1])14. [백준: 다이나믹 프로그래밍(11726번)] 피보나치 함수(정답률: 36.682%)
[문제]
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
[출력]
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
[코드]
n = int(input())
d = [0]*1001
d[1]=1; d[2]=2
if n>=3:
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n]%10007)15. [백준: 그래프 이론(2606번)] 바이러스(정답률: 45.929%)
[문제]
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
[입력]
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
[출력]
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
[코드]: Breath First Search(BFS) 알고리즘 사용
from collections import deque
def viurs_bfs(graphs, start, visited):
que = deque([start])
visited[start]=True
while que:
v = que.popleft()
for i in graphs[v]:
if not visited[i]:
que.append(i)
visited[i]=True
return visited
n = int(input())
adj_list = []
m = int(input())
for i in range(m):
adj_list.append(list(map(int, input().split())))
L = [[] for i in range(n+1)]
for i,j in adj_list:
L[i] += [j]
L[j] += [i]
visit = viurs_bfs(L, 1, visited=[False]*(n+1))
print(sum(visit)-1)16. [백준: 그리디 알고리즘(11399번)] ATM(정답률: 68.779%)
[문제]
인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
[출력]
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
[코드]
n = int(input())
P = list(map(int, input().split()))
P.sort()
answer = 0
answer2 = []
for i in P:
answer += i
answer2.append(answer)
print(sum(answer2))17. [프로그래머스: Lv2] : 도넛과 막대 그프(정답률: 16%)
[문제]
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.
- 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.
- 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 같습니다.
- 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다. 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다. 8자 모양 그래프의 형태는 다음과 같습니다.
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.
그 후 각 정점에 서로 다른 번호를 매겼습니다.
이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.
그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
| edges | result |
| [[2, 3], [4, 3], [1, 1], [2, 1]] | [2, 1, 1, 0] |
| [[4, 11], [1, 12], [8, 3], [12, 7], [4, 2], [7, 11], [4, 8], [9, 6], [10, 11], [6, 10], [3, 5], [11, 1], [5, 3], [11, 9], [3, 8]] | [4, 0, 1, 2] |
[문제풀이]
- 막대 그래프는 나가는 간선이 없고 들어오는 간선만 1개 이상
- 8자 모양은 그래프는 나가는 간선이 2개, 들어오는 간선이 2개 이상
- 정점 노드는 들어오는 간선은 없고, 나가는 간선이 2개 이상인 경우
def solution(edges):
n = max([i for edge in edges for i in edge]) ## 가장 큰 수의 노드
degree = [[0,0] for _ in range(n+1)]
for i,j in edges:
degree[i][0] += 1
degree[j][1] += 1
bar = 0; eight = 0; move_vertex = 0
for i in range(1, n+1):
## 막대 그래프는 나가는 간선이 없고 들어오는 간선만 1개 이상
if degree[i][0]==0 and degree[i][1]>=1:
bar += 1
## 8자 모양 그래프는 나가는 간선이 2개, 들어오는 간선이 2개 이상
if degree[i][0]==2 and degree[i][1]>=2:
eight += 1
## 정점 노드는 들어오는 간선은 없고, 나가는 간선이 2개 이상인 경우
if degree[i][0] >= 2 and degree[i][1] == 0:
move_vertex = i
donut = degree[move_vertex][0] - bar - eight
return [move_vertex, donut, bar, eight]18. [백준: 다이나믹 프로그래밍(2775번)] 부녀회장이 될테야(정답률: 57.480%)
[문제]
평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.
이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.
아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.
[입력]
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다.
[출력]
각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.
[코드]
def teacher(k,n):
matrix = [[0 for i in range(n+1)] for j in range(k+1)]
matrix[0] = [i for i in range(n+1)]
for i in range(1,k+1):
for j in range(1, n+1):
matrix[i][j] = sum(matrix[i-1][:(j+1)])
return matrix[k][n]
T = int(input())
for _ in range(T):
k = int(input())
n = int(input())
print(teacher(k,n))
19. [백준: 다이나믹 프로그래밍(2779번)] 계단 오르기(정답률: 34.053%)
[문제]
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
[입력]
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
[출력]
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
[코드]
N = int(input())
stairs = []
for _ in range(N):
stairs.append(int(input()))
# 계단이 1개 또는 2개일 때 예외 처리
if N == 1:
print(stairs[0])
elif N == 2:
print(stairs[0] + stairs[1])
else:
# DP 테이블 초기화
d = [0] * N
d[0] = stairs[0]
d[1] = stairs[0] + stairs[1]
d[2] = max(stairs[1] + stairs[2], stairs[0] + stairs[2])
# DP 테이블 채우기
for i in range(3, N):
d[i] = max(d[i-2] + stairs[i], d[i-3] + stairs[i-1] + stairs[i])
# 마지막 계단에서의 최대 점수 출력
print(d[N-1])20. [백준: 다이나믹 프로그래밍(1149번)] RGB거리(정답률: 55.555
%)
[문제]
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
[입력]
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
[출력]
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
[코드]
N = int(input())
cost = []
for i in range(N):
cost.append(list(map(int, input().split())))
dp = [[0]*3 for _ in range(N)]
dp[0][0] = cost[0][0] ## 빨강
dp[0][1] = cost[0][1] ## 초록
dp[0][2] = cost[0][2] ## 파랑
for i in range(1,N):
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
answer = min(dp[N-1][0], dp[N-1][1], dp[N-1][2])
print(answer)[코드풀이]
- dp[i][0]: i번째 집을 빨강으로 칠하는 경우
- 이전 집을 초록 또는 파랑으로 칠한 경우의 최소 비용 중 더 작은 값(min(dp[i-1][1], dp[i-1][2]))에 현재 집을 빨강으로 칠하는 비용(cost[i][0])을 더한 값
- dp[i][1]: i번째 집을 초록으로 칠하는 경우
- 이전 집을 빨강 또는 파랑으로 칠한 경우의 최소 비용 중 더 작은 값(min(dp[i-1][0], dp[i-1][2]))에 현재 집을 초록으로 칠하는 비용(cost[i][1])을 더한 값
- dp[i][2]: i번째 집을 파랑으로 칠하는 경우
- 이전 집을 빨강 또는 초록으로 칠한 경우의 최소 비용 중 더 작은 값(min(dp[i-1][0], dp[i-1][1]))에 현재 집을 빨강으로 칠하는 비용(cost[i][2])을 더한 값
마지막 집까지 칠했을 때, 세 가지 색깔로 칠한 비용 중 가장 작은 값을 선택
21. [백준: 그래프 이론(1012번)] 유기농 배추(정답률: 38.395%)
[문제]
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
[입력]
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
[출력]
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
[코드 (1)] : 재귀함수 사용시 RecursionError 발생
- 재귀 호출의 깊이가 Python의 기본 재귀 한도 초과
- 배추밭의 크기가 50x50이고 배추의수가 최대 2500개까지 주어질 수 있기 때문에 깊은 재귀 호출 발생 가능.
def go(xx,yy):
## 특정한 조건을 만족하면
if [xx,yy] in matrix:
matrix.remove([xx,yy])
#### 4가지 방향에 대해서 모두 go ####
go(xx-1,yy)
go(xx+1,yy)
go(xx,yy-1)
go(xx,yy+1)
T = int(input())
for _ in range(T):
M,N,K = map(int, input().split())
matrix = []
for _ in range(K):
matrix.append(list(map(int, input().split())))
answer = 0
while matrix:
x,y = matrix[0]
go(x,y)
answer += 1
print(answer)
[코드 (2)]: 재귀함수 대신 stack 구조를 이용한 반복문 구조 구현(RecursionError 해결)
def go_stack(xx,yy,matrix,directions):
stack = [[xx,yy]]
while stack:
cx, cy = stack.pop()
if [cx,cy] in matrix:
matrix.remove([cx,cy])
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if [nx,ny] in matrix:
stack.append((nx,ny))
T = int(input())
for _ in range(T):
M,N,K = map(int, input().split())
matrix = []
for _ in range(K):
matrix.append(list(map(int, input().split())))
directions = [[-1,0],[1,0],[0,-1],[0,1]]
answer = 0
while matrix:
x, y = matrix[0]
go_stack(x, y, matrix, directions)
answer += 1
print(answer)22. [백준: 그리디 알고리즘(11047번)] 유기농 배추(정답률: 52.622%)
[문제]
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
[코드]
N,K = map(int, input().split())
number = []
for _ in range(N):
number.append(int(input()))
number = number[::-1]
answer = 0
for money in number:
a,b = divmod(K, money)
K = b
answer += a
print(answer)23. [프로그래머스: Lv2] 3 x n 타일링(정답률: 52.622%)
[문제]
가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
[입출력 예]
| n | result |
| 4 | 11 |
def solution(n):
MOD = 1000000007
# 홀수 값은 채울 방법이 존재하지 않음
if n % 2 != 0:
return 0
dp = [0] * (n + 1)
dp[0] = 1 # base case: 3x0 타일을 채우는 방법은 1가지 (아무것도 안 채우는 방법)
if n >= 2:
dp[2] = 3 # 3x2 타일을 채우는 방법은 3가지
if n >= 4:
# 점화식으로 dp 배열 채우기
for i in range(4, n + 1, 2):
dp[i] = dp[i - 2] * 3 % MOD
for j in range(0, i - 2, 2):
dp[i] = (dp[i] + dp[j] * 2) % MOD ## 2를 곱하는 이유는 대칭 반영
return dp[n]22. [백준: 다이나믹 프로그래밍(11053번)] 가장 긴 증가하는 부분 수열(정답률: 38.074%)
[문제]
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
[입력]
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
[출력]
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
[코드]
N = int(input())
number_set = list(map(int, input().split()))
dp = [1]*N
for i in range(1,N):
for j in range(i):
if number_set[i] > number_set[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))23. [백준: 다이나믹 프로그래밍] 정수 삼각형(정답률: 59.713%)
[문제]
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
[입력]
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
[출력]
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
[코드]
n = int(input())
matrix = []
for _ in range(n):
matrix.append(list(map(int, input().split())))
for i in range(n-1,0,-1):
for j in range(0,i):
matrix[i-1][j] += max(matrix[i][j], matrix[i][j+1])
print(matrix[0][0])
[코드풀이]
- 맨 밑에서부터 시작하여 matrix[i][j]와 matrix[i][j+1] 중 더 큰 값을 matrix[i-1][j]에 더해주는 알고리즘이다.
24. [백준: 그래프 이론] 단지번호붙이기(정답률: 42.703%)
[문제]
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
[입력]
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
[출력]
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
[코드]
N = int(input())
matrix = []
for _ in range(N):
matrix.append(list(map(int, input())))
matrix2 = []
for i in range(N):
for j in range(N):
if matrix[i][j]==1:
matrix2.append([i,j])
directions = [[-1,0],[1,0],[0,-1],[0,1]]
def go_stack(xx,yy,matrix,directions):
num = 0
stack = [[xx,yy]]
while stack:
cx, cy = stack.pop()
if [cx,cy] in matrix:
num += 1
matrix.remove([cx,cy])
for dx,dy in directions:
nx,ny = cx+dx, cy+dy
if [nx,ny] in matrix:
stack.append((nx,ny))
return num
answer = 0
number = []
while matrix2:
x, y = matrix2[0]
number.append(go_stack(x,y,matrix2,directions))
answer += 1
print(answer)
number.sort()
for n in number:
print(n)'Coding Study' 카테고리의 다른 글
| 최단 경로 알고리즘 (1) | 2024.06.06 |
|---|---|
| [##프로그래머스 & 백준 coding study ## : 2024.06] (1) | 2024.06.03 |
| Depth First Search(DFS) & Breath First Search(BFS) (0) | 2024.05.14 |
| [## 프로그래머스 coding study ##: 2024.04] (0) | 2024.04.01 |
| [## 프로그래머스 coding study ##: 2024.03] (0) | 2024.03.13 |
