문제 링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 import heapq def dijkstra(i, j): global result q = [] heapq.heappush(q, (0, i, j)) visited[i][j] = 1 distance[i][j] = 0 while q: cnt, x, y = heapq.heappop(q) if x == n - 1 and y == m - 1: result = mi..
분류 전체보기
문제 링크 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 문제 풀이 문제를 따라가며 조건에 맞게 구현해나가면 어렵지 않게 풀 수 있습니다. 다소 비효율적으로 푼 것 같기도 하지만 주어진 숫자 범위가 매우 작아 시간적인 문제는 없었습니다. 저는 세 개의 함수로 나누어 풀이했습니다. 1) 모눈종이를 붙일 수 있는지 여부를 확인하는 함수 def check(r, c, sticker, start_x, start_y): for x in range(r): ..
문제 링크 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 문제 풀이 1) 4개 이상 연속된 뿌요들을 찾아 삭제하는 함수 2) 중력 작용으로 뿌요를 아래로 떨어뜨리는 함수 이렇게 두 가지 함수로 분리하여 작성했습니다. 1) 4개 이상 연속된 뿌요들을 찾아 삭제하는 함수 def burst(i, j, color): global flag q = deque() q.append([i, j]) visited[i][j] = 1 pu..
문제 링크 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 풀이 def dfs(n): if n in dict: return dict[n] else: dict[n] = dfs(n // p) + dfs(n // q) return dict[n] n, p, q = map(int, input().split()) dict = {} dict[0] = 1 print(dfs(n)) 딕셔너리를 활용하니 너무 간단하게 풀리는 문제였습니다. n이 딕셔너리 내에 키로 존재하지 않을 경우 재귀를 돌려 dict의 value를 채워나가며 key가 n인 value를 구하면 결과를 도출할 수 있습니다.
문제 링크 https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제 풀이 n = int(input()) flowers = [] for _ in range(n): start_m, start_d, end_m, end_d = map(int, input().split()) flowers.append([start_m * 100 + start_d, end_m * 100 + end_d]) flowers.sort() end_date = 301..
문제 링크 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 풀이 투 포인터 개념을 활용해야 하는 문제입니다. 해결의 핵심 포인트는 주어진 숫자 배열을 오름차순 정렬한 후, 왼쪽 기준점을 인덱스 1씩 늘려가며 고정하고 오른쪽에 있는 수들과의 차이를 확인하는 것입니다. 오른쪽 기준점은 고정된 왼쪽 기준점과 다르게 1씩 오른쪽으로 이동하며 왼쪽 기준점과의 차이를 확인하는데 사용됩니다. 만약 두 수의 차이가 주어진 m보다 작..
문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이 N, M이 각각 10만까지로 만약 범위를 입력받을 때마다 해당 구간에 대해 더하는 연산을 통해 답을 도출한다면 O(NM)의 시간복잡도로 시간초과가 나게됩니다. 매번 합을 도출하는 것이 아니라, 처음에 입력받은 리스트에 대해 누적합을 미리 저장해놓은 후, 만약 i부터 j 인덱스까지의 범위를 구하고 싶을 경우 [ j까지의 누적합 - (i - 1)까지의 누적..
문제 링크 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 적록색약인 사람과 아닌 사람을 flag로 구분하여 bfs 탐색 내에서 'R', 'G'를 구분할지 말지만 구현해주면 되는 쉬운 BFS 문제였습니다. from collections import deque def bfs(i, j, flag, visited): q = deque() q.append([i, j]) visited[i][j] = 1 color = graph[i][j..
