Waltwaez의 기록장 - 아카이브

https://www.acmicpc.net/problem/10181. 풀이- 주어진 행렬을 8x8로 자른 뒤, 체스판이 되도록 칠하는 문제다.- 체스판의 모양은 항상 2개밖에 없다 : 행렬의 좌측 상단이 흰색이거나, 검은색이거나. 즉,1) 주어진 행렬의 가장 왼쪽 상단의 점을 보고,2) 해당 위치를 기준으로 8x8 행렬에 대해 왼쪽 상단의 점이 흰색일 때 고쳐야 할 칸의 개수와 검은색일 때 고쳐야 할 칸의 개수를 구한 뒤, 그 중 작은 값만 가져간다. - 행, 열의 개수가 50개 이하이므로 최대로 고쳐야 할 칸의 수는 1250개일 것이다. 그래서 최소 칸의 개수를 1251로 놓고 시작했다.- 2차원 행렬이라 변수를 설정할 때 N, M이나 i, j로 놓으면 헷갈리는 경우가 많은데, 나 같은 경우는 row,..

문제 링크 정수 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..