백준

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 풀이 사용한 알고리즘 : 라인 스위핑 풀이전략 1. 시작점과 끝점에 대한 튜플 배열을 별개로 생성한다. 시작점의 튜플은 (시작점 위치, 1) 끝점의 튜플은 (끝점 위치, -1)로 만든다. 위 문제에서 주어진 예제 입력 1번을 예로들면 아래와 같다. 시작점 배열 = [ [0,1], [15,1], [5,1] ] 끝점 배열 = [ [40,-1], [30,-1], [10,-1] ] 2. 시작점 배열과..

https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 풀이 사용한 알고리즘 : 라인 스위핑 풀이 전략 1. 맨처음 시작 위치인 0과 첫 가로등 사이의 거리를 구한다. 2. 각 각로등 사이의 거리를 구하되 짝수 거리만큼 떨어져 있으면 나누기 2한 몫을, 홀수 거리만큼 떨어져 있으면 나누기 2한 몫에 1을 더한 값들 중 가장 큰 값을 저장한다. 3. 마지막 가로등의 위치와 굴다리 맨 마지막 위치 사이의 거리를 구한다. 4. 1~3번에서 구한 값들 중 가장 ..

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 풀이 사용한 알고리즘 : 라인 스위핑 ※ 풀이 전략 1. 입력 받은 선들을 시작점 기준으로 오름차순 정렬한다. 2. 맨 처음 입력한 선분의 시작점을 start, 끝점을 end로 둔다. 3. 다음 선의 시작점이 end보다 작으면 end는 해당 선의 끝점으로, 다음 선의 시작점이 end보다 크면 start는 해당 선의 시작점, end는 해당 선의 끝점으로 변경한다. 4..

https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹, 백트래킹 ※ 풀이 전략 1. 학생 개인이 풀 수 있는 문제를 2진수로 나타낸다. 풀 수 있는 문제는 1, 풀 수 없는 문제는 0으로 표기한다. ex) 예로 1번 학생이 총 5문제 중 2, 3, 5 번을 풀 수 있다고 한다면 10110 (2) = 22 이다.(오른쪽부터 1번 문제이고, 맨 왼쪽 비트가 5번 문제를 나타낸다.) 2. 백트래킹을 기법을 이용..

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 사용한 알고리즘 : 비트마스킹 풀이 전략 : 입력한 숫자를 2진수로 생각하고, 해당 2진수 안에 있는 1의 개수가 K개 이하가 될 때까지 1씩 더한다. (비트 1의 개수가 곧 물병의 개수를 의미하기 때문이다.) ex ) 000000001 = 1L 물병 1개 => 총 물병의 개수 : 1 000000010 = 2L 물병 1개 => 총 물병의 개수 : 1 000001010 = 8L 물병 1개, 2L 물병 1..

https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹 풀이 전략 : 기본값을 2^20으로 두고 비트마스크를 통해 승객을 태우거나 하차시킨다. default=Math.pow(2,20) 최초 기차의 상태는 00000 00000 00000 00000 이다. 여기서 비트 마스킹에 사용할 값인 default를 1 00000 00000 00000 00000 로 두고 아래 명령에 따라 변화하는 기차 상태값을 살펴보자. ..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input=sys.stdin.readline N,M=map(int,input().split()) visited=[False]*(N+1) result=[] def back_Tracking(x): if x==M: print(' '.join(map(str,result))) return for i in range(1,N+1): result.append(i) back_Tracking(..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input = sys.stdin.readline N,M=map(int,input().split()) visited=[False]*(N+1) result=[] def recur(x): if x==M: print(' '.join(map(str,result))) return for i in range(1,N+1): if visited[i]==False and (len(result)..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input=sys.stdin.readline n,m=map(int,input().split()) visited=[False]*(n+1) result=[] def recur(x): if x==m: print(' '.join(map(str,result))) return for i in range(1,n+1): if visited[i]==False: visited[i]=True r..

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net import sys from collections import deque n,m,r=map(int,sys.stdin.readline().split()) graph=[[] for _ in range(n+1)] visited=[0 for _ in range(n+1)] def bfs(start): cnt=1 visited[sta..