구현해 보는 이유 C++ 헤더 에 lower_bound와 upper_bound 함수가 있다. 근데 있는 거 두고 굳이 왜 직접 구현해 보는 걸까? 이유는 총 2가지이다. 1. 학습적인 목적(이진탐색 구현) 2. 이진 탐색 변형 이 목적으로 한번 구현해 본다. lower_bound와 upper_bound 메서드 lower_bound lower_bound는 찾고자 하는 값보다 크거나 같은 값이 처음 나타난 곳의 인덱스를 반환한다. 예를 들어서, {2,4,6,7,9}에서 lower_bound를 사용하여 2를 찾는다면 배열에서 2의 인덱스인 0을 반환한다. 또한 5를 찾는다면, 처음으로 5보다 큰 6의 인덱스인 2를 반환한다. upper_bound upper_bound는 찾고자 하는 값보다 큰 값이 처음 나타난..

문제 이해 단계 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20 30,50}이고, 길이는 4이다. 문제 접근 단계 특이점 알아내기 가장 긴 ~ 부분 수열 시리즈 문제 항상 비슷하면서 풀이가 다른 게 해당 시리즈 특징이다. 일단 수열..

문제 이해 단계 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048이라는 게임이 존재한다. 이 게임 상하좌우 이동 중 하나를 고르는데, 한번 이동할 때 모든 블록이 해당 방향으로 벽이나 다른 블록에 부딪힐 때까지 움직인다. 이때 같은 값을 가지는 두 블록이 충돌하면 두 블록은 하나로 합쳐지면서 값도 하나로 합쳐진다. 한 번 이동할 때 이미 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다. 이러한 게임에서, Nx..

문제 이해 단계 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 높이 h와 너비 w를 가진 2차원 맵이 존재한다. 여기서 원하는 것은 문서를 최대한 많이 획득하는 것이다. '. ' : 빈 공간 ' * ' : 벽 ' $ ' : 문서 알파벳 대문자 : 잠겨 있는 문 알파벳 소문자 : 열쇠 해당 문자의 대문자에 해당하는 문을 열 수 있음 처음에는 빌딩 밖에 있고, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 그리고 같은 열쇠를 여러 번 사..

문제 이해 단계 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 팰린드롬은 좌우가 대칭되는 숫자로 이루어진 수열을 뜻한다. 예를 들어 (1,2,3,2,1), (1,3,1) (3) 등이 해당된다. N개의 수열이 주어지고, 총 M개의 (S, E) 쌍이 들어온다. 이는 S번호부터 E번호까지로 이루어진 수열이 팰린드롬인지를 판단하는 것이다. 팰린드롬이면 1, 그렇지 않으면 0을 출력한다. 문제 접근 단계 일단 제한사항부터 살펴보자. 수열의 크기 N은 최대 2,000까지이다. 정수는 최대 1..

문제 이해 단계 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 행렬 N개를 곱하는데 곱하는 순서에 따라 값이 달라진다. 행렬 N의 크기가 주어졌을 때, 곱셈 연산 횟수의 최솟값을 구하는 문제곱셈 연산을 하는 방법은 크기가 NxM인 행렬 A와 MxK인 행렬 B가 있을 때, AxB = N x M x K를 크기로 계산한 후 행렬은 N x K가 된다. 입력은 무조건 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다. 문제 접근 단계 ..

문제 이해 단계 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2차원 좌표 평면 위의 2개의 선분 L1과 L2가 주어진다. 두 선분이 교차하는지 아닌지를 판단하는 문제. 교차하면 1, 그렇지 않으면 0을 출력한다. 입력으로 L1의 양 끝 좌표(x1, y1) (x2, y2) L2의 양 끝 좌표 (x3, y3) (x4, y4)가 들어온다. 문제 접근 단계 문제 조건에서 시간제한이 0.25초로 상당히 짧은 것을 볼 수 있다. 그리고 두 좌표를 연결하는 선분 L1, L2이기 때문에 일차함수라는 것을 알 수 있..

문제 이해 단계 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 접근 단계 1번부터 ~N번까지 N명의 학생들을 키 순서대로 줄을 세운다. 입력을 키를 비교한 두 학생의 번호 A, B가 M개 들어온다. 이는 A학생 뒤에 B학생이 서야 한다는 의미이다. 학생들을 앞에서부터 줄을 세운 결과를 출력하는데, 답이 여러 가지인 경우에는 아무거나 하나 골라서 출력한다. 문제 구현 단계 일단 제한사항부터 살펴보..