🔔문제 소개
🔗연습 요약
| 연습 시간 | 연습 문제 수 | 카테고리 |
|---|---|---|
| 120 분 | 6 문제 | 그리디, 다이나믹 프로그래밍, 완전 탐색, 그래프, 구현 중 랜덤 3 선택 |
🔗문제 요약
| 문제 | 번호 | 난이도 | 시간 내 풀이 여부 | 풀이 여부 |
|---|---|---|---|---|
| 파티가 좋아 파티가 좋아 | 4055 | G5 | X | 바로가기 |
| 출근 | 13903 | S1 | O | O |
| 치킨치킨치킨 | 16439 | S4 | O | O |
| 성냥 | 2029 | S4 | 바로가기 | |
| ACM-ICPC | 11946 | S4 | O | O |
| 재귀함수가 뭔가요? | 17478 | S5 | O | O |
📑풀이 노트
📌 출근
문제 요약
기본적인 미로탐색 문제, 그래프의 1인 부분만 밟고 (0, i)에서 (N, i) | 0 <= i <= N 까지 가는 최단경로를 구하는 문제
풀이 요약
| 풀이 순서 | 풀이 시간 | 시도횟수 | 카테고리 |
|---|---|---|---|
| 1 | H+65 | 3 | 그래프 이론 |
코드
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
q = deque()
for i, s in enumerate(graph[0]):
if s:
q.append([0, i])
visited[0][i] = 1
mv = [list(map(int, input().split())) for _ in range(int(input()))]
while q:
cx, cy = q.popleft()
for mx, my in mv:
nx, ny = cx + mx, cy + my
if 0 <= nx <n and 0 <= ny < m and visited[nx][ny] == 0 and graph[nx][ny]:
q.append([nx, ny])
visited[nx][ny] = visited[cx][cy] + 1
res = float('INF')
for i in visited[-1]:
if 0 < i < res:
res = i
print(res-1 if res != float('INF') else -1)회고
res의 최댓값을 대충 99999 로 정했다가 틀렸습니다가 나온 문제, 어렵진 않았는데 이런 사소한 실수때문에 한 10분 손해봄.
📌재귀 함수가 뭔가요?
문제 요약
재귀가 진행될 때마다 인덴트를 늘려가며 주어진 문자열을 출력해라.
풀이 요약
| 풀이 순서 | 풀이 시간 | 시도횟수 | 카테고리 |
|---|---|---|---|
| 2 | H+71 | 1 | 구현 |
코드
def recursive(m):
print("_" * (4 * (n - m)) + '"재귀함수가 뭔가요?"')
if not m:
print("_" * (4 * (n - m)) + '"재귀함수는 자기 자신을 호출하는 함수라네"')
print("_" * (4 * (n - m)) + "라고 답변하였지.")
return
print("_" * (4 * (n - m)) + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
print("_" * (4 * (n - m)) + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
print("_" * (4 * (n - m)) + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
recursive(m - 1)
print("_" * (4 * (n - m)) + "라고 답변하였지.")
n = int(input())
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
recursive(n)회고
재귀의 기저사례와 진입조건을 잘 따져 앞에 인덴트를 늘려가는 방식인데 한글이 vscode에서 안나오는 문제가 있었음. (테스트 불가.)
📌ACM-ICPC
문제 요약
ACM-ICPC에서 제출 로그가 주어졌을때 각 팀별 문제수와 시간을 순위에 따라 출력해라
풀이 요약
| 풀이 순서 | 풀이 시간 | 시도횟수 | 카테고리 |
|---|---|---|---|
| 3 | H+105 | 5 | 구현, 정렬 |
코드
team, problem,log_cnt = map(int, input().split())
score = [0]*(team+1)
solved = [[0]*(problem+1) for _ in range(team+1)]
wrong = [[0]*(problem+1) for _ in range(team+1)]
for log in range(log_cnt):
runtime, tnum, pnum, res = input().split()
if res == 'AC' and not solved[int(tnum)][int(pnum)]:
solved[int(tnum)][int(pnum)] = 1
score[int(tnum)] += wrong[int(tnum)][int(pnum)] * 20 + int(runtime)
else:
wrong[int(tnum)][int(pnum)] += 1
solved = [sum(s) for s in solved]
# 팀 번호, 푼 문제 수, # 총 시간
result = sorted(list(zip([i for i in range(1, team+1)], solved[1:], score[1:])),
key=lambda x:(-x[1], -x[2], x[0]))
# 문제를 많이 푼 순
# 문제 수가 같으면 총 시간이 작은순
# 둘다 같으면 팀 번호가 빠른 순
# 팀 번호, 푼 문제 수, 총 시간
for r in result:
print(*r)회고
의외로 구현에 애를 먹었던 문제, 3%에서 자꾸 틀렸습니다가 나와 아예 지워버리고 처음부터 구현을 다시했음. 조건이 많아 구현이 어려웠음.
📌치킨치킨치킨
문제 요약
치킨 종류가 주어지고, 그 중 3개만 선택할 때 회원들의 만족도 합이 가장 높은 것을 구해라.
회원들의 만족도는 치킨의 만족도 중 가장 큰 것을 선택한다.
풀이 요약
| 풀이 순서 | 풀이 시간 | 시도횟수 | 카테고리 |
|---|---|---|---|
| 4 | H+118 | 1 | 완전 탐색 |
코드
from itertools import combinations
member, kinda = map(int, input().split())
satis = [list(map(int, input().split())) for _ in range(member)]
mmax = 0
for comb in combinations(range(1, kinda+1), 3):
pmax = 0
for mem in range(member):
memb_max = 0
for idx in comb:
memb_max = max(memb_max, satis[mem][idx-1])
pmax += memb_max
mmax = max(pmax, mmax)
print(mmax)회고
문제를 잘못 이해해서 삽질한 문제
전체 회고
이번 테스트의 난이도는 크게 어려운 것은 없었는데 조급해 했던것이 문제였다. 특히 첫 번째 Gold V 문제를 1시간 동안 풀었는데 실패했던게 가장 큰 멘탈이 흔들렸던 문제였던 것 같다.
조금 더 많은 연습이 필요할 것 같다.
우선 이번 테스트를 끝내고 앞으로의 계획은 빠르게 최단거리 알고리즘을 마무리하고 심화 자료구조를 훑어본 뒤 복습 겸 하여 Gold 이상 난이도의 문제들로만 구성된 각각의 알고리즘 문제 풀이 연습을 진행할 예정이다.
PS린이