Dogfootruler Kim

문제 www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 그냥 문제에서 하라는대로 해주면 된다 ,, 쉽따 .. 소스코드 import sys input = sys.stdin.readline def add(x): if x not in arr: arr.append(x) def remove(x): if x in arr: index = arr.index(x) arr.pop(index) def check(x): if x in arr: print("1") else: print("0") def toggle..

문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 입출력 예제를 보면 바로 규칙을 알 수 있다. 4일 때, 7 7일 때, 44 10일 때, 274 1~3 일 때는 쉽게 계산이 가능하다. 1 -> 1 2 -> 2 3 -> 4 4 -> 7 5 -> ? 6 -> ? 7 -> 44 여기서 5까지만 구해봤다. 5일 때 13개가 나왔다. 그렇다면, 1 -> 1 2 -> 2 3 -> 4 4 -> 7 5 -> 13 6 -> ? 7 -> 44 이제 규칙이 보일 것이다 ! dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 인 것을 알 수 있다. 확실하게 알기..

문제 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 문제가 어려워 보이지만, 간단히 말하면 트리에서 마지막 입력받는 정점을 루트로하는 서브트리의 정점의 수를 출력하면 된다. dfs로 탐색하면서 각 정점에 대한 서브트리의 수를 count 배열에 담아준다. count 배열로 방문여부 표시도 같이 해줄 수 있다. 소스코드 import sys input = sys.stdin.readline sys..

문제 www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 가장 긴 증가하는 수열의 변형? 이라고 생각하면 된다. 먼저, 입력 리스트를 오름차순으로 정렬시킨 후, b 전봇대 기준으로 가장 긴 증가하는 수열을 구한다. n 에서 그 구한 수열의 길이를 빼주면 된다. 가장 긴 증가하는 수열을 구하기 위해서, B 전봇대 현재 가르키고 있는 위치 숫자보다 작되, 제일 카운트가 큰 숫자에 +1을 해주면 된다. 소스코드 import sys input = sys.stdin.rea..

문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n의 경우의 수를 몇가지 구해보면, 피보나치 문제와 같은 것을 알 수 있다. n = 1, 1개 n = 2, 2개 n = 3, 3개 n = 4, 5개 n = 5, 8개 n = 6, 13개 소스코드 n = int(input()) dp = [0]*(n) dp[0] = 1 dp[1] = 2 if n == 1 or n == 2: print(dp[n-1]) exit() for i in range(2, n): dp[i] = dp[i-..

문제 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 n == 0 일 때, f(0) = 1, f(1) = 0 n == 1 일 때, f(0) = 0, f(1) = 1 n == 2 일 때, f(0) = 1, f(1) = 1 n == 3 일 때, f(0) = 1, f(1) = 2 n == 4 일 때, f(0) = 2, f(1) = 3 n == 5 일 때, f(0) = 3, f(1) = 5 n == 6 일 때, f(0) = 5, f(1) = 8 잘 보면 규칙을 발견할 수 있다 ! n>=2 일 때, f(0) = n-1의f(0)개수 + n-2의f(0)개수, f..

문제 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 소스코드 def solution(participant, completion): answer = '' participant.sort() completion.sort() for i in completion: if i in participant: index = participant.index(i) del participant[index] answer = p..

문제 programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 풀이 말 그대로 두 개 뽑아서 더해줬다. 소스코드 def solution(numbers): answer = [] for i in range(len(numbers)): for j in range(i+1, len(numbers)): num = numbers[i]+numbers[j] if num not in answer: ans..