alpyrithm_알파이리즘

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 한 조각을 두 번 사용할 수 없으므로 왼쪽 인덱스 < 오른쪽 인덱스인 경우에서만 반복..

5052 전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 문제 풀기 전 공부할 것 : 트라이(Trie) 풀이 1 전화번호 목록을 받아서 정렬을 하면 prefix의 가능성이 있는 번호가 앞뒤로 정렬된다. 따라서 바로 뒤에 있는 번호만 확인하면 된다. import sys input = sys.stdin.readline t = int(input()) for _ in range(t): n = int(input()) nums = [input(..

1700 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 풀기 전 공부할 것 : 그리디 알고리즘 풀이 1 전기용품의 이름 list인 kind를 for문으로 돌면서 kind[i]가 이미 plug에 꽂혀있으면 continue로 넘어간다. plug에 구멍이 남아있으면 kind[i]를 꽂고 넘어간다. kind[i]가 plug에 꽂혀있지 않으면서 plug에 구멍이 남아있지 않다면 idx를 저장할 idxs list를 만들고 plug에..

1747 소수&팰린드롬 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 풀기 전 공부할 것 : 소수 구하는 방법, 에라토스테네스, 팰린드롬 풀이 1 에라토스테네스의 체를 이용해서 1,000,000 이하의 범위에서 소수를 찾는다. 그리고 n보다 크거나 같으면서 1,000,000보다 작거나 같은 수에서 팰린드롬인 수를 먼저 찾아준다. 팰린드롬인 수면 소수인지 위에서 구한 prime을 통해 확인한다. 만약 ..

1205 등수 구하기 https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 송유진의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000�� www.acmicpc.net 문제 풀기 전 공부할 것 : 문제 해석 풀이 1 0

1449 수리공 항승 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 풀기 전 공부할 것 : 정렬, 반복문 풀이 1 새는 곳 위치 한 곳을 막기 위해서는 길이가 1인 테이프 1개가 필요하다. 새는 곳의 위치부터 테이프를 붙였다면 테이프의 길이만큼 떨어진 곳까지 막을 수 있다. 새는 곳의 위치를 오름차순으로 정렬한다. 새는 곳의 위치는 자연수이므로 1로 초기화를 하고 현재 막을 수 있는 곳도 leak의 0번째(새는 곳의 가장..