목록Algorithm/백준 (224)
Hanbit the Developer
https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net import sys input = sys.stdin.readline def get_pi(keyword): keyword_length = len(keyword) pi = [0]*keyword_length j = 0 for i in range(1, keyword_length): while keyword[i] != keyword[j] and j > 0: j = pi[j-1] if keyword[i]..
https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net import sys input = sys.stdin.readline dx = [-1, -1, -1, 0, 1, 1, 1, 0] dy = [-1, 0, 1, 1, 1, 0, -1, -1] POINTS = [0, 0, 0, 1, 1, 2, 3, 5, 11] LENGTH = 4 class Node: def __init__(self): self.children = {} self.is_e..
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬에 단지 우선순위큐를 사용한 문제이다. 위상 정렬은 아래 글에 설명되어있다. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-2623%EB%B2%88-%EC%9D%8C%EC%95%85%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8 [Python] 백준 2623번: 음악프로그램 https..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net import sys input = sys.stdin.readline def solution(): primes = get_prime_numbers() # Two pointers count = 0 primes_length = len(primes) start = 0 cur_sum = 0 for i in range(primes_length): # 현재 값을 추가 cur_sum += primes[i] # N 이하가 될 때까지 감소시킴 while cur_sum > N: cur_sum -= primes[start] start +..
https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net Segment Tree의 응용인 Lazy propagation의 응용 문제이다. Lazy propagation의 상세한 설명은 아래 링크에 담겨있다. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%9..
https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net import sys input = sys.stdin.readline class Node(): def __init__(self, key): self.key = key self.children = {} class Trie: def __init__(self): self.head = Node(None) def insert(self, strings): current_node = self.he..
https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Lazy Propagation을 통해, query, update 동작을 O(logN)으로 수행하여 이 문제를 해결한다. 이 글은 기본적인 Segment Tree를 알고 있다는 가정하에 설명한 것이다. 먼저, get_tree_length() 함수를 통해 적절한 길이를 얻고, 트리, lazy를 초기화 시킨다. 만약 N이 2의 제곱꼴이라..
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include typedef struct Node { int val; struct Node *next; } Node; // Get minNode whose next node is min in linked list Node *getMinNode(Node *header, int length) { Node *cur = header; Node *minNode = cur; for (int i = ..
https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': N, M, K = map(int, input().split()) # Set counts counts = [[1]*(M+1) for _ in range(N+1)] for i in range(1, N+1): for j in range(1, M+1): counts[i][j] = counts[i-1][j] + counts[i][j-1] ..