Baekjoon

문제 링크 # https://www.acmicpc.net/problem/1780 문제 해설 # Idea # Divide and Conquer 2차원 배열의 요소를 완전탐색하면서 동일한 값으로 구성되지 않을 경우, 행렬을 9등분하여 재귀적 호출 수행 처음 시도에서는 행렬을 매번 슬라이싱하면서 전달하여 시간 초과가 발생 행렬의 시작 인덱스 번호를 전달하고 길이 …

문제 링크 # https://www.acmicpc.net/problem/1182 문제 해설 # Idea # Brute Force 전체 배열에서 1부터 N개의 부분 조합을 완전탐색하면서 합이 S와 같은 경우를 카운트하고 출력 Data Size # N: 1 <= int <= 20 S: abs(int) <= 1,000,000 arr: …

문제 링크 # https://www.acmicpc.net/problem/11725 문제 해설 # Idea # BFS 1번 노드부터 BFS를 수행하면서 다음 노드에 순차적으로 접근 다음 노드가 이미 방문한 노드의 경우 부모 노드라 판단하여 배열에 저장 부모 노드가 저장된 배열에 대해 2번 노드부터 순차적으로 부모 노드를 출력 Time Complexity # …

문제 링크 # https://www.acmicpc.net/problem/1676 문제 해설 # Idea # Math 팩토리얼 수를 구하고 문자열로 변환해 연속되는 0의 개수를 출력 Data Size # N: 0 <= int <= 500 해설 코드 # Copy python from math import factorial import re N = …

문제 링크 # https://www.acmicpc.net/problem/1541 문제 해설 # Idea # Greedy 최솟값을 만들기 위해서는 ‘-‘를 기준으로 괄호를 치는 것이 최선 ‘-‘를 기준으로 식을 나누고 구분된 식을 계산하여 결과를 출력 Data Size # arr: str(50) 해설 코드 # …

문제 링크 # https://www.acmicpc.net/problem/1389 문제 해설 # Idea # BFS 1부터 N까지의 번호에 대해 매번 BFS를 수행하면서 다른 모든 노드와의 거리를 파악 가장 작은 거리의 합을 가진 노드의 인덱스 번호를 출력 Time Complexity # O(N^2+NM) = 510,000 Data Size # N: 2 …

문제 링크 # https://www.acmicpc.net/problem/5430 문제 해설 # Idea # Implementation, Deque 문제에서 주어진대로 매번 배열을 뒤집으면 O(N^2)의 시간 복잡도로 시간 초과가 발생 배열에 영향을 주지 않으면서 R 함수를 처리하기 위해 상태 변수를 정의하고, D 함수가 호출될 경우 배열의 상태에 따라 첫 …

문제 링크 # https://www.acmicpc.net/problem/1463 문제 해설 # Idea # Dynamic Programming N에 대해 조건을 만족하는 경우에서 3으로 나누기, 2로 나누기, 1 …

문제 링크 # https://www.acmicpc.net/problem/1697 문제 해설 # Idea # BFS N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색 두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행 K에 대한 거리를 출력 N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단 …

문제 링크 # https://www.acmicpc.net/problem/20922 문제 해설 # Idea # Two Pointer 수열의 시작과 끝 지점에 대한 두 개의 포인터 지정 끝 지점에 대한 포인터를 확장하면서 탐색되는 원소의 수를 카운트 원소의 수가 K개와 같아지는 시점부터 시작 지점에 대한 포인터를 확장하여 범위 축소 최종적으로 두 포인터 간 거 …