이숭간 공부기록

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제유형 : DP 문제풀이 : 최적부분구조와 중복되는 부분문제를 만족하므로 DP(다이나믹 프로그래밍)으로 풀어야하는 문제이다. 현재의 최적의 해 = 2로 나누었을때 최적의해, 3으로 나누었을때 최적의해 중 작은값 + 1 ( 물론 나누어 떨어질때만 나눌수있음) 정답코드: import sys input = sys.stdin.readline n = int(input()) dp = [1] * (n+1) # 숫자랑 인덱스 일치시키기 위해서 0은 안쓰는걸로 if n==1: # 1이면 0이므로 출력하고 종료 print(0) exit() ..

www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제유형 : 큐 (자료구조) 문제풀이 : 원 형태로 연결되어있는 자료구조를 큐로 구현하기 내가 원하는 곳 (타겟지점) 으로 도달하기까지 거치는 것들은 큐에서 빼고 다시 큐에 넣어주는 형식으로 하면 원 형태의 자료구조를 큐로 구현할 수 있다. ex ) 1,2,3,4,5,6,7에서 3을 타겟으로 할때 거치는 1,2,는 다시 뒤에 넣어줌으로써 3,4,5,6,7,1,2를 구현할 수 있다. 정답코드 : import sys input = sys.stdin.readline n,k = map(int, inpu..

www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제유형 : 수학, 에라토스테네스의 체 문제풀이 : 2부터 차례대로 담긴 배열을 순회하면서, 배수들을 전부 표시하고 표시된걸 만나면 건너뛰는식으로 소수가 아닌것들을 전부 표시한다 예를들어 2는 표시가 안되어있으므로 4,6,8,10 ... 로 표시를 하고 3도 마찬가지로 6,9,를 표시할건데 이미 앞에서 6이 표시되었으므로 이때는 건너띄고 9로 넘어간다. 만약 4처럼 처음부터 바로 2에의해 표시된 수를 만난경우 바로 건너뛴다. (다음으로_ 5로) 참고 : m.blog.naver.c..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제유형 : 이진탐색 문제풀이 : n과m의 범위가 10만까지이므로 완전탐색을 진행하면 n*m이 되므로 시간초과가 남을 예상하고 탐색에서 logN의 시간을 갖는 이분탐색을 떠올려야한다. 이진탐색 정리! 이진탐색은 정렬된 배열을 대상으로 한다. 이진탐색 함수의 매개변수에는 배열, 타겟(찾고자하는 값), 시작인덱스, 끝인덱스 를 필요로한다. 찾고자하는 값이 없을때에 대..

www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 문제유형 : 정렬 문제풀이 : 사용자들 정보가 담긴 배열의 원소를 튜플로 저장 , 튜플의 형태는 (나이, 이름, 가입한순서) 정렬하는데 1순위 나이, 2순위 가입한순서로 정렬 출력은 나이, 이름 파이썬 튜플정리 ! 튜플은 생성후 변경 불가능 (삽입, 삭제 불가능) 소괄호를 이용해 선언 + 연산자를 이용해 튜플 2개를 한개의 튜플로 합칠 수 있다. 슬라이스 기능 이용가능 (리스트와 방법 동일) len(), max(),..

www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제유형 : DP, 수학, 구현 문제풀이 : 방법1. DP로 푸는방법 : 이항계수는 k가 0일때 and n과 k가 같을때 1이고 나머지값에대해서는 n,k = n-1,k + n-1,k-1의 값을 갖는다. 따라서 array[i][j] = array[i-1][j] + array[i-1][j-1] 의 점화식을 이용하면서 DP배열을 채워나가면 된다. 방법2 : 이항계수 공식으로 팩토리얼 라이브러리 이용 공식 = n! / k! * (n-k)! 로 계산 math.factorial() 이용 정답코드 ..