0과 1의 쉼터

풀이 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명의 사람이 중복해서 참여할 수 있는 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

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

풀이 스택이란 항아리 처럼 나중에 집어넣은 것이 먼저 나오는 제한적 접근 나열 구조이다. LIFO(Last In First Out) 형식이며, 기본 개념을 구현만하면 된다. 단, 한 줄에 하나씩 출력해야 한다는 것을 명심하자 pop 명령을 실행하기 전에 스택이 비었는지 확인하기 위해 empty 명령어만 함수로 구현했다. 실제 메모리에 대한 참조를 해제할 필요 없이, 변수 top을 사용해 값을 가르키는데 제한을 두었다. 소스코드 소스코드 보기 출처 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net..

풀이 가중치가 없는 방향 그래프가 주어질 때, 모든 정점 간 연결이 가능한지 아닌지를 탐색 후 인접 행렬 형식으로 표현해주면 된다. Floyd Washall 을 사용해서 풀이했다. 가중치는 없지만, 결국 모든 탐색 가능한 정점에 대해 정점 간 연결이 존재하는 경우 또 다른 정점간의 간접적 연결이 되기 때문이다. 단, 단순히 정점간의 간접적 연결에 대한 유무 판단만 하면 되기에 아래의 조건만 충족한지 살펴보자 소스코드 소스코드 보기 출처 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net

풀이 최대 100개의 카드 중에서 3장의 카드를 고를 수 있는 모든 경우의 수를 탐색해도 제한 시간 내 합을 출력할 수 있다. 3개의 카드를 골라야 하니 3중 loop을 사용해 탐색하자. loop의 조건이 순서대로 1씩 감소하는 이유는, 최악의 경우 중복된 카드를 뽑지 않고서는 N - 2 ~ N 번째 카드를 선택했을 때가 조건에 맞는 최댓값이 나오는 경우이기 때문이다. 소스코드 소스코드 보기 출처 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net