(python3) 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 수학으로 해결하기 1,2,3으로 조합해서 수를 만드는 방법은, 3을 먼저 넣고, 남은 값을 2로 만들고, 그리고 남은 값은 1을 채우는 것과 같다. 코드 import sys def solution(input) : N = int(input().strip()) for _ in range(N) : S = 0 n = int(input().strip()) for i in range(n//3 ..
(python3) 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 두 포인터로 시작점과 끝점 잡기, 원소별 등장 횟수 세기 원소별로 등장 횟수를 세면서 횟수가 K가 넘어갈때까지 끝점을 한칸씩 뒤로 옮깁니다. 등장 횟수 카운팅은 try except와 dict를 활용했습니다. 카운팅이 K를 넘어간 경우 s ~ e-1 의 문자열 길이를 확인해서 최대 부분 문자열 길이를 찾습니다. 마지막에 추가되면서 임계치를 넘긴 그 문자가 나올때까지 s를 뒤로 밉니다. s를 밀면서 s~e 에서 빠지는 문자들의 카운팅도 빼줍니다..
(python3) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 문제 유명한 DP 유형이라 따로 정리해보았습니다. LCS (Longest Common Subsequence, 최장 공통 부분 수열) 두가지 LCS 두 문자열의 연속된 공통 부분 : longest common substring 두 문자열의 공통 부분 : longest common subsequence DP 이 문제의 핵심 풀이법은 DP 입니다. 연속된 공통 부분 (LCSubstring) 찾..
(python3) 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net (시간초과) 풀이 1. 모든 순열을 만들고 체크하기 perm 함수에서 모든 순열을 만듭니다. 순열은 재귀로 만들었습니다. 순열이 완성되었을 때 is_correct 함수로 이 순열이 주어진 조건과 같은지 확인합니다. 같으면 출력하는 형식으로 코드를 짜봤는데 시간초과..입니다. N = 10 이 최대 입력이라 10! 이면 괜찮을지도? 라는 생각이었는데, 컴퓨터가 8~9부터 힘겨워하더라구요 코드 import sys from copy import..
(python3) 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 메모리 초과, 최소힙, heapq 배열을 모두 받은 상태에서 맨 아랫줄 N개를 비교해서 가장 큰 값을 찾아서 pop 하는 방식으로 N번 수행해서 N번째 pop 되는 값을 구하려고 했는데, 메모리초과가 났습니다. 이 문제는 최소힙으로 정보를 읽어올때마다 항상 N개의 값만 저장하는 방식으로 해결할 수 있습니다. 파이썬에서는 배열을 최소힙 형태로 관리할 수 있는 heapq 모듈을 제공합니다. 아래 독스로 사용법을 확인할 수 있습니다. heapq — Hea..
(python3) 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 아이디어 사진 틀이 꽉 차있을 때 새로운 후보가 들어오면 기존 사진틀의 후보 중 우선순위가 가장 낮은 후보를 삭제해야합니다. 우선순위는 1. 득표수 높은 순, 2. 나중에 들어온 순 으로 결정됩니다. 저는 후보 득표를 빨리 올리기 위해서 dict를 사용했고 삭제할 후보를 찾아야할 때 마다 정렬하는 방식으로 해결했습니다. 코드 import sys def solution(input) : N = int(input().strip()) M = ..
