목록Algorithm (178)
우노
문제 링크 https://www.acmicpc.net/problem/15961 풀이 슬라이딩 윈도우 알고리즘과 딕셔너리를 사용해서 해결할 수 있습니다. 윈도우의 크기를 k로 설정한 뒤, 윈도우를 오른쪽으로 한 칸씩 이동하며, 구간 내에 존재하는 접시의 종류별 개수를 파악하면 됩니다. 참고 회전 초밥 벨트는 원형으로 이루어져있기 때문에, 오른쪽 인덱스는 오른쪽 인덱스를 접시의 수로 나눈 나머지를 사용하면 됩니다. 구간 내에는 항상 쿠폰 번호가 포함되어 있다고 가정합니다. 코드 import sys from collections import defaultdict # n : 회전 초밥 벨트에 놓인 접시의 수 # d : 초밥의 가짓수 # k : 연속해서 먹는 접시의 수 # c : 쿠폰 번호 n, d, k, c =..
문제 링크 https://www.acmicpc.net/problem/2531 풀이 슬라이딩 윈도우 알고리즘과 딕셔너리를 사용해서 해결할 수 있습니다. 윈도우의 크기를 k로 설정한 뒤, 윈도우를 오른쪽으로 한 칸씩 이동하며, 구간 내에 존재하는 접시의 종류별 개수를 파악하면 됩니다. 참고 회전 초밥 벨트는 원형으로 이루어져있기 때문에, 오른쪽 인덱스는 오른쪽 인덱스를 접시의 수로 나눈 나머지를 사용하면 됩니다. 구간 내에는 항상 쿠폰 번호가 포함되어 있다고 가정합니다. 코드 import sys from collections import defaultdict # n : 회전 초밥 벨트에 놓인 접시의 수 # d : 초밥의 가짓수 # k : 연속해서 먹는 접시의 수 # c : 쿠폰 번호 n, d, k, c = ..
문제 링크 https://www.acmicpc.net/problem/1351 풀이 해당 문제는 DP 또는 Hash로 해결할 수 있습니다. 해당 포스트에선 Hash를 사용한 해결 방법을 다루고 있으며, n번째 값을 딕셔너리에 저장하는 재귀 함수를 통해 해결할 수 있습니다. 코드 import sys n, p, q = map(int, sys.stdin.readline().split()) # 딕셔너리 선언 dict = {} dict[0] = 1 def solution(n): # n번째 값이 저장되어있다면, 그대로 반환 if (n in dict): return dict[n] # n번째 값이 저장되어있지 않다면, n번째 값을 계산 및 저장한 뒤, 반환 else: dict[n] = solution(n//p) + so..
문제 링크 https://www.acmicpc.net/problem/9375 풀이 참고 의상을 한 개만 걸치고 있어도 알몸이 아닙니다. 같은 종류의 의상은 하나만 입을 수 있습니다. 주어진 의상으로 만들 수 있는 조합의 개수가 정답이 됩니다. 따라서, 주어진 의상에 대한 조합의 개수는 아래와 같이 계산할 수 있습니다. ( a 의상의 종류 수 + 1 ) * ( b 의상의 종류 수 + 1 ) * ( c 의상의 종류 수 + 1 ) … -1 각 의상의 종류 수에 +1을 해준 이유는, 해당 의상을 착용하지 않는 경우도 포함하기 위함입니다. 마지막에 -1을 해준 이유는, 모든 의상을 착용하지 않은 경우는 제외하기 위함입니다. 코드 import sys t = int(sys.stdin.readline()) for _ ..
문제 링크 https://www.acmicpc.net/problem/13414 풀이 중복 신청된 학번은 뒤로 밀린다는 것을 고려해, 수강신청이 들어온 순서대로, 학번과 순서를 딕셔너리에 Key, Value 형식으로 저장합니다. 해당 방식을 통해, 중복 신청된 학번의 순서는 자연스럽게 커지게 됩니다. 이후, 순서를 기준으로 오름차순 정렬한 뒤, 학번을 제한 인원만큼 출력하면 됩니다. 추가적으로, 제한 인원보다 신청 인원이 적을 경우에는, 제한 인원을 신청 인원과 동일하게 수정합니다. 코드 import sys k, l = map(int, sys.stdin.readline().split()) # 수강신청이 들어온 순서대로 학번과 순서를 딕셔너리에 Key, Value로 저장 dict = {} for i in r..
문제 링크 https://www.acmicpc.net/problem/2003 풀이 투 포인터 알고리즘을 사용해 해결할 수 있습니다. 구간의 시작 idx와 끝 idx를 0과 1로 초기화합니다. 구간의 합을 계산합니다. 구간의 합이 목푯값보다 작다면, 끝 idx를 오른쪽으로 한 칸 이동합니다. 구간의 합이 목푯값보다 크다면, 시작 idx를 오른쪽으로 한 칸 이동합니다. 구간의 합이 목푯값과 같다면, 경우의 수를 증가시키고, 끝 idx를 오른쪽으로 한 칸 이동합니다. 참고로, 1개의 수가 m이 되는 경우도 생각해야합니다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split..
문제 링크 https://www.acmicpc.net/problem/10025 풀이 슬라이딩 윈도우 알고리즘을 활용하여 해결할 수 있습니다. 양동이의 좌표별 얼음 양은 1차원 배열에 저장합니다. 1차원 배열의 크기는 최대 크기인 1000001로 생성합니다. 윈도우의 범위는 (2 * k) + 1 로 설정합니다. 특정 위치에서 앞뒤로 k 만큼의 범위를 포함하기 때문입니다. 반복문을 돌며 윈도우 범위 내의 얼음의 양을 계산하고, 최댓값을 비교해나갑니다. 윈도우를 한 칸씩 이동하며, 윈도우의 맨 앞에 있었던 값은 윈도우의 합에서 빼고 윈도우의 맨 뒤에 추가되는 값은 윈도우의 합에 더해줍니다. 코드 import sys n, k = map(int, sys.stdin.readline().split(" ")) # 양동..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 풀이 대표적인 경로 찾기 알고리즘입니다. 2차원 DP 테이블을 생성한 뒤, 시작 위치는 1로, 웅덩이의 위치는 -1로 변환합니다. 이후, DP 테이블의 칸들을 순서대로 탐색해 나갑니다. 현재 칸이 웅덩이(-1)일 경우엔, 0으로 변환합니다. 현재 칸이 웅덩이가 아닐 경우엔, 왼쪽 칸과 위쪽 칸의 합으로 변환합니다. 세부 알고리즘은 아래 코드와 같습니다. 코드 def solution(m, n, puddles): # 2차원 DP 테이블 초기화 dp = [[0] * (m+1) for _ in range(n+1)] # 시작 위치는 1로 처리 dp[1][1] = 1 # 웅덩이는 -1로 처리..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42884 풀이 차량의 이동 경로를 진출 시간을 기준으로 오름차순 정렬한 뒤, 모든 차량의 이동 경로를 순서대로 탐색하며, 현재 설치된 카메라의 위치보다 다음 차량의 진입 지점이 클 경우, 카메라를 새롭게 설치합니다. 세부 알고리즘은 아래 코드와 같습니다. 코드 def solution(routes): # 진출 시간을 기준으로 오름차순 정렬 routes.sort(key = lambda x:x[1]) # 카메라 설치 위치 초기화 camera = -int(1e9) # 카메라 설치 개수 count = 0 # 차량의 이동 경로 탐색 for route in routes: # 현재 설치된 카메라의 위치보..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42885 풀이 투 포인터 알고리즘을 사용해 해결할 수 있습니다. 구명보트에 태울 수 있는 사람은 최대 2명입니다. 따라서, 사람들의 몸무게를 오름차순 정렬한 뒤, 두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나 한 명(몸무게가 가장 많은 사람)을 태웁니다. 코드 def solution(people, limit): # 몸무게를 오름차순 정렬 people.sort() # 시작, 끝 인덱스 start, end = 0, len(people)-1 # 보트의 수 count = 0 while start