1. 문제 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 2. 풀이 배열의 모든 부분 집합을 구하여 값을 계산한다면, 배열 하나만 해도 시간 복잡도 $ O(2^n) $를 가지기 때문에 시간초과가 발생한다. 이 문제의 핵심 포인트는 "누적합"을 구하는 것이다. 그렇다면 A 배열과 B 배열의 누적합의 개수는 몇 개씩이 나올까?? A 배열에서 누적합의 개수는 총 n개가..
1. 문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 2. 풀이 Point 이분 탐색 + BFS를 사용하여 해결 주요 자료구조 List[] inList : 인접리스트 long min : 주어진 간선 중 최솟값 long max : 주어진 간선 중 최대 값 boolean[] visited : 방문체크 배열 각각의 다리에 가중치가 부여되어 있고, 이 가중치를 넘지 않으면서 공장 -> 공..
1. 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2. 풀이 용액의 특성 값의 범위가 -10억 ~ +10억 까지이므로 int형으로 하면 범위를 초과하므로 합을 구하는 변수나 long형으로 선언한다. (10억 + 10억 + 10억 = 30억 OR (-10억) + (-10억) + (-10억) = -30억이므로 int의 한계인 -21억 ~ +21억의 범위를 넘는다.) 주요 자료구조 List numList : 용액의 특성..
1. 문제 https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 2. 풀이 백준 알고리즘 분류에서 이분 탐색으로 분류되어 있다. 과자의 길이는 양의 정수이므로 막대과자의 초기 값은 1로 잡고 이분 탐색을 실시한다. mid 값을 구한 후 입력으로 주어진 과자 길이를 탐색하면서 탐색한 값을 mid 값으로 나눈 몫을 cnt에 더한다. 이 cnt의 값이 입력으로 주어진 조..
1. 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 2. 풀이 이분탐색을 활용한 골드V 문제이다. 문제를 풀면서 이분탐색의 Upper_bound, Lower_bound가 정확히 기억이 나지 않아 글을 찾아보면서 문제를 해결했다. https://blog.naver.com/bestmaker0290/220820005454 알고리즘 기초 - Lower Bound & Upper Bound Low..
1. 문제 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 2. 풀이 이분탐색을 이용하는 문제이다. 각각의 테스트 케이스 별로 A 배열과 B 배열이 주어졌을 때 선택 당해지는 배열인 B 배열을 정렬한 후 이분탐색을 진행한다. 탐색의 대상은 B 배열의 인덱스인데 이때의 핵심은 탐색이 끝났을 때 결과인 index 값이 선택된 A의 값보다 작은 B 요소의 개수라는 것이다. 탐색이 끝났을 때 B[in..
1. 문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 2. 풀이 이분 탐색을 활용한 문제이다. 문제를 해결하면서 탐색을 해야할 대상을 어떻게 잡아야 할지 생각을 해도 모르겠어서 다른 분들의 풀이를 참고하였다. 이 문제에서 탐색해야 할 것은 블루레이의 크기이다. 입력 값이 예제 입력 1과 같고 블루레이의 크기가 10이라고 가정해보자. 앞에서부터 레슨을 더해본다면 1 + 2 + 3 + 4 = 10 다음에 5를 더하면 15가 되기 때문에 하나의 블루레..
1. 문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이 이분탐색을 활용한 문제이다. 오랜만에 풀어서인지 개념이 기억나지 않아 찾아보던 중 좋은 분의 글이 있어서 참고하였다. https://www.acmicpc.net/blog/view/109 이분 탐색(Binary Search) 헷갈리지 않게 구현하기 개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo
