def dfs(v):
done.append(v) # 방문한 노드 추가
# print(done)
# 해당 행(노드) 탐색(1행 ~ n행)
for i in range(1, n+1):
if (i not in done) and (matrix[v][i] == 1):
dfs(i)
return done
def bfs(start):
queue = [start]
done = [start]
while queue:
v = queue.pop(0)
for i in range(1, n+1):
if (i not in done) and (matrix[v][i] == 1):
queue.append(i)
done.append(i)
return done
n, m, v = map(int, input().split())
done = []
matrix = [[0]*(n + 1) for _ in range(n + 1)]
for _ in range(m):
x, y = map(int, input().split())
matrix[x][y] = 1
matrix[y][x] = 1
print(*dfs(v))
print(*bfs(v))
그래프를 표현하기 위해 여기서는 '인접 행렬' 방식으로 구현했다. DFS(깊이 우선 탐색)은 주로 스택과 재귀를 통해 구현하고 BFS(너비 우선 탐색)은 큐로 구현을 많이 한다.
N = int(input())
H = list(map(int, input().split()))
result = [0] * N
for i in range(N):
cnt_zero = 0
for j in range(N):
if cnt_zero == H[i] and result[j] == 0:
result[j] = i + 1 # 수 1 ~ N
break
elif(result[j] == 0):
cnt_zero += 1
print(*result)
입력 값으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. 그리고 줄을 선 순서대로 키를 출력하면 된다.
차례대로 각자 왼쪽에 큰 사람이 몇 명인지를 0의 개수로 판단해서 자리에 넣어준다. 예를 들어 왼쪽에 2명이 있다 하면 결과값 배열에 [0, 0, 현재,...] 즉, 자신보다 큰 2명의 자리를 비워두고 자리에 들어가면 된다. 그렇게 되면 다음 사람은 앞전보다 큰 사람이기 때문에 앞사람 위치는 무시하고 자신보다 큰 사람 수와 0의 수만 같으면 그 자리에 들어가면 된다.
N = int(input())
weights = [int(input()) for _ in range(N)]
weights.sort(reverse=True) # 내림차순
for i in range(N):
weights[i] = weights[i] * (i+1)
print(max(weights))
문제 접근 방법
- 로프를 병렬로 연결하면 각 로프에는 w/k만큼의 동일한 중량이 걸린다.
- 즉,가장 작은 무게를 들 수 있는 로프가 들 수 있는 질량 * 병렬연결 로프 개수= 최종 무게
- 가장 무거운 무게를 들 수 있는 로프부터 내림차순으로 정렬한다.
처음에는 너무 어렵게 접근해서 복잡하게 생각했다. 그래서 디큐를 활용해 하나씩 빼고 넣고 하려고 했다가 실패했다. 이렇게 단순하게 풀릴지는... 후..
T = int(input())
A, B, C = 0, 0, 0
while T > 0:
if T >= 300:
A = (T // 300)
T = (T % 300)
if (T >= 60) and (T < 300):
B = (T // 60)
T = (T % 60)
if (T < 60):
C = (T // 10)
if (T % 10) == 0:
print("{} {} {}".format(A, B, C))
break
else:
print(-1)
break
특별히 어려운 조건이 없는 문제였다. 최소한의 버튼 클릭 수를 구하기 위해 입력값을 큰 값으로 최대한 나누면 된다. 입력 값이 단위별로 나눌 수 있는 값인지 판단 후 계산을 하고 몫을 출력해주면 된다. 마지막에 10초로 나눴을 때 나머지가 0이 아니면 -1을 출력한다.
def recruit(num, score):
min_interview = score[0][1] # 첫번째 지원자 면접 등수
cnt = 1 # 첫 번째 지원자는 서류점수가 1등이기에 무조건 뽑힘
for i in range(1, num): # 1번 ~ n-1번
if score[i][1] < min_interview: # 뽑히는 경우
min_interview = score[i][1] # 더 높은 등수로 변경
cnt += 1
return cnt
tests = int(input())
for _ in range(tests):
num = int(input())
score = [list(map(int, input().split())) for _ in range(num)]
score.sort(key=lambda x: x[0]) # 서류 시험 등수 오름차순
print(recruit(num, score))
Python3로 제출하면 시간 초과가 나고, pypy로 제출하니 통과가 됐다. for문을 최대로 줄이려고 해 봤지만 다른 방법을 찾기가 쉽지 않았다.
문제 조건
- 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발.
- 즉, 현재 지원자의 서류 성적보다 더 높은 서류 성적을 가진 사람들보다 면접 성적이 높아야 선발된다.
따라서 우선 성적을 '서류 성적순'으로 정렬시킨다. 그리고 가장 높은 서류 성적을 가진 사람은 면접이 낮더라도 무조건 선발된다. 그래서 첫 번째 지원자의 면접 성적을 min_interview에 담고 그 값을 다음 사람들과 비교해나간다.
더 낮은(즉, 더 좋은 면접 성적) 성적을 가진 사람이 있으면 min_interview에 담는다. 그렇게 되면 특정 지원자의 면접시험 성적과 min_interview만 비교해 특정 지원자의 선발 여부를 결정할 수 있게 된다. 왜냐하면 이미 서류 성적순으로 정렬이 됐기에 지나온 지원자들보다 면접 성적만 낮지 않으면 되기 때문이다.
sugar = int(input())
result = 0
while sugar != 0:
if sugar < 0:
result = -1
break
if (sugar % 5) == 0:
result += (sugar // 5)
sugar = 0
else:
sugar -= 3
result += 1
print(result)
일단 설탕의 무게가 큰 단위인 5로 나눠지면 몫을 result에 담고 설탕 무게를 0으로 만든다. 만약 5로 나눠지지 않는다면 설탕에서 -3을 해주고 result를 1증가시킨다. 그러다 설탕이 0보다 작아지는 경우에는 5, 3으로 나눌 수 없는 값이기 때문에 -1을 출력하고 반복문을 종료한다.
