Python

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 사용한 알고리즘 : 세그먼트 트리 풀이 전략 세그먼트 트리란 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조로 위와같은 구조를 가진다. 최댓값을 저장하는 트리 초기 설정 코드 static int max_init(int arr[], int node, int nodeLeft, int nodeRight){ if(nodeLeft==nod..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 풀이 사용한 알고리즘 : BIT(Binary Index Tree, segment tree) 풀이 전략 바이너리 인덱스 트리에 대한 이해가 있어야만 풀 수 있는 문제이다. 바로 전에 풀었던 구간합 구하기와 풀이 방법이 동일했다. 바이너리 인덱스 트리와 풀이 방법에 대해 자세히 적어놓았으니 아래 링크를 참고바란다. https://chaechaeros.tistory.com..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 사용한 알고리즘 : BIT(Binary Index Tree) 풀이전략 BIT 알고리즘에 대해 이해하고 있어야만 이 문제를 풀 수 있다. 따라서 BIT 알고리즘에 대해 설명하도록 하겠다. 1. 트리 구조 만들기 원소가 8개인 리스트가 주어졌을 때, 해당 리스트를 바이너리 인덱스 트리로 만들어 보겠다. 1~8 사이의 숫자들을 이진수로 바..

https://www.acmicpc.net/problem/2550 2550번: 전구 첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력 www.acmicpc.net 풀이 사용한 알고리즘 : LIS 풀이 전략 import sys input=sys.stdin.readline N=int(input()) switch=list(map(int,input().split())) bulb=list(map(int,input().split())) arr=[] for i in switch: arr.append(bulb.index(i)) length=[0]*N preNode=[] for i i..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 사용한 알고리즘 : LIS (Longest Increasing Subsequence) 원소가 N개인 배열에서 일부 원소를 골라내서 만든 부분수열 중 오름차순을 만족하며, 그 길이가 최대인 수열을 LIS라고 한다. 풀이과정 1. 입력값을 저장할 arr, 특정 인덱스에서 내림차순의 LIS 값을 저장할 length 리스트를 정의한다. 2. 0~N-1 인덱스를 돌며 특정 인덱스에서 해당 ..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 사용한 알고리즘 : 풀이1_ 라인 스위핑, 풀이2_투 포인터 ※풀이 전략 2가지 전략으로 풀이를 해보았다. 풀이1. (라인 스위핑) 1. 입력받은 각각의 수를 튜플 형식으로 리스트에 추가한다. 만약 음수면 (abs(수), -1)로, 양수면 (수, 1) 형식으로 리스트에 추가한다. (abs는 절댓값 의미) 2. 리스트에 저장된 튜플들을 튜플의 첫 번째 원소로 ..

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/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net import sys input=sys.stdin.readline n=int(input()) result=[0]*(50*20+1) #50이 20번 쓰여 더해진게 최대값이므로 RomaNum=[1,5,10,50] buf=[] cnt=0 def recur(x,start): if x==n: result[sum(buf)]=1 return for i in range(start,4): buf.append(RomaNum[i]) recur(x+1,i) buf.pop() recur(0,0) print(sum(re..