For Programmer

https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 처음에 전체를 N번 동안 돌고 각 반복문마다 앞에서 앞,뒤(i,i+1) 값을 보면서 앞의 값이 뒤의값보다 크다면 앞의 값을 (앞의값 - 뒤의 값 + 1)으로 바꿔주는 방식으로 생각했다. 다행이 N = 100이라 O(N^2)이 통과되었지만 N 이 10000이상일때도 해당 문제를 풀려면 O(N)방식을 생각해야한다. 따라서 그 방식이 뒤에서부터 값을 비교하며 만약 앞에값이 뒤값보다 더 크다면 해당 값..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 위 문제는 그리디적으로 접근해야하는데 실버4 치고는 처음에 사실 생각하기 꽤 어려웠다. 풀이법은 우선 오름차순 정렬한뒤 젤 작은값 * 총개수 , 그다음작은값 * (총개수 - 1) , ... 와같은식으로 계산한다음 가장 큰 값을 출력하는 식으로 접근하면 된다. 해당 문제의 증명은 각자 다들 잘 생각해보기 바란ㄷㅏ........ import sys input = sys.stdin.readli..

https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 간단한 그리디 문제이다. 1부터 1씩증가시켜가면서 계속 더해가며 횟수를 센다. 만약 S와 같다면 그 횟수를 출력하면 되고 S보다 크다면 마지막 더한 횟수를 -1 해준 값을 출력하면 된다. S = int(input()) cur = 0 # 현재 값 i = 1 # 더할 값(1씩 증가) cnt = 0 # 더한 횟수 while True: cur += i # i만큼 계속 더한다 cnt += 1 # 횟수를 1씩 증가 if cur > S: # 만약 S보다 크다면 한개 줄이면 되므로 cnt -= 1 # 횟수를 1개 줄이고 brea..

https://www.acmicpc.net/problem/24956 24956번: 나는 정말 휘파람을 못 불어 '유사 휘파람 문자열'인 부분 수열의 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제 사실 골드 4 치고는 굉장히 어려운 문제이다. 접근 방법은 다음과 같다. 1. 누적합으로 W와 E의 개수를 미리 구해야 놓아야 한다. (단 E는 반대방향으로 누적합) 2. H를 만날때 마다 해당 H지점에서 왼쪽으로 W의 개수 * 2 ^ 오른쪽으로 E의 개수 - E의개수 - 1 로 구해야한다. 3. pow 내장 메서드와 3번 째인자 Mod 사용하면 더욱더 빠른 시간복잡도로 2 ** N 계산이 가능하다. 여기서 의문인 2 ^ 오른쪽으로 E의..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 간단한 투포인터 문제이다. 하지만 주의할 점은 문자의 종류가 N개 보다 작아도 최댓값을 갱신해주어야 한다. (문제에서 이부분에 대한 설명이 약간 부족했다. 이 부분을 테스트 케이스로 보여주면 좋았겠다.. ㅠ) alpha = [0] * 26 N = int(input()) word = input() + 'z' # 문자열의 범위를 벗어나지 않게 하기 위해 아무 문자로 패딩 s = 0 # 시작인덱스 e = 0 #..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 빠른 소수 구하기(에라토스테네스의 체 최적화) 2. 투포인터 (연속된 구간의 합) 위의 2가지를 이용하면 쉽게 문제를 해결할 수 있다. N = int(input()) # 빠른 소수 구하기 (에라토스 테네스의 체 최적화) sosu = [True for i in range(N + 1)] sosu[0], sosu[1] = False, False temp_sosu = [] for i in range(2, len(sosu)): if not sosu[i]: continue temp_sosu.append(i) index =..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 모르면 한없이 어렵고 알고나면 한없이 쉬운 문제이다. 그냥 간단하다 1. 리스트안에 x,y,z 좌표와 현재의 점 번호를 함께 튜플로 저장한다. 2. 각각의 점을 기준으로 정렬한 후 3. 바로 붙어있는 점이 가장 짧은 거리이므로 그 거리를 계산해서 4. 다시 리스트 하나에 해당 두점과 거리를 모두 넣어준다. 5. 그 후 거리를 기준으로 오름차순 정렬 후 크루스칼 해주..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 간단히 크루스칼 코드만 알고 있다면 쉽게 해결할 수 있다. 조건 2가지 ( 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. , 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.) 가 있는데 그 중 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 의 조건을 생각하기가 까다로울 수 있다. 문제를 잘보..