이숭간 공부기록

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제유형 : 그리디, 정렬 문제풀이 회의가 겹치지 않으면서 최대수를 구해야하므로 끝나는시작이 빠를수록, 끝나는 시작이 같다면 시작하는 시간이 빠를수록 해당 회의를 선택하는것이 최대의 회의개수를 만들수 있다. 시작시간으로도 한번더 정렬해줘야 하는 이유는 시작시간과 종료시간이 같은 회의일경우 count를 해줘야하기 때문이다. 현재일의 시작시간이 이전일의 종료시간보다 크면 count를 증가시킨후, 종료시간을 현재일의 종료시간으로 갱신한다. 정답코드 import sys input = sys.stdin.readline n = int(i..

www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제유형 : 그래프, DFS/BFS 문제풀이 : 그래프에서 연결된 리스트 (덩어리)의 개수를 찾는문제이므로 DFS/BFS를 통해 그래프를 탐색한다. dfs함수는 시작노드에서부터 연결된 노드들로 재귀적으로 호출되며 더이상 방문할 노드가 없을때 리턴된다. 따라서 전체 노드를 순회하며 아직 방문 전일때, 해당 노드를 시작노드로 하여 DFS함수를 실행하면 ..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제유형 : 수학, 그리디, 문자열 문제풀이 : 괄호를 적절히 넣어 최솟값을 만드는 방법이므로 - 를 만나면 앞에 괄호를 넣는다. 언제 괄호를 닫아주는가? 그다음 - 를 만나면 괄호를 닫고 다시 괄호를 열여준다. +일때는 계속 지나간다. 만약 배열이 모두 끝났는데 아직 괄호가 열려있는 상태라면 맨 마지막에 괄호를 추가하여 닫아준다. 괄호가 열려있냐 닫혀있냐의 여부는 flag변수를 통해 수행한다. 위 과정을..

www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제유형 : 수학, DP 문제풀이 : 정답코드 : 1. 내가푼코드 (DP 로품, 근데 걍 빨리 풀고싶어서 좀 안좋게품 호호 _ 메모리낭뷔, 그래도 편법은 아니지않나? ) import sys input = sys.stdin.readline n = int(input()) dp = [-1] * (n+8) dp[2]=1 dp[4]=2 dp[5]=1 dp[6]=3 dp[7]=2 dp[8]=4 for i in range(9, n+1): dp[i] = min(dp[i-2], dp[i-5])+1 print(dp[n]) 2. 다른분 코드 ( DP..

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..