투투

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 접근 사이클이 완성되기 위해서는 최소 세 개의 점이 연결되어야 한다. 이를 유니온 파인드 알고리즘을 활용하여 해결할 수 있다. 입력되는 두 개의 점이 있을 때 한 쪽 점을 다른 쪽에 속한 집합으로 합친다. 이후에 두 개의 점을 입력받았을 때 루트 노드가 같다면 사이클이 완성되었다고 판단할 수 있다. 구현 - 아래와 같이 union와 find 연산을 함수로 만든다. def find(a): if..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 접근 이번 문제에는 상어들의 step 크기가 최대 1000이다. 따라서 최대 RxC 마리의 상어들의 모두 1000의 크기만큼 이동할 때 한 칸씩 이동하도록 구현하면 시간초과가 발생한다. 따라서 상어들의 step 크기를 줄여야했다. 이를 위해 규칙을 찾아보면 상하로 움직이는 상어들은 (R-1) x 2배, 좌우로 움직이는 상어들은 (C - 1) x 2배일 때 같은 자리로 돌아오게 ..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 접근 이번 문제에서는 특정 범위를 90도로 회전시키는 것을 구현하는 것이 가장 큰 문제였다. 먼저 board라는 원본 맵을 탐색하면서 입력받은 범위만큼 나누고 90도로 회전시키는 함수에 회전한 board를 다른 2차원 리스트에 저장하였다. 일단 1이 들어왔다고 가정하고 몇몇 범위를 예시로 어떻게 인덱스가 변하는지 파악하였다. 예를 들어 (0, 0)을 시작으로 2x2크기는 (0,..

문제 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100,000이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. 입력 첫째 줄에 N과 K를 입력하고 둘 째줄에는 N개의 숫자를 입력한다. N은 1이상 200,000이하, K는 1이상 100이하이다. 출력 조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다. 접근 투 포인터 알고리즘을 공부하기 위해 이 문제를 풀게되었다. 먼저 left와 right가 첫 번째 원소를 가리킨다. ..

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다. 접근 가장 긴 증가하는 부분 수열의 문제를 이분 탐색으로 풀면서 출력되는 부분 수..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 접근 먼저 사다리를 어떻게 모델링할 것인지 정했다. 사다리를 2차원 리스트로 표현하였다. 사다리를 타고 내려오다가 1을 만났을 때 오른쪽으로 이동하도록 하고, 왼쪽에 1이 존재하면 왼쪽으로 이동하도록 하였다. 따라서 2차원 리스트에서 1은 현재 위치와 오른쪽이 이어져있다는 의미이다. 이제 이를 활용하여 1번부터 N번까지 사다리를 타고 내려왔을 때 모든 열이 처음과 같은 위치를 가리키고 있을 때 ..

문제 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. 출력 첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다. 접근 입력받은 문자열에서 슬라이싱을 통해 접미사를 구하고 오름차순 정렬한다. 구현..

문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "le..

문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자. 입력 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. 출력 P가 S의 부분 문자열이면 1, 아니면 0을 출력한다. 접근 kmp 알고리즘을 적용하여 부분 문자열을 찾았다. 인덱스 i는 S, 인덱스 j는 P를 가리킨다고 했을 때 S의 길이만큼 i가 순차적으로 증가한다. j는 0부터 시작하여 S[i] == ..

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 접근 문자열 패턴을 찾는 알고리즘인 KMP를 공부하기위해 위의 문제를 풀었다. 일단 지금까지 KMP 알고리즘을 다음과같이 이해했다. 문자열 S에서 패턴 문자 P를 찾는다고 하자. 이를 S의 처음부터 탐색하고 다른 문자가 나왔을 때 다시 P의 처음부터 탐색을 하면 불필요한 중복이 발생한다. 따라서 P에서 각 인덱스까지의 문자까지 (ABCD가 있을 때 A, AB, ABC, ABCD) 최대 접미사..