기업에 따라 라이브러리 사용에 제한이 있기 때문에, Python의 장점 중 하나인 itertools 사용할 수 없는 경우가 생기게 됩니다. 그렇기 때문에 코딩테스트를 앞두고 관련 알고리즘을 직접 구현하며 정리하는 시간을 가져보았습니다. 하나의 템플릿처럼 제가 자주 사용하는 형태로, 모든 구현에 재귀를 사용합니다. 이유는 처음 관련된 내용을 학습했을 때, 반복문보다 흐름이 더 직관적이었기 때문입니다.[조합]def c(idx, target, result): # 리스트의 현재 인덱스, 선택된 수의 개수, 만들어지 조합 if target == n: print(result) return if idx == len(arr): # 숫자들이 다 선택되지 않은 상태에서 다음 숫자를 ..
Python
[문제]https://www.acmicpc.net/problem/2638시뮬레이션이 포함된 그래프 탐색 문제입니다. 주요 전략은 치즈의 외부와 내부 공간을 분리하여, 치즈의 외부를 지속적으로 탐색하는 것입니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] self.answer = 0탐색은 BFS, DFS 둘 다 가능하지만, BFS가 더 빠른 속도를 보장할 수 ..
[문제]https://www.acmicpc.net/problem/5840문제의 등급보다는 다소 생각을 해야 풀 수 있는 문제입니다. 문제를 요약하자면 ID가 부여된 소들 중, 동일한 ID를 가진 소들의 거리가 K 이하인 그룹 중에서 가장 큰 ID를 가진 그룹을 찾는 문제입니다. 단순하게 생각하면 n^2으로 문제를 풀어낼 수 있을 거 같지만, 소들의 수인 N의 최대는 50,000이고 시간 제한은 1초이므로 그렇게 풀어낼 수는 없습니다. 그렇기 때문에 문제를 선형 시간으로 풀어내는 방법으로 접근해야 합니다.[초기화] def __init__(self): self.n, self.k = map(int, input().split()) self.cows = [int(input()) fo..
[문제]https://www.acmicpc.net/problem/21610어려울 거 없는 구현 및 시뮬레이션 문제입니다. 문제에서 제시한 대로 순서대로 코드를 작성하면 되겠습니다. 구현 시 주의할 점은 주어진 격자의 양 끝이 연결되어 있는 구조라는 것입니다. 즉 0열에서 왼쪽으로 이동하면 n-1열로 이동할 수 있고 이는 반대의 경우도 가능하며 행에도 적용됩니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.move_info = [tuple(map(int, ..
[문제]https://www.acmicpc.net/problem/26086지문을 읽었을 때, 크게 어렵게 느껴지는 문제는 아니지만 최적화를 수행해야 한다는 점, 개인적으로 지문을 제대로 파악하지 못했던 점에서 다소 어려움이 있었던 문제입니다. 해당 문제의 관건은 요구사항대로 그대로 구현하되, 불필요한 연산을 수행하지 않음으로써 성능을 보장하는 것입니다.[초기화] def __init__(self): self.n, self.q, self.k = map(int, input().split()) self.cmd = [tuple(map(int, input().split())) for _ in range(self.q)][풀이] def solve(self): last_o..
[문제]https://www.acmicpc.net/problem/2812주어진 숫자에서 순서는 유지한 채, k개의 수를 제거해 큰 수를 만들어내는 문제입니다. 즉 숫자들을 재조합하는 문제가 아니라는 것입니다. https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스의 해당 문제와 동일한 문제입니다. 숫자를 순서대로 순회 및 스택에 저장해, 스택의 숫자를 순간마다 가장 큰 수로 유지하면 해결 가능한 문제입니다. 출력 방식에 따라 소요 시간이 약 ..
[문제]https://www.acmicpc.net/problem/17404 RGB 거리와 동일한 문제입니다. 다만 제약 조건으로 1번 집의 색과 n번 집의 색상이 서로 달라야 한다는 조건이 추가되었습니다. 해당 문제의 기본 규칙은 서로 인접한 집의 색상이 서로 달라야 한다는 것입니다. 기존 RGB 거리에서의 풀이는 현재 주어진 색상으로 칠한다고 가정했을 때, 바로 직전의 집들 중 해당 색상을 제외한 비용 중, 최소를 선택해서 갱신하면 되는 것이었습니다. 하지만 첫 번째 집과 마지막 집의 색상이 서로 달라야 하므로 처음 색상을 고정하는 추가적인 절차가 필요합니다. 해당 과정은 풀이에서 상세하게 다루겠습니다.[초기화] def __init__(self): self.n = int(input()..
[문제]https://www.acmicpc.net/problem/2887 주어진 노드(행성)를 최소 비용으로 모두 연결한다는 점에서 최소 신장 트리 유형의 문제라는 것을 알 수 있었습니다. 문제는 순수하게 최소 신장 트리를 구현하면 되지만, 난이도가 난이도인만큼 최적화를 수행해야 풀 수 있는 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.cord = [list(map(int, input().split())) for _ in range(self.n)] self.parents = [i for i in range(self.n)] self.answer = 0[풀이]class Node: def ..
[문제]https://www.acmicpc.net/problem/28707 언뜻 보면 정렬 유형의 문제처럼 보이지만, 조작으로 주어지는 입력과 최솟값을 구한다는 점에서 데이크스트라(Dijkstra) 문제인 것을 알 수 있었습니다. 𝑙 𝑖번 째 노드에서 𝑟𝑖 번 째 노드로 이동하는데, 비용 𝑐𝑖가 소요된다고 받아들였습니다. 다만 기존의 문제와 다른 점은 배열 자체가 값이 된다는 것입니다. 이 점을 유의하며 문제를 풀어야 합니다.[초기화] def __init__(self): self.n = int(input()) self.arr = list(map(int, input().split())) self.m = int(input()) self.o..
[문제]https://www.acmicpc.net/problem/2239주어진 스도쿠 보드를 기준으로 완성시키는 문제입니다. 간단하게 생각하면 주어진 행, 열과 3x3 공간을 전부 탐색 후, 가능한 숫자를 끼워 넣고 퍼즐을 완성하면 됩니다. 이를 구현하기 위해 DFS 방식을 사용합니다. 깊이를 늘려가며 퍼즐을 만들어 가다가 유효하지 않은 퍼즐이 생성되면, 이전 단계로 이동해 유효하지 않은 숫자를 버리고 유효한 숫자를 집어넣어 재탐색을 진행합니다. 해당 문제는 까다로운 부분이 존재하는데, 답이 여러 개 생성될 수 있다는 것이고 이를 제한하지 않으면 "출력초과"가 발생하게 됩니다.또한 기본적인 백트래킹을 사용하면 시간 초과가 발생하기 때문에 최적화를 염두하여 문제를 풀어내야 합니다.[초기화] def _..
