알고리즘 문제풀이

백준 12100번 - 2048(Easy) 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 40484 10624 5981 24.008% 문제 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 ..

백준 10429번 - QUENTO 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 254 120 106 49.533% 문제 Quento는 Q42에서 만든 게임이다. 이 게임의 게임판은 항상 3×3 크기이며, 오른쪽 그림과 같이 검정색 칸에는 숫자, 흰색 칸에는 +또는 -가 적혀져 있다. 게임판의 상단에는 만들어야하는 숫자 N과 사용해야 하는 숫자의 개수 M이 주어진다. 이제 숫자에서 스와이프를 시작해 +/-로 이동한 다음, 다시 숫자로 스와이프를 하고, 이런식으로 숫자를 M개 지났을 때, 결과가 N이 되어야 한다. 이미 방문한 칸은 재방문 할 수 없으며, 다시 지나가는 것도 불가능하다. 예를 들어, 7을 숫자 2개를 이용해서 만들려면, 4+3, 9-2는 가능하다. 하지만, 5+3..

백준 16234번 - 인구 이동 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 512 MB 22597 9112 4992 35.932% 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다. 위의 조건에 의해 열어야하는..

백준 11657번 - 타임머신 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 24640 2472 1534 16.807% 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이..

백준 1976번 - 여행 가자 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 10471 3988 3008 39.009% 문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이..

서로소 집합 ( Disjoint Set Unit, DSU ) 이란 ? 공통 원소가 없는 상호베타적인 부분 집합들로 나눠 진 원소들에 대한 정보를 저장하고 조작하는 자료구조. DSU는 해당 원소가 같은 집합 내에 포함되어 있는지 빠르게 확인하기 위해서 사용되는 자료구조이다. 공통 원소를 포함하고 있지 않는 집합이므로, 교집합 or 차집합 등의 연산은 불필요하다.(= 의미가 없다) 핵심 연산( Union - Find ) Union 연산 : 2개의 DSU를 하나의 Set으로 합쳐주는 연산 Find 연산 : 어떤 element 가 주어 질 때, 이 Element가 속해있는 집합의 대표원소를 반환 *대표 원소가 같다 -> 같은 서로소 집합 에 속해 있다는 것. Disjoint Set은 Array, Linked L..