내 잡다한 노트

'호'는 한자로 서로 호, '제'는 덜 제 라고 한다. 서로 두 수를 나눈다라는 뜻이라고 한다. - 최대공약수 - 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질을 이용해 반복해서 나머지가 0이 나올 때까지 나누면 그 수가 최대공약수라고 한다. function gcd(a, b) { let r while (b != 0) { r = a % b a = b b = r } return a } - 최소공배수 - a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다. function lcm(a, b) { return (a * b) / gcd(a, b) } 위에서 구한 최대공약수로 최소공배수는 쉽게 구할 수 있다..

언제 써야 하는가? ) '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다 핵심 아이디어 ) '거쳐가는 정점'을 기준으로 최단거리를 구하는 것. 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 저장한다. 저울 소스코드중... graph = [[INF] * (n + 1) for _ in range(n + 1)] for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0 for _ in range(m): a, b = map(int, input().split()) graph[a][b] = 1 a -> b로 갈 수 있으면 1로 해주고 가지 못하는 방향이라면 INF로..

문제) https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 처음부터 접근 방법이 잘못돼 한참을 헤매었다. bfs로 풀려고 했는데 나중에 보니 간선의 가중치가 다르더라... 그걸 너무 늦게 깨달았다. bfs, dfs는 간선의 가중치가 1로 다 같을 때 쓸 수 있는 것인데.... ㅠㅠ 소스코드) n = int(input()) m = int(input()) dp = [[inf] * (n+1) for _ in range(n+1)]..

dp = [[0] * len(b) for _ in range(len(a))] dp가 이런 값일때 출력으로 확인해주면 길~게 출력이 돼서 확인하기 힘든 경우가 있다. 그럴 땐 print(*dp, sep="\n") 이렇게 작성해주면 [0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0] 이렇게 출력이 돼서 쉽게 디버깅을 해줄 수 있다. 진짜 개꿀 리스트앞에 * 이게 리스트 안에서 가장 겉에 있는 값을 한꺼번에 넘겨주기 때문이다. 즉, dp가 2차원배열이니 겉에 값인 2차원 안에 있는 값을 한..

from collections import Counter 로 사용할 수 있다. Counter(a)는 말 그대로 a라는 것에 속하는 값의 개수를 세어 주는 편리한 도구이다. 딕셔너리 형태로 리턴해준다. most_common(int) 를 사용하면 개수가 가장 많은 것을 필터링해서 쓸 수 있다 Counter끼리의 비교도 가능하다 + - & | 같은 연산이 가능하다.

문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 소스코드 import sys n, k = map(int, sys.stdin.readline().split()) dp = [10001] * (k+1) dp[0] = 0 coin = [] for _ in range(n): coin.append(int(input())) for c in coin: for p in range(c, k+1): if p-c >= 0: dp[..

iterable한 객체(리스트, 튜플, 문자열)에서 쉽게 값들을 가져오는 방법 -기본 형태- a[start : end : step] 모두 양수, 음수 다 들어갈 수 있다. start는 시작 인덱스 end는 끝 인덱스, 대신 range()처럼 끝 인덱스는 포함되지 않는다 step는 커지는 단계 default 값은 +1 자주 쓰이는 예시 a = [1,2,3,4,5] a[::-1] 이라고하면 문자열을 역순으로 새롭게 만들수 있다. ex) a = [5,4,3,2,1] a[-3:] = [3,4,5] a[:-1] = [1,2,3,4]

에라토스테네스의 체의 쓰임새 - 소수를 대량으로 판별할 때 쓰인다. 시간 복잡도 - 어떤 숫자의 제곱근까지만 약수의 여부를 구하면 돼서 O(n^1/2)가 된다. 알고리즘 - 구해야 하는 소수의 범위로 배열을 할당 - 2부터 시작해서 배수인 숫자들을 지운다. 여기서 자기 자신은 지우지 않는다 - 이것을 전체 범위의 n^1/2까지 했다면 종료시킨다. 더 자세한 설명은 여기로! 그림으로 설명이 잘 돼있는 것 같다. https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4