Waltwaez의 기록장 - 아카이브

문제 링크 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 1. 풀이- 처음에는 BFS로 풀었다. 그런데 시간 초과가 났다.1. DP로 풀었다. ('동적 프로그래밍'이라는 말을 쓰지만 메모이제이션이라는 말이 더 직관적인 것 같다.)2. 글을 쓰면서 BFS 코드를 다시 봤는데, 암만 생각해 봐도 BFS 코드가 DP 코드에 비해 시간 초과가 날 부분이 없다는 생각이 들었다. 그래..

1. 힙이란? 1 / \ 3 4 / \ / 5 6 7- 완전 이진 트리 Complete Binary Tree 형태를 갖는 자료구조이다.-- 완전 : 마지막 레벨을 제외한 모든 레벨(깊이)에서 노드가 완전히 채워져 있다-- 이진 : 모든 부모 노드는 2개의 자식 노드를 갖는다. - 모든 부모 노드의 값은, 자식 노드보다 크거나 같다. - 배열로 구현할 수 있다.-- 인덱스 i 에 대해, 왼쪽 자식은 2i + 1 에, 오른쪽 자식은 2i + 2 에 위치한다.-- 부모 노드는 (i - 1) // 2 에 위치한다.1.1. 추가 과정(heapq.heappush)1. 주어진 배열의 가장 마지막 인덱스에 값을 추가함2. 추가한 값이 부모 노드보다 작다면, 부모 노드와의 ..

1. DFS- 깊이 우선 탐색(Depth First Search)import sysinput = sys.stdin.readlineN, M, v = map(int, input().split())graph = {}for i in range(1, N+1): graph[i] = []for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a)dfs_visited = [0] * (N + 1)def dfs(node): dfs_visited[node] = 1 graph[node].sort() for next_node in graph[node]: if dfs_visited..

1. 기본1. 2부터 구하고자 하는 수까지 모두 나열2. 2부터 숫자를 올리며 자신의 배수는 제거3. 과정 2를 반복하면 구간의 모든 소수가 남게 됨2번에서 올라가는 숫자는 구하고자 하는 수까지 가지 않아도 된다. 구하고자 하는 수의 제곱근까지만 가도 됨.2. 구현# 정수 n까지의 소수 리스트 얻기def sieve_of_eratosthenes(n): prime = [True] * (n + 1) prime[0] = False prime[1] = False for p in range(2, int(n**0.5) + 1): if prime[p]: for i in range(p * p, n + 1, p): prime[i] = Fals..

이진 탐색은 일반적으로 이렇게 짠다.def binary_search(arr, target): left = 0 right = len(arr) - 1 while left 1. 종료 조건- 종료 조건은 인덱스가 left > right일 때이다. (즉 반복 조건은left - left   2. 갱신 조건위처럼 left, right 를 갱신하는 게 일반적이지만.. 2.1. 중복 값중 가장 왼쪽/오른쪽 인덱스 찾기중복된 값 중 가장 왼쪽을 찾고 싶거나, 가장 오른쪽을 찾고 싶은 경우는 아래처럼 구현한다.공통적으로 left 가장 왼쪽 찾기 : right 갱신 조건에서 mid - 1 대신 mid  가장 오른족 찾기 : left 갱신 조건에서 mid + 1 대신 mid  가장 왼쪽 인덱스 값 찾기 w..