Gold Random Defense
💻230603~230609 (골5)
1. 마법사 상어와 비바라기(골5)
21610
처음 구름 위치는 [N-1, 0], [N-1, 1], [N-2, 0], [N-2, 1]
cloud_move 함수
양 끝이 이어지기 때문에 % 연산자 사용
ex) -3 % 5 = 2
d와 s로 구름 움직임, 물의 양 +1, visited = 1
water_add 함수
대각선을 하나씩 보면서 범위 안에 있는 곳에 물이 있으면 +1
cloud_new 함수
cloud 리스트 초기화 후 새로운 구름 생성
직전에 구름이 없던 곳이고, 물의 양이 2 이상인 곳에 생성
💻230610~230616 (골5~골3)
1. 빗물(골5)
14719
그림처럼 배열 만들기
벽 만나면 그동안 모았던 빗물을 결괏값에 더해주기
빈 곳인데 벽을 지났으면 빗물 증가
2. A와 B(골5)
12904
T에서 하나씩 빼서 S로 만들기
마지막 문자가 'A'일 때는 그냥 pop
마지막 문자가 'B'일 때는 pop한 후 reverse
3. 아기 상어(골3)
16236
문제
1. 아기 상어의 처음 크기는 2
2. 자신보다 큰 물고기가 있는 곳은 지나갈 수 없음
3. 자신보다 작은 물고기만 먹을 수 있음
4. 우선순위: 가까움 > 왼쪽 > 위쪽
5. 자신의 크기만큼 먹으면 1증가
풀이
2. visited 배열에서 지나갈 수 있는 곳만 0으로 바꾸기
3. arr[nx][ny] != 9 이 조건 없으면 상어 크기가 9보다 커졌을 때 무한 루프 돌음
4. 힙은 제일 작은 값이 앞으로 옴 (거리, 행, 열)로 heappush하면 우선순위대로 정렬이 됨
5. 크기가 증가하면 먹은 물고기 개수 초기화 해줌
💻230617~230623 (골5~골3)
1. 줄서기(골5)
17178
※주의: 문자열 비교일 때는 123 < 4가 된다
천 미만의 자연수이므로 zfill(3)으로 앞에 0을 채워줌, 문자열 일 때 123 > 004가 됨
💻230722~230728 (골5~골4)
1. 운동(골4)
1956
플로이드 워셜
- 모든 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있음
과정
1. 인접행렬 만들기(대각선은 0, 길이 없으면 INF)
2. i는 각 라운드별 중간노드
3. j, k로 인접행렬 살펴보면서 i를 중간노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 업데이트
2. 배열 돌리기 4(골4)
17406
백트래킹+시뮬레이션
1. dfs로 백트래킹을 돌림
2. 한 칸씩 돌리는데 이때 제일 왼쪽위의 값을 저장해두고 왼→아래→오→위 순으로 돌린 후 tmp값을 한칸 오른쪽에 넣어줌
3. 제일 작은 값 출력
3. 게리맨더링(골4)
17471
완전 탐색+bfs
c1: 조합으로 구한 배열
c2: arr에서 c1에 속하지 않은 나머지
c1과 c2를 둘다 bfs 돌린 후 모든 곳을 방문하였다면 answer 후보
4. 별 찍기 - 10(골5)
2447
재귀
모두 '*'로 채워놓고, 27이면 9~17을, 9면 3~5를 ' '로 바꾸기
💻230729~230804 (골4~골3)
1. 네트워크 연결(골4)
1922
최소 스패닝 트리+유니온 파인드
- 프림 알고리즘
1) 임의의 정점을 시작 정점으로
2) 최소 신장 트리의 루트 노드로 삽입
3) 삽입된 정점과 인접한 정점의 가중치 비교
- 크루스칼 알고리즘(아래 코드)
1) 가중치의 오름차순 정렬
2) 사이클 간선 제외
3) MST 집합에 추가
※ for문 마지막에 print(parent, result) 넣었을 때 출력 결과
[0, 1, 2, 2, 4, 5, 6] 2
[0, 1, 2, 2, 4, 4, 6] 5
[0, 1, 1, 2, 4, 4, 6] 9
[0, 1, 1, 2, 4, 4, 6] 9
[0, 1, 1, 1, 1, 4, 6] 15
[0, 1, 1, 1, 1, 4, 6] 15
[0, 1, 1, 1, 1, 4, 1] 23
[0, 1, 1, 1, 1, 1, 1] 23
[0, 1, 1, 1, 1, 1, 1] 23
[0, 1, 1, 1, 1, 1, 1] 23
2. 경사로(골3)
14890
구현
1. 한 번의 for문에서 가로 한번, 세로 한번 돌리기
2. 높이(r)가 1보다 크면 False
3. 높이(r)가 1일때
3-1. 앞에가 낮을 때, 경사로 놓을 자리가 없거나 이미 경사로가 놓여져 있는 곳이면 False, 아니면 경사로 놓기(visited 함수 바꿔줌)
3-2. 뒤에가 낮을 때, 3-1과 동일
4. True인 경우만 다 더하기
3. 타일 채우기(골4)
2133
4. 거짓말(골4)
1043
DFS
1. [1, 2, 3, 4]면 graph[1]에 2, 3, 4를 넣고 graph[2]에 1, 3, 4를 넣는 식으로 graph를 만듦
2. 진실을 아는 사람을 모두 dfs 돌림
3. 모든 파티에서 진실을 아는 사람이 한 명이라도 있으면 결괏값 차감
💻230805~230811 (골5~골3)
1. 녹색 옷 입은 애가 젤다지?(골4)
4485
다익스트라
- 순차 탐색: 거리 테이블을 매번 탐색하는 방식
- 우선순위 큐: 거리가 짧은 노드를 우선 탐색(아래 코드)
1. 갈 수 있는 곳을 힙에 (비용, 행, 열)로 넣는다. → 비용이 작은 순대로 정렬됨
2. 그렇게 작은 곳만 방문하다가 도착 지점에 도착하면 종료
2. 치즈(골3)
2638
BFS
1. 외부 공기 2로 만드는 방법: 상하좌우만 움직일 수 있게 한 후 0이면 2로 바꿈 → 대각선은 방문할 수 없으니 외부 공기일 때 내부 공기를 방문할 수 없음
2. 치즈 없애는 방법: 1일 때 외부공기와 맞닿는 부분이 2군데 이상이면 없애기
3. 마법사 상어와 파이어볼(골4)
20056
구현
ball(큐): 답을 구할 때 사용, (r, c, m, s, d) 삽입
arr(이차원 큐): 위치를 알 때 사용, arr[r][c]에 (m, s, d) 삽입
0. ball이라는 큐에 모든 파이어볼을 삽입
1. ball에 있는 모든 파이어볼을 꺼낸 후에 이동 시킴 → 1번과 N번이 연결되어있으므로 모듈 연산자로 구하기 → 위치를 알기위해 arr에 삽입
2. arr에서 파이어 볼이 두 개 이상인 곳에서 파이어볼 나눠짐 → 나눠진 파이어볼은 또 ball에 삽입됨, 안 나눠진 파이어볼도 ball에 삽입(arr에선 제거)
3. ball 큐의 m들을 합산한 값 출력
※ 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다. → ball에 있는 파이어볼을 이동시키는 건 다음 for문을 돌 때임
4. 감시 피하기(골5)
18428
조합&구현
1. 3개의 위치를 골라서 장애물 설치
2. 선생님을 만나면 False, 아니면 True
💻230819~230825 (골4~골3)
1. 구슬 찾기(골4)
2617
DFS
graph1은 나보다 무거운 구슬 넣는 그래프
graph2는 나보다 가벼운 구슬 넣는 그래프
cnt가 절반보다 많으면 중간 구슬이 될 수 없음
2. DFS 스페셜 저지(골3)
16964
DFS
원래 dfs는 탐색할 때 가장 작은 수부터 탐색
이 문제는 order 순으로 방문해야함
order 마지막까지 방문이 가능하다면 1 출력, 그 전에 return되면 0 출력
3. 최소 스패닝 트리(골4)
1197
최소 스패닝 트리, 유니온 파인드
1. 가중치 작은 순으로 힙에 넣기
2. 사이클을 형성하지 않는 간선만 넣기
4. 카드 정렬하기(골4)
1715
힙
힙 사용해서 가장 앞에 있는 것 두 개 더하기
💻230826~230901 (골4~골2)
1. 가운데를 말해요(골2)
1655
힙
maxheap: 최대힙(중간 값보다 작은 수 저장)
minheap: 최소힙(중간 값보다 큰 수 저장)
'maxheap 개수 >= minheap 개수'를 항상 만족하기
maxheap의 첫번째 값이 중간수
2. 파일 합치기(골3)
11066
DP
[크누스 최적화]
첫 번째 for문 이후(초기 세팅)
0 70 100 150
0 0 60 110
0 0 0 80
0 0 0 0
두 번째 for문 이후
0 70 160 300
0 0 60 170
0 0 0 80
0 0 0 0
3. 플로이드(골4)
11404
플로이드 워셜
바로 가는 것 vs k를 거쳐가는 것
4. RGB거리 2(골4)
17404
DP
처음과 마지막 꺼도 달라야 하므로
i와 j가 다를 떄만 계산해준다
💻230902~230908 (골5~골4)
1. 맥주 마시면서 걸어가기(골5)
9205
BFS
그래프 만드는 부분에서 맨해튼 거리가 1000이하면 두 지점을 연결해준다
2. 숫자고르기(골5)
2668
DFS
1 → 3으로 생각했을 때 dfs(1)을 하면 1이 visited 처리 되는게 아니라 3만 visited 처리를 한다
dfs가 끝났을 때 1도 방문처리가 되어있다면 사이클을 돌았다고 간주
※ set이 sort가 되는 줄 알았는데 안 됨! → sort 해주기
3. 줄세우기(골4)
2631
DP, LIS
현재 값의 이전 값들을 돌면서 본인보다 작은게 있으면 dp값 갱신
4. 주사위 굴리기(골4)
14499
구현
1. 위치가 벗어나면 명령어를 수행하지 않아야 하기 때문에 다시 원래 위치로 돌려 놓는다(19, 20번째 줄)
2. 주사위 상태는 dir를 활용하여 바꾼다
dir 배열이 뭘까?
[[동쪽으로 이동했을 때], [서], [북], [남]]
dice 값을 [1, 2, 3, 4, 5, 6] → [4, 2, 1, 6, 5, 3] 인덱스로 바꾸면 된다는 뜻(dice[1] = dice[4])
댓글남기기