전체 글

기업에 따라 라이브러리 사용에 제한이 있기 때문에, Python의 장점 중 하나인 itertools 사용할 수 없는 경우가 생기게 됩니다. 그렇기 때문에 코딩테스트를 앞두고 관련 알고리즘을 직접 구현하며 정리하는 시간을 가져보았습니다. 하나의 템플릿처럼 제가 자주 사용하는 형태로, 모든 구현에 재귀를 사용합니다. 이유는 처음 관련된 내용을 학습했을 때, 반복문보다 흐름이 더 직관적이었기 때문입니다.[조합]def c(idx, target, result): # 리스트의 현재 인덱스, 선택된 수의 개수, 만들어지 조합 if target == n: print(result) return if idx == len(arr): # 숫자들이 다 선택되지 않은 상태에서 다음 숫자를 ..

[문제]https://www.acmicpc.net/problem/12100오랜만에 높은 난이도의 문제를 풀어보았는데, 전혀 Easy하지 않았습니다. 풀이 방식 자체는 어렵지 않게 떠올렸는데, 보드를 조작하는 과정에서 원상 복귀하는 것을 고려하지 않아 디버깅에 3시간을 헤맨 문제입니다. 또한 생각한 풀이가 너무나도 삼성스럽길래 찾아보니 기출문제가 맞았습니다.https://www.acmicpc.net/problem/15683이 문제와 유사한 거 같습니다.[초기화]public class BOJ_12100_2048Easy { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer s..

[문제]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/9466문제를 단순하게 표현하면, 형성된 그래프에서 사이클에 속하지 않는 노드의 수를 찾으면 되는 문제입니다. 여기서 노드는 학생을 의미합니다.12345673137346문제의 예시를 그래프로 나타내면 다음과 같은 모습을 나타내게 됩니다. 여기서 사이클에 속하지 않는 노드는 1, 2, 5 총 3개가 됩니다. 위와 같이 그래프로 표현해 보고, 문제에서 제시하는 바가 사이클에 속하지 않는 노드를 찾아야 한다는 것을 알 수 있었습니다. 문제 자체는, BFS와 DFS 모두 수행가능하지만, 최단 경로를 찾는 문제도 아니고 탐색 과정을 추적하는 과정에서 별도의 비용일 발생하는 BFS보다 DFS가 적합하기 때문에, 해당 방식으로 문제를 풀어냈습니다. 제 ..

[문제]https://www.acmicpc.net/problem/4577조건에 맞춰 시뮬레이션을 수행하면 되는 단순한 문제입니다. 하지만 예외 처리 부분을 바로 떠올리지 못해 시간을 많이 잡아먹었던 문제입니다. 또한 게임이 끝났을 때 남은 명령을 수행하지 않는다는 것을 확인하지 못해 더 오래 걸렸습니다. [초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int r, c; static char[][] grid; static String command; static StringBuilder sb = new StringBuilder(); stat..

[문제]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..

6주 차는 PQ(Priority Queue)에 대해 학습했습니다. 해당 자료구조에 대해 개념적으로 이해하고 있고 문제를 풀 때, 탐색 시간을 최적화할 때 사용할 수 있는 것도 알고 있지만 해당 유형의 문제를 많이 풀지 않았다 보니, 문제를 풀 때 쉽게 떠올리지 못해 연습하는 시간을 가졌습니다. 파이썬의 경우, 자바와 달리 우선순위 큐가 라이브러리로 구현되어 있지 않기 때문에 우선순위 큐의 연산을 구현할 수 있는 heapq 라이브러리를 사용해 문제를 풀 수 있습니다. heapq는 이진트리로 구현된 자료구조로 값의 삽입 및 삭제 연산의 시간복잡도를 O(log n)으로 수행할 수 있습니다. https://www.codetree.ai/missions/8/problems/process-numeric-command..

5주 차는 DFS(Depth-First Search)에 대해 학습하였습니다. 평소 그래프 문제는 BFS(Breadth-First Search)로 풀다 보니 막상 DFS로 푸는 방법이 생각나지 않았습니다. 저번주차까지 Backtracking에 대해 학습했으므로 응용 및 복습 겸 진행해 보았습니다. https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai요약하..

4주 차도 Backtracking에 대해 학습했습니다. 실력 진단을 수행했는데, 해당 유형의 문제를 풀지 못했습니다.https://www.codetree.ai/missions/2/problems/select-segments-without-overlap?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ain = int(input())lines = [tuple(map(int, input().split())) for _ in range(n)]answer = 0selected_lines = []def..

3주 차는 Backtracking에 대해 학습했습니다. 생각하지도 못했는데 굉장히 취약했던 유형이었습니다. 자주 풀었을 땐, 선택하거나 선택하지 않거나의 개념이 그려졌었는데 그래프 유형이나 시뮬레이션, 구현류의 문제들만 풀다 보니 감이 사라져서 대부분의 문제를 정답을 확인했던 주입니다. https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai굉장히 기본적인..