Baekjoon

문제 링크 # https://www.acmicpc.net/problem/10026 문제 해설 # Idea # 모든 방문하지 않은 칸에 대해 BFS 탐색하면서 같은 구역을 방문 적록색약의 경우 R과 G를 같은 구역으로 판단하고 탐색 각각의 경우에 대한 BFS 호출 횟수를 서로 다른 구역의 수로 판단하여 출력 Time Complexity # BFS: …

문제 링크 # https://www.acmicpc.net/problem/21758 문제 해설 # Idea # 벌이 같은 방향을 향하는 경우 상자까지의 총합에서 두 벌의 시작 위치에 있는 값을 제외 벌이 다른 방향을 향하는 경우 상자까지의 총합에 절댓값을 취해서 더함 Data Size # N: 3 <= int <= 100,000 arr[i]: 1 …

문제 링크 # https://www.acmicpc.net/problem/5547 문제 해설 # Idea # 전체 좌표 평면의 외곽에 1만큼의 여백을 추가하고 x,y 좌표가 0부터 시작한다고 판단 y가 홀수 일 때, 인접한 좌표는 상하좌우와 함께 우상단,우하단을 포함 y가 짝수 일 때, 인접한 좌표는 상하좌우와 함께 좌상단, …

문제 링크 # https://www.acmicpc.net/problem/1308 문제 해설 # Idea # 각각의 날짜에 대한 문자열을 date 타입으로 변환하고, today 기준 1000년 후 날짜와 dday를 비교 조건이 맞을 경우 ‘gg’를 출력하고, 아니면 두 날짜의 차이를 출력 Data Size # y,m,d: 1,1,1 …

문제 링크 # https://www.acmicpc.net/problem/7569 문제 해설 # Idea # BFS 7569번 토마토 문제에서 하나의 차원이 추가된 버전입니다. 차원이 늘어난만큼 N의 최대 길이가 감소했기 때문에 여전히 BFS로 해결할 수 있습니다. 익은 토마토의 기준에서 전체 상자를 BFS로 완전탐색하면서 안익은 토마토까지의 최소 거리를 기 …

문제 링크 # https://www.acmicpc.net/problem/7576 문제 해설 # Idea # BFS를 활용한 시뮬레이션을 통해 모든 토마토가 익을 떄까지 걸리는 최소 기간을 계산 초기엔 안익은 토마토의 기준에서 매번 익은 토마토까지의 최단거리를 탐색하여, O(N^4)의 시간 복잡도로 시간 초과가 발생 이후 익은 토마토의 기준에서 시뮬레이션을 …

문제 링크 # https://www.acmicpc.net/problem/18870 문제 해설 # Idea # Sort 집합을 통해 압축한 unique한 좌표 목록을 정렬시키고, 정렬된 리스트 내에서 좌표와 인덱스를 딕셔너리로 맵핑 Time Complexity # O(N Log N) = 13,000,000 Data Size # N: 1 <= int …

문제 링크 # https://www.acmicpc.net/problem/1931 문제 해설 # Idea # Sliding Window 슬라이딩 윈도우의 전형적인 문제로, 끝 시간을 기준으로 시간을 정렬해서 겹치지 않는 수를 계산 Time Complexity # O(N) = 100,000 Data Size # N: 1 <= int <= …

문제 링크 # https://www.acmicpc.net/problem/15686 문제 해설 # Idea # Combinations 최대 집의 개수가 100, 최대 치킨집의 개수가 13으로 매우 적은 경우의 수를 가지고 있기 때문에, 모든 조합에 대한 완전탐색을 통해 최소 거리를 계산 초기에는 집에 대한 치킨 거리가 작은 치킨집을 우선적으로 선발해서, 폐업 …

문제 링크 # https://www.acmicpc.net/problem/1927 문제 해설 # Idea # Heapq 파이썬 heapq 모듈 자체가 최소힙이기 때문에 해당하는 기능을 활용하여 구현 Time Complexity # O(Log N) = 16 Data Size # N: 1 <= int <= 100,000 x: 0 <= int …