문제 링크 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..
문제 링크 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 풀이 def bfs(x, y): q = deque() q.append([x, y]) visited[x][y] = 1 while q: x, y = q.popleft() for dir in range(4): nx, ny = x + dx[dir], y + dy[dir] if 0 0 and not visited[i][j]: num += bfs(i, j) for i in range(n..
문제 링크 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 풀이 정답률이 낮은 이유가 있던 문제였습니다. 메모리와 시간의 압박이 쎘습니다,,ㅠㅠ 결국 이 문제의 핵심은 학생들 간 사이클을 파악하는 것입니다. 팀을 이룰 수 있는 경우는 두 가지입니다. 1) 본인이 본인을 선택하는 경우 2) 1 -> 2 -> 3 -> 1 이렇게 이어진 형태로 서로를 지목하는 경우 1번 학생부터 for문을 돌려서 확인했습니다. 지목한 사람을 타고타고 가다가 만약 이..
