Algorithm
-
[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] 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 +=..