본문 바로가기
728x90

PS91

[코드트리 챌린지] 4주차 - 그래프 탐색(BFS) ★ 핵심 : BFS(너비우선탐색) 1. collections의 deque() 활용하기 2. is_vaild() 함수 활용하기 → r, c 좌표 인덱스가 적절한지 판단 → board에 이동가능한 곳인지 판단 → in_queue[r][c]로 방문한 곳인지 판단 · 문제링크 https://www.codetree.ai/cote/13/problems/places-can-go?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai · 핵심 1. 출발점이 한 곳이 아니라 동시에 많은 경우 → 출발점 후보.. 2023. 10. 2.
[백준/BOJ] 1005번 - ACM Craft (Python) · 문제링크 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net · 핵심 : 위상 정렬 + DP · 코드(Python) # https://www.acmicpc.net/problem/1005 t = int(input()) for _ in range(t): N, K = map(int, input().split()) adj = [[] for _ in range(N + 1)] ind = [0 for _ in range(N + 1)] dp = [0 f.. 2023. 9. 30.
[코드트리 챌린지] 3주차 - 2차원 바람 · 문제링크 https://www.codetree.ai/cote/13/problems/The-2D-wind-blows?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai · 핵심 : 2차원 돌리기 1. 대상이 되는 2차원 좌표들의 집합 모으기 # 2차원 회전 - 좌표집합 밀기로 접근 def get_grids(r1, c1, r2, c2): qs = deque([]) for col in range(c1, c2 + 1): qs.append((r1, col)) for row in range(r1.. 2023. 9. 29.
[백준/BOJ] 2623번 - 음악프로그램 (Python) · 문제링크 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net · 핵심 : 위상 정렬 - 「 in-degree를 활용한 방법」 1. 방향성이 존재하는 그래프 생성 & 들어오는 간선 수 기록 → 3 1 4 3 → 3 : 가수의 수, 1 4 3 : 가수의 번호 → 1 - 4 / 4 - 3 으로 그래프 연결 2. in-degree = 0인 후보들 적절한 자료구조(리스크, 큐, 스택, 힙 등)에 넣기 3. candiates가 전부 비.. 2023. 9. 29.
[백준/BOJ] 1347번 - 미로 만들기 (Python, Java) · 문제링크 https://www.acmicpc.net/problem/1347 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net · 핵심 1. 시작점이 설정되어있지 않다. → 명령어의 최대 길이는 50이므로 넉넉하게 아주 큰 board를 생성하고 적절한 시작점을 임의로 설정한다. → max_n = 200, cr = max_n // 2 , cc = max_n // 2 2. 큰 board에서 이동한 영역을 추출하기 → 도착을 1로 표시 → 사각형을 추출하기 위해서 1이 존재하는 (행, 열)들 중에서 min_r, .. 2023. 9. 25.
[백준/BOJ] 2252번 - 줄 세우기 (Python, Java) · 문제링크 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net · 핵심 : 위상 정렬 - 「 in-degree를 활용한 방법」 1. 방향성이 존재하는 그래프 생성( 무방향성 그래프, 사이클 있는 그래프의 경우 위상정렬이 쉽지 않음) → adj 그래프 생성 ☆ 2. 들어오는 간선의 수 기록 → 위상정렬에서는 in-degree = 0인 후보군(candiates)을 문제 조건에 부합한 특정 자료 구조(리스트,.. 2023. 9. 25.
728x90
반응형

티스토리툴바