Algorithm
-
[BOJ] 2473번 - 세 용액Algorithm/BOJ 2022. 6. 11. 14:27
[BOJ] 2473번 - 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 알고리즘 각 용액의 3가지의 합이 최소가 되는 경우의 수를 찾아야한다. 이분탐색을 이용하여 하나를 선택한 다음에 나머지 두가지를 매칭하는 방법을 사용하였다. 1. 데이터를 입력 받는다. 2. 이분 탐색을 위하여 데이터를 정렬한다. 3. 각 용액 별로 최소의 경우(left , right 를 두어 결과 값이 0보다 크면 right를 작게 반대는 ..
-
[BOJ] 11660번 - 구간 합 구하기 5Algorithm/BOJ 2022. 6. 11. 14:00
[BOJ] 11660번 - 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 알고리즘 구간 합을 미리 DP로 구하여 둔 다음에 해당되는 행 영역의 합을 구하여준다. 계산상 편의를 위해 2차원은 N+1로 적용하였다. 코드 #BOJ 11660번 import sys input = sys.stdin.readline answer = [] n , m = map(int,input().split()..
-
[BOJ] 2170번 - 선 긋기Algorithm/BOJ 2022. 6. 11. 13:56
[BOJ] 2170번 - 선 긋기 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 주의할 점이 선을 긋는다고 하여 0부터 시작하는 것이 아닌 음수부터 시작이 된다 및 여러 번 그은 부분이나 한번 그은 부분이나 동일하게 계산되어야 한다. 알고리즘 그리디 알고리즘을 이용하여 풀었다. 시작점이 작은 좌표부터 시작하여 가장 긴 값을 찾아가는 형태로 찾아가면 최소 최대 길이를 구할 수 있다. 최소 값을 갱신하면서 찾아야 하기..
-
[BOJ] 2143번 - 두 배열의 합Algorithm/BOJ 2022. 6. 10. 14:47
[BOJ] 2143번 - 두 배열의 합 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 알고리즘 해당 범위 내에서 특정 값이 있는지 여부를 확인하기 위한 이분탐색 ( 정렬 필수 ) 1. A,B 각각의 경우의 수로 나타낸다. 2. B를 정렬한다. 3. A를 통해 B에서 해당되는 경우의 수가 있는지 이분탐색 4. 결과 출력 코드 #BOJ 2143번 import bise..
-
[BOJ] 15903번 - 카드 합체 놀이Algorithm/BOJ 2022. 6. 10. 14:11
[BOJ] 15903번 - 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 알고리즘 그리디로 생각하여 풀었다. 작게 만들기 위해서는 작은 두수를 뽑아내서 갱신시켜주어야 한다. 이때 시간 복잡도가 가장 낮은 Heap을 이용 1. heapq를 이용하여 Data 초기화 2. 요청받은 갯수만큼 heapq 갱신 3. 갯수 출력 코드 #BOJ 15903번 import heapq n , m = map(i..
-
[BOJ] 1520번 내리막 길Algorithm/BOJ 2022. 6. 10. 13:07
[BOJ] 1520번 내리막 길 처음에는 DP와 BFS로 푸는 문제로 접근하였다. 생각하였던 예시 중에서는 올바르게 동작하였으나, 제출 시 시간 초과가 걸려 실패하였다. 왜 그런지 곰곰히 생각해보던 도중 BFS로 구현을 하게 되면 순차적으로 탐색을 하게 되어 돌아서 가는 경우에 대해서 갱신하여 처리하기 어렵다. 따라서 어차피 숫자 가중치에 따라 더 큰것부터 우선으로 찾아 들어가야하기 때문에 BFS의 Queue를 우선순위 Queue로 구현해볼까라고 생각하였다. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는..
-
[BOJ] 1253번 좋다Algorithm/BOJ 2022. 6. 8. 19:56
[BOJ] 1253번 https://www.acmicpc.net/problem/1253 알고리즘 문제 접근 : 이분 탐색 각 숫자에 대해서 이분 탐색 처리 맨 앞과 맨 뒤부터 하나씩 단계별로 줄여가면서 checking 다만, 중복 숫자에 대해서는 한번에 처리 코드 #BOJ 1253번 import bisect n=int(input()) datas = list(map(int,input().split())) datas.sort() answer = 0 i = 0 while i < n : left , right , target = 0 , n-1 , datas[i] temp = 1 while left < right : #예외 마이너스인경우 # 5 / -4 -3 -2 -1 0 if left == i : left +=..
-
[BOJ] 11000번 강의실 배정Algorithm/BOJ 2022. 6. 8. 18:32
[BOJ] 11000번 - 강의실 배정 문제 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 알고리즘 그리디를 이용한 알고리즘으로 생각하여 풀었습니다. 가정) 현재까지의 강의실 시간 중에 가장 빨리 끝나는 시간보다 늦게 끝난다면, 현재 강의실에 이어서 하면 된다. 아니라면 강의실 추가 1. 강의실 시간을 시작 시간 , 끝나는 시간으로 재정렬 2. 순차적으로 강의실 시간을 보면서 현재까지의 가장 빨리 끝나는 시간과 비교 3-1. 만약 빨리 끝나는 시간보다 시작한 시간이 더 작다면, 강의실이..