내 잡다한 노트

문제) https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 소스코드) import sys sys.setrecursionlimit(10**8) n, m = map(int, input().split()) dirmap = [sys.stdin.readline().rstrip() for _ in range(n)] #print(dirmap) visited = [[False] * m for _ in range(n)] fini..

문제 ) https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 쉽다고 생각했는데 한참을 애먹은 문제... 시간제한은 1초인데 m, n은 4만까지 있고 그거마저도 test_case가 여러개가 있어서 브루트포스로 하면 1초만에 못한다고 생각을 했는데 가능하더라....ㅋ;; 내 힘으로 풀지 못해 다른 사이트의 코드를 참고했다. 소스코드 ) for _ in range(int(input())): m, n, x, y = map(int, input().split()..

'호'는 한자로 서로 호, '제'는 덜 제 라고 한다. 서로 두 수를 나눈다라는 뜻이라고 한다. - 최대공약수 - 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[..