0과 1의 쉼터

풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가장 긴 비연속 부분 수열의 길이를 알아내면 된다. 그렇다면, LIS는 어떻게 만들어 지는가? 기본적으로 위에서 언급했 듯 이전 요소보다 큰 요소가 나오면 된다. 문제의 입력에서 알 수 있듯 항상 증가만 하는 요소로 주어지지 않는다. 아래 그림을 보자. 입력받은 배열 A와, 배열에 대한 LIS 길이를 기록할 dp배열이 있다. 그 아래에는 단순히 이전 요소보다 큰 요소가 나오는 경우만 기록한 Increasing Subsequence이다. 첫 번째 경우 10 - 20 - 30 - ..

풀이 combination을 구현해 값을 출력하면 되는 문제이다. 다른 언어의 경우 bigInteger가 없으면 구현하기 까다롭지만, Python에서는 표준 라이브러리를 이용해 풀이할 수 있다. 문제에서 주어지는 최댓값인 100 C 50은 작은 편으로 빨리 풀고 넘기자. 날먹 츄르릅.. 소스코드 소스코드 보기 출처 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. [백준 1967] 트리의 지름 [Python] 에서 더 많은 정점을 입력받는 동일한 문제이지만, 이전 글의 풀이와 동일한 방법으로 문제를 해결할 수 있다. 다른 점이라 하면, 입력이 양방향 그래프로 주어지기 때문에 따로 처리하지 않아도 된다. 소스코드 소스코드 보기 출처 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. 트리의 지름이란, 트리에서 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 값을 의미한다. 즉, 문제에 나온 이미지처럼 임의의 두 정점을 길게 당길 때 가장 큰 원을 만들 수 있는 간선의 합이 트리의 지름을 의미한다. 그렇다면 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 정점은 어떻게 찾을까? 임의의 두 정점(x, y)과 간선의 가중치의 합이 최대가 되는 정점(v1, v2)의 관계에 있어 다음과 같다. (x, y) 두 정점 모두 (v1, v2)와 일치할 때 : 한 번의 탐색으로 정답을 구할 수 있다. (x, y) 중 하나의 정점(x)만 (v1, v2)의 (v1)과 일치할 때 : 한 번의 탐색으로 (v1)를 구할 수 있다..

풀이 정수 N이 주어질 때, N^2의 최소 배수를 출력하면 된다. 즉, N^2 를 출력하면 된다. TC가 최대 20만개로 빠른 입력을 받자. 소스코드 소스코드 보기 출처 15372번: A Simple Problem. For each test case, output a single line containing the integer K, the answer for that test case. www.acmicpc.net

풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(people)이 또 다른 파티에 참석하게 될 경우 지민이는 마찬가지로 진실만을 말해야 한다. Disjoint Set 구현 풀이 즉, 한 명이라도 진실을 아는 사람이 있는 파티(know_truth)에 참석한 사람들(people)의 Disjoint Set 관계 간 동일 그룹 및 동일 root node를 가지게 되는 것이다. 파티에 참석한 모든 인원을 공통 조상으로 묶어주자. M개의 파티는 진행되는 파티마다 새로 진실을 알게 되는 사람들이(people) 늘어날 수 있으니, 파티를 모두 마친 후 지민이가..

풀이 부터 시작해 주어진 M, N에 관련된 조건에 맞게 두 자연수를 1씩 증가(이 때 k도 1씩 증가) 해야 한다. 증가한 두 자연수가 이 되기 전에 와 일치하면, 그때의 k를 출력하면 된다. 기본적인 로직은 아래와 같다. 단순히 (M, N, x, y)가 (39999, 40000, 39999, 40000) 으로 주어져도 LCM(39999, 40000) = 1,599,960,000 이기에 위의 방식대로 모든 수를 다 구하면 시간초과가 발생할 것이다. 난이도가 실버1로 낮은 편이고, 주어지는 수 또한 작은 수에 해당되기에 중국인의 나머지 정리를 사용하지 않고도 풀이할 수 있다. 아래와 같은 풀이 과정을 통해 접근이 가능하다. 구하고자 하는 k는 이 가 되기 위해 (x = y)가 아닌 이상 M, N의 배수에 ..

풀이 뱀과 사다리 게임은 쉽게 출발지에서 주사위를 굴려 도착지까지 도달해야 하는 게임이다. 무조건 큰 숫자로 이동하는 '사다리'와 작은 숫자로 이동하는 '뱀' 이지만,'사다리-사다리' 보다 '뱀-사다리'가 더 빠를 수 있다는 점에 유의하자. 즉, 절대적으로 좋고(사다리) 안 좋은(뱀) 조건이 없다. 필자는 개인적으로 뱀을 좋아한다 (~쉬익~쉭) 그 때문에 이동 가능한 모든 칸에 대해서 탐색을 진행해야 한다. 다음 조건을 유의하자 주사위를 굴려 나온 수만큼 이동한 칸에 '사다리' 또는 '뱀'이 있을 때, 선택이 아닌 강제로 이동을 해야한다. '사다리'와 '뱀' 을 동시에 가지는 경우는 없다. 게임은 1회 이상 진행된다. 'N + M

풀이 입력받은 길이와 너비에 맞는 직사각형을 'X'로 출력해주면 된다. 각 TC마다 한 줄 개행 해주어야 한다. 소스코드 소스코드 보기 출처 10188번: Quadrilateral A quadrilateral is a 4-sided figure. For this program, print out a 4 sided figure using the capital letter X. The largest side will be 20, and the smallest side will be 1. www.acmicpc.net

풀이 두 수 A, B가 주어질 때 문제에서 정의된 D, S, L, R 명령을 사용해서 A를 B로 만드는 과정에서 사용한 명령을 순서대로 출력해주면 된다. 시간 제한은 6초로 넉넉한 편이기 때문에 Bidirectional Search 방식을 사용하지 않고, 기본 BFS 방식으로도 해결할 수 있다. 우선, 동일한 숫자가 만들어져 중복된 탐색을 방지하기 위해, 해당 숫자를 만들지 않은 경우에만 만들어줘야한다. queue에 해당 숫자를 만들기 위한 명령어를 set으로 묶어 넣어줘도 되지만, visited 배열에 넣어주기로 했다. 단 위의 방식을 사용할 경우 boolean값이 아닌, 문자열이 탐색 기준이 되기 때문에, 초기값과는 분명히 다른 시작값을 넣어주어야 한다. (초기값 : '-', 시작값 : '') que..