📂 알고리즘_문제풀이

[백준 BOJ / JAVA] 두 배열의 합 (2143번)

📘 1. 문제 소개 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. 이분 탐색을 이용한 풀이 🧵 1. 풀이 간단하게 생각해 보면 다음과 같은 방법을 떠올릴 수 있다. A와 B의 부 배열의 합을 구한다. A의 부 배열의 합을 반복문으로 돌면서, B의 부 배열의 합에서 이분 탐색을 이용하여 T를 만들 수 있는 값을 찾는다. (물론 B의 부 배열의 합을 기준으로 반복문을 돌아..

[백준 BOJ / JAVA] 멀티버스 Ⅱ (18869번)

📘 1. 문제 소개 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 📘 2. 풀이 🧵 1. 좌표 압축 문제의 포인트는 좌표 압축이다. 좌표 압축이란 좌표 값들을 작은 범위의 값으로 압축하는 것이다. 수의 값에 상관없이 수의 대소관계만 알면 될 때 사용할 수 있다. -100, -4, 0, 3, 5000이라는 좌표가 있다고 해보자. 이를 배열처럼 표시한다면 다음과 같다. -100 ... -4 ... 0 ... 3 ... 5000 존재 존재 존재 존재 존재 하지만 압축을 이용하여 대소관계만 파악한다면 다음과 ..

[백준 BOJ / JAVA] 괄호의 값 (2504번)

📘 1. 문제 소개 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 📘 2. 풀이 해당 문제는 일반적인 스택 문제에 값을 구하는 문제가 더해진 문제다. 괄호를 이용한 일반적인 스택 문제에 대한 설명은 아래 문제를 참고하도록 하자. 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net ..

BOJ 14865 - 곡선 자르기 [JAVA]

14865번: 곡선 자르기 컴퓨터 그래픽 캔버스는 컴퓨터 화면에서 그림을 그릴 수 있는 직사각형 영역을 말한다. 캔버스는 2차원 좌표 평면처럼 각 점의 위치를 좌표로 표시한다. 캔버스의 정중앙 점이 원점 (0,0)이고, www.acmicpc.net 해당 문제는 스택(괄호 문제)을 이용하는 것이다. '스택'이라는 아이디어를 떠올리기 전까지 정말 많은 시도를 했을 것이다. 필자도 여러 방법(y축을 기준으로 상승 또는 하강하는 경우, 덮개를 고려하는 경우)을 시도해 보았다. 하지만, 예외 케이스들이 너무 많아서 스택이 아닌 다른 방법을 사용하는 것에는 많은 어려움이 있을 거라고 생각한다. 우선 감을 빨리 잡기 위하여 '곡선 자르기' 문제와 괄호 문제가 어떻게 같은지 그림을 통해서 알아보자. 하나의 봉우리에 대..