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 문제들과 동일하다. 바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다. 행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 ..
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 3 16을 예로 들어보자. 3부터 16까지 검사하면서 현재 숫자가 소수이면 출력해주는 구조인데, 그냥 구하면 시간초과가 발생할 것이다. 그리고 1은 좀 특별하게 예외처리를 해주어야 한다. 왜냐?? 1은 소수가 아니지만, 소수 판별 알고리즘에 걸리지 않아 소수로 판별되기 때문이다! 2부터 n의 제곱근까지 i를 증가시키면서 혹시 딱 나눠 떨어지는 수가 있다면, 소수가 아니므로 False를 반환하고, 검사에 걸리지 않았다면 True를..
https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net x,y 좌표쌍을 여러 개 입력 받고, 정렬하는 문제이다. x좌표에 대해 오름차순으로 정렬하고, 만약 x좌표 값이 동일하다면 y좌표 값을 기준으로 오름차순 정렬해주면 된다. 사실 파이썬 정렬의 기본값은 오름차순이라, 아래 코드처럼 정렬 기준을 정해주지 않아도 되지만 쓸 경우가 반드시 있을 것이라 생각하므로 알아두면 좋을 것 같다! Key가 의미하..
