https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net 시계의 침만 주어진 두 시계가 시간이 일치할 확률을 구하는 문제입니다. 주의할 점은 침이 일정한 규칙을 가지고 있지 않기 때문에, 1 2 3 4 와 4 2 1 3 은 possible을 가집니다. KMP알고리즘을 이용하여 간단히 구할 수 있습니다. (KMP라는 것을 생각하기 좀 어려웠다... 처음에는 각으로 계산하려했다) 우선, 입력값은 0
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 상어를 낚는 낚시왕은 다음과 같이 진행됩니다. 1. 낚시왕이 오른쪽으로 한 칸 이동한다. 2. 낚시왕이 있는 열에서 가장 가까운 상어를 잡는다. 3. 상어가 이동한다. 핵심은 상어가 이동함을 구현하는 것입니다. 특별한 알고리즘은 없지만, 최대 100 * 100 칸에 상어가 있을 수 있기 때문에 연산을 최소화하여야 합니다. 상어의 이동은 다음과 같습니다. 1. 상어는 마주보는 방..
https://www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 아이디어만 잘 떠올리면 어렵지 않은 문제였습니다. 조건은 다음과 같습니다. 0과 1로 이루어진 수이며 1으로 시작해야합니다. 그리고 자릿수는 100자리 이하인 수 중 입력으로 주어진 애들의 배수인 수를 구하는 것입니다. 예를 들어 17은 17 * 653= = 11101 을 만족합니다. 만족하는 수가 없다면 BRAK을 출력시킵니다 처음에 100자리면 최대 2^100 경우를 나눠야하나 싶었지만 어짜피 가능성 있는 녀석들만 계산해주면 되기 때문에 bfs를 사용하였..
백준 문제는 아니지만 이번에 과제로 퀵소트 구현하고 python의 메서드와 비교하라는 문제가 있어 간단히 정리해봅니다. 퀵소트는 기준이 되는 pivot 값보다 크고, 작음을 이용해 분리해주고, pivot을 제 위치에 넣습니다. 그리고 pivot보다 작은 애들에 대해 똑같이 정렬해주고, 큰 애들에 대해 똑같이 정렬해줍니다. (이번에 하면서 머지소트를 폰 노이만이 만든 것을 알게되었다. 일반적으로 퀵소트가 더 빠르지만 최악의 상황이 발생하지 않는 머지소트. 역시 갓 노이만) 코드는 다음과 같습니다. (과제가 csv 파일 불러와서 시간, 메모리 측정하고, 정렬하는 거라 함수만 보면 됩니다.) # 랜덤한 리스트 (100만개 원소) 오름차순 (ex. 1 2 3 4 5) 정렬 퀵소트 import time # 시간 ..
https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 자기 전에 간단한 문제를 풀어보았습니다. 애들을 줄 세우는데 최소 몇 번 옮겨서 줄을 다시 맞출 수 있는지를 구하는 문제로, LIS 와 동일합니다. 학생들이 3 7 5 2 6 1 4 로 줄을 서 있다면 맨 앞에 학생부터 자기가 최대 몇 번 째 증가 수열의 원소가 될 수 있는지 구하면 됩니다. 3 => 1 7 => 2 5 => 2 2 => 1 6 => 3 1 => 1 4 => 2 이므로 6번 학생이 마지막..