Algorithm

문제 링크 # https://www.acmicpc.net/problem/1927 문제 해설 # Idea # Heapq 파이썬 heapq 모듈 자체가 최소힙이기 때문에 해당하는 기능을 활용하여 구현 Time Complexity # O(Log N) = 16 Data Size # N: 1 <= int <= 100,000 x: 0 <= int …

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

문제 링크 # https://school.programmers.co.kr/learn/courses/30/lessons/77486 문제 해설 # Idea # Union-Find 알고리즘의 Find() 함수를 사용하여 부모 노드에 대해 재귀적으로 접근 최악의 경우 O(NM)=10^10으로 시간 초과가 발생하지만, 매 탐색마다 최대 10,000원을 10 …

문제 링크 # 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://school.programmers.co.kr/learn/courses/30/lessons/68936 문제 해설 # Idea # Divide and Conquer 2차원 배열을 4등분씩 나눠 재귀함수를 호출하고 동일한 값으로 채워져 있는지 판단하여 값의 개수 증가 2^n 형태의 정수에 대해 NumPy …

문제 링크 # https://school.programmers.co.kr/learn/courses/30/lessons/87390 문제 해설 # Idea # Greedy n의 크기가 굉장히 크기 때문에 2차원 배열을 만드는 것만으로 시간 초과가 발생할 것을 예상 r행 c열의 값은 max(r,c)+1과 같고 1차원 배열의 인덱스 i에 대해 r은 i//n, c …

문제 링크 # https://school.programmers.co.kr/learn/courses/30/lessons/17687 문제 해설 # Idea # Math 0부터 시작해 t*m의 길이를 만족하는 N진법 배열을 생성 매 순서마다 p 위치에 해당하는 값을 추출해 문자열로 반환 Data Size # n: 2 <= int <= 16 t: 0 …

문제 링크 # 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) 해설 코드 # …