https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net N이 최대 100,000까지 입력이다. 하나하나씩 다 계산해가며 비교하면 100,000 x 100,000으로 1초안에 절대 풀 수 없게 된다. 그래서 이 문제는 이분탐색의 개념과 투 포인터를 활용한다. 우선, 배열을 쭉 오름차순으로 정렬한 뒤 (오름차순으로 정렬하면 음수는 절댓값이 큰 것이 앞에 오고, 양수는 절댓값이 큰 것이 뒤로 간다.) 두 개를 더 했을 때 ..
https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 어려워 보이지만 차근차근 따져보면 쉽게 풀리는 문제이다. 이 문제에서 가능한 연산은 오직 나누기3과 곱하기2 뿐이다. 그렇다면, 맨 앞에는 어떤 수가 와야할까? -> 인수3을 가장 많이 가지고 있는 숫자가 맨 앞에 와야한다! 왜 그럴까? 6 9를 예시로 보자, 6에서 9를 만들 수 있을까 라고 물어보면 답은 절대 불가능하다 이다. 15와 9를 예시로 들어도 마찬가지이다. 1. 곱..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 오랜만에 푼 bfs 문제이다. 보물의 위치가 정해져있지 않기 때문에, 브루트포스를 이용하여 보물의 위치를 정해주는 것이 필요하다. 모든 육지(L)에 대해 bfs 탐색을 진행해주는데, 첫번째 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이가 5라고 할 때, bfs함수는 5를 반환하고 ans 변수에 저장한다. 지도를 초기화해준뒤, 2번째로 만나는 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이..
https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net kmp 알고리즘에 관한 문제이다. kmp 알고리즘이란, 문자열 패턴 매칭을 O(nm)이 아닌, O(n+m)에 해결할 수 있도록 해주는 문제이다. 이 알고리즘을 이해하기 위해서는, 접두사 접미사의 개념과 pi라고 칭한 이동경로 테이블을 왜 만드는지에 대한 이해가 필요하다. 이동경로 table은, 패턴의 부분 문자열(길이 1~원래 길이까지)마다 접두,접미사가 최대로 겹치는 길이를 저장해둔 tab..
https://www.acmicpc.net/problem/4587 4587번: 이집트 분수 입력으로 주어진 분수 M/N이 다음과 같이 나타낼 수 있다면, D1, D2, D3, ...를 공백으로 구분해 출력한다. (D1 ≤ D2 ≤ D3 ≤ ....) www.acmicpc.net 이 문제 역시 알고리즘 수업에 나온 문제가 백준에 있길래 풀어보았다. 내가 아는 이집트 분수의 풀이법은 2가지다. 1. 현재 분수에서 뺄 수 있는 가장 큰 기약분수로 빼면서 구하기 2. 현재 분수 p/q를 뒤집어서 q/p로 만든 후, 이 q/p보다 큰 정수를 선택하고, 그 정수를 역을 취해 원래 분수에 빼주는 방법 2번 방법이 시간적인 측면에서 훨씬 유리하기 때문에, 2번으로 해보려다가 문제의 조건을 보고 1번 방법을 택했다. (..
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 알고리즘 수업에 나온 내용이 백준 문제에 있길래 풀어보았다. 우선 행과 열 값들을 저장해준다. 그런 다음 삼중 for문(O(n^3)) 을 이용해 값을 구해준다. 행렬곱셈의 순서는 다른 dp 문제들과 동일하다. 바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다. 행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 ..
