alpyrithm_알파이리즘

2294 동전 2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 1 BFS를 이용해서 해결하기 가치가 같은 동전이 여러 번 주어질 수도 있기 때문에 coins를 set으로 입력받는다. 사용한 동전의 최소 개수를 출력하기 때문에 check를 만들어 확인한다. 불가능한 경우를 위해 flag를 설정한다. que에 우선 주어진 동전의 종류를 넣고 하나씩 꺼내서 k..

1068 트리 www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프, 트리, 깊이 우선 탐색 풀이 각 노드의 부모를 parents에 저장한다. 삭제할 노드도 del_node에 저장하고 tree 맵을 만든다. parents를 for문으로 돌면서 삭제할 노드이거나 삭제할 노드를 부모로 둔 노드를 제외하고 tree에 저장한다. 삭제한 노드가 루트라면 빈 리스트를, 아니라면 [-1]를 que에 저장한다. tree를 돌면서 리프 노..

1049 기타줄 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 문제 풀기 전 공부할 것 : 수학 풀이 1 6줄 패키지와 1줄 낱개 리스트를 따로 만든다. 6줄 패키지로만 산 경우와 6줄 패키지 + 낱개로 산 경우 중 작은 값을 출력한다. import math import sys input = sys.stdin.readline n, m = map(int, input().split()) six_set, one = [], [] for _ in ..

1292 쉽게 푸는 문제 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1≤A≤B≤1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 문제 풀기 전 공부할 것 : 수학 풀이 1 section에 1을 한 번, 2를 두 번, 3을 세 번, ... 의 수를 누적하여 누적이 1000을 넘을 때까지 저장한다. a, b 구간을 for문을 돌면서 누적된 값보다 작아지면 그 인덱스를 더한다. a, b = map(int, input().split()) section = [0, 1] i = 1 while section[-1] < 1000: i += 1 s..

2217 로프 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 그리디 알고리즘 풀이 각 로프가 버틸 수 있는 중량을 입력받는다. 중량을 정렬한다. 해당 중량보다 큰 중량에서는 해당 중량만큼 걸 수 있기 때문에 해당 중량 x 그것보다 같거나 큰 중량이 최대 중량이다. 버틸 수 있는 중량 = 해당 중량 X 해당 중량보다 큰 중량의 수 버틸 수 있는 중량 중 가장 큰 값이 최대 중량이다. import sys ..

4358 생태학 https://www.acmicpc.net/problem/4358 4358번: 생태학 문제 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 입력 �� www.acmicpc.net 문제 풀기 전 공부할 것 : 자료 구조, 문자열, 트리, 트리를 사용한 집합과 맵, 트라이, defaultdict 풀이 1 입력을 받고 만약 입력이 비어있으면 입력받는 것을 멈춘다. 입력받을 때 defaultdict에 value 값에 1을 더해준다. 동시에 전체 나무 수를 찾기 위해 n에도 1을 더해준다. 각 종의 이름을 사전 순으로 출력하기 위해 key값들을 따로 저장해 정렬한다. 비율..

14425 문자열 집합 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어� www.acmicpc.net 문제 풀기 전 공부할 것 : 문자열, 트리, 트리를 사용한 집합과 맵, 트라이 풀이 1 Trie를 공부했으므로 Trie로 풀어보기 Trie를 구현한다. 집합 S는 Trie의 insert를 이용한다. M개의 문자열은 search를 통해 집합 S에 포함되어 있는지 여부를 판단한다. python 시간 초과 pypy 정답 class Node(obj..

3649 로봇 프로젝트 https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 문제 상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다. 구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길 www.acmicpc.net 문제 풀기 전 공부할 것 : 이분 탐색, 정렬 풀이 1 센티미터 = 10000000 나노미터 lego의 조각 길이를 정렬한다. 구멍은 항상 두 조각으로 막아야 하고 정답이 여러 개인 경우 차이가 가장 큰 것을 출력해야 하므로 lego 리스트의 각각의 끝에서부터 레고 조각을 고른다. lego 한 조각을 두 번 사용할 수 없으므로 왼쪽 인덱스 < 오른쪽 인덱스인 경우에서만 반복..