King of the Jungle Lion

문제링크: 13034번: 다각형 게임 (acmicpc.net) 13034번: 다각형 게임 N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다. 성관이와 홍준이는 다각형에서 게임을 하려고 www.acmicpc.net 이 문제는 두명이 다각형 게임을 플레이하는데, 둘 다 모두 가장 이상적으로 행동한다고 했을 때 누가 이기는지 구하는 문제이다. 여기서 다각형 게임이란 N개의 꼭짓점으로 이루어진 이루어진 볼록 다각형에서 턴마다 번갈아가며 점 2개를 골라 선분을 긋는데, 여기서 선분은 이미 그은 선분과 교차하면, 점에서라도 교차하면 안된다. 그렇게 번갈아 선분을 그어나가다가 선분을 더이상 그을 수 없는 상태가 되면 해당..

문제링크: 3878번: 점 분리 (acmicpc.net) 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 이 문제는 좌표평면 상의 여러개 하얀 점과 검은 점들이 있을때, 이 점들을 직선으로 분류할 수 있는지 없는지 판단하는 문제이다. 데이터적으로 보면 여러개의 데이터를 points로 좌표평면 위에 할당하고 이 데이터들을 분류할때 linearly separable 할수 있는지를 판단하는 문제로도 응용할 수 있곘다. 먼저 좌표평면 상 두 개의 그룹을 분류한다고 치면, 한 그룹과 다른 그룹의 범위가 겹치지 않으면 될..

문제링크: 14897번: 서로 다른 수와 쿼리 1 (acmicpc.net) 14897번: 서로 다른 수와 쿼리 1 첫째 줄에 배열의 크기 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 배열에 포함된 수가 1번째 수부터 주어진다. 수는 공백으로 구분되어져 있다. 배열에 포함된 수는 1,000,000,000보다 작거나 같 www.acmicpc.net 이 문제는 배열 A의 길이 N이 N

문제링크: 1420번: 학교 가지마! (acmicpc.net) 1420번: 학교 가지마! 첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. www.acmicpc.net 이 문제는 NxM 크기의 도시에 도현이의 위치와 학교의 위치와 벽의 위치가 주어졌을 때, 도현이가 학교에 갈 수 없게 하려면 최대 몇개의 벽을 세워야 하는지 구하는 문제이다. 최대 개수와 최소 개수를 생각해 보면 최소 개수는 도현이와 학교가 이미 분리된 위치에 있을 때 0, 따로 있을때 학교를 상하좌우로 막은 경우 4 이렇게 최소 0, 최대 4를 가질 수 있다. 이 ..

문제링크: 13547번: 수열과 쿼리 5 (acmicpc.net) 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 이 문제는 길이가 N인 수열에서 (i, j)가 입력인 쿼리가 주어졌을때 i번째 수부터 j번째 수까지 다른 수의 개수를 출력하는 쿼리를 구현하는 문제이다. 이 문제를 풀기 위해서는 mo's 알고리즘에 대해 알고 있어야 한다. mo's 알고리즘은 주어진 쿼리들의 순서를 오프라인 쿼리처럼 특정한 방법으로 배열 한 뒤, 이전의 쿼리의 답을 이용해 가며 다음 쿼리의 답을 구하는 방법이다. 여기서 ..

문제링크:11377번: 열혈강호 3 (acmicpc.net) 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 이 문제는 최대 유량을 이용해 푸는 문제이다. 기존의 풀었던 최대 유량 (또는 열혈강호 1) 에서 한가지 조건이 추가되는데, 기존에는 한 직원당 할 수 있는 일이 1개로 모두 같게 정해졌다면, 이번 문제는 모든 직원 N명중 K명은 특별히 2개의 일까지 할 수 있다는 조건이 추가된다. 내가 처음에 생각한 방법은 모든 직원에게 용량 2인 간선을 할당 해 주고, 기존..

문제링크:19585번: 전설 (acmicpc.net) 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 이 문제는 트라이를 이용하여 문자열을 탐색해 나가는 문제이다. 특이한 점으로는 color을 뜻하는 문자열 C개, name을 뜻하는 문자열 N개가 주어지고 팀 명이 주어지는데, 팀명이 반드시 color 문자열 + name 문자열 형식으로 이루어 져 있는지 판별해야 한다. C, N은 모두 최대 4000개까지 주어질 수 있고, color, name의 문자열 개수는 최대 1000자 이다. 팀의 개수 Q는..

문제링크:2367번: 파티 (acmicpc.net) 2367번: 파티 첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 이 값은 N보다 작거나 같은 음이 아닌 정수이다. 다음 N개 www.acmicpc.net 이 문제는 최대 유량을 이용한 문제이다. 최대 유량이란 그래프의 각 간선마다 최대로 흘려보낼 수 있는 가중치가 정해져있을 때, 시작 노드 (source) 에서 끝 노드 (sink) 까지 보낼 수 있는 가중치들의 최대 합을 구하는 문제이다. 최대 유량문제를 해결하는 방법에는 여러가지 알고리즘이 있지만 흔히 사용하는 에드몬드-카프 알고리즘을 사용해서 문제를 해결하였다. 각 간선이 보낼 수 있는 가중치를 capa..

문제링크:16903번: 수열과 쿼리 20 (acmicpc.net) 16903번: 수열과 쿼리 20 첫째 줄에 쿼리의 개수 M(1 ≤ M ≤ 200,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 주어진다. 입력으로 주어지는 x의 범위는 109보다 작거나 같은 자연수이다. 3번 쿼리는 하나 이상 주어진다. www.acmicpc.net 이 문제는 특이하게 배열 A에 원소 x를 추가하거나 원소 x를 제거하거나, 또는 임의의 k가 주여졌을때 A의 임의의 원소 x와 x XOR k 연산을 했을때 얻을 수 있는 최대값을 구해야 하는 문제이다. XOR연산을 하기 위해 원소 x가 주어지면 x를 이진수 배열의 str로 바꾸고, 바꾼 이진수 배열을 시간 복잡도 O(N)으로 처리하기 위해 str를 트라이 형태로 저장하였..

문제링크:13537번: 수열과 쿼리 1 (acmicpc.net) 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 이 문제는 길이가 N인 수열이 있을 때, 쿼리의 입력이 (i, j, k) 이렇게 주어지면 i번째부터 j번째 까지의 수열의 원소 중 k 보다 큰 값들의 개수를 출력하는 문제이다. 여기서 N의 최대값은 100,000, 쿼리의 개수의 최대값도 100,000 이기 때문에 불러오는 쿼리의 시간 복잡도를 O(logN) 선에서 처리해야 한다. 나는 전에 몇번 다루었던 merge ..