알고리즘||코딩테스트

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/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 사용한 알고리즘 : 이진 탐색, LIS(Longest Increasing Subsequence) 풀이 전략 1. 첫 번째 입력한 수를 비어있는 result 리스트에 추가한다. 2. i 번째 입력한 수가 result의 맨 끝값보다 크면 result 리스트에 추가한다. 3. i 번째 입력한 수가 result의 맨 끝값보다 작으면 result 내부를 이진탐색하여, 해당 수보다 크거나..

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