목록전체 글 (44)
시간이 NullNull
본 프로젝트에서는 인도네시아 내의 모든 섬을 해저터널로 연결하는 것을 목표로 합니다. 해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 물리적으로는 연결되지 않는 것으로 가정합니다. 이 문제의 경우... 참 애먹인 문제입니다. 처음 접했을때는 어떻게 풀지 몰랐다가 나중가서는 아 그냥 완탐하면 되겠네 했다가.... 그 다음에는 문제 자체를 이해 못하여서 다익스트라로 다 방문도 해봤다가... 최근에 다시 그래프 문제를 공부하면서 크루스칼과 Union Find 알고리즘을 공부하기 시작하면서 문제가 이해되기 시작하고 해결할 수 있게 되었다. Union Find의 개념을 다른 글에 포스팅 하기 보다 여기에 몰아서 한번에 적도록 하겠다. 나는 다른 블로그들을 많이 보면서 이해하였지만 ..
당신은 프로포즈를 위해 촛불을 삼각형으로 배치하고 있다. 촛불을 K단 크기로 배치하면, 1단에는 K개의 양초, 2단에는 K-1개의 양초, …, K단에는 1개의 양초를 배치해서 총 (K(K+1))/2개의 양초가 필요하다. 당신이 사용할 양초의 개수 N이 주어질 때, 이 양초를 모두 사용하면 몇 단 크기의 촛불 삼각형을 만들 수 있는지 구하여라. 처음에 문제만 읽었을때 만들수 있는 촛불의 단이 최대 몇인지 구하는 것인지 알고 잠깐 고민했으나 각 테스트 케이스 마다 주어진 양초 N개를 모두 사용하여 만들 수 있는 촛불 삼각형의 단수를 출력한다. 만약 삼각형을 만드는 것이 불가능하면 -1을 출력한다. 출력에 이렇게 함정을 놔두어 헷갈리게 해두었다... 나만 그렇게 느끼나 처음에 문제만 보면 최대 몇개 만들 수 ..
N개의 양의 정수가 주어졌을 때, 이들 중 정확히 서로 다른 두 개의 정수 쌍을 고르려고 한다. 이 때, 두 정수를 고르는 데 있어서 특별한 제약 조건이 존재한다. 고른 서로 다른 두 정수를 x, y라고 하면, 두 정수의 곱 x*y는 10진수로 읽었을 때 증가하면서도 연속한 숫자들로 이루어져야 한다. 예를 들어 2, 23, 23456, 56789는 제약 조건을 만족하고, 21, 54321, 67890, 89012, 88, 889, 79는 제약 조건을 만족하지 않는다. 이 조건을 만족하는 모든 쌍 중, 두 정수의 곱이 최대화되는 쌍을 “최고의 쌍” 이라고 부른다. 최고의 쌍이 존재하는지, 존재한다면 이 쌍의 곱은 얼마인지 계산하는 프로그램을 작성해보자. 1. 정수 중 중복하지 않게 2개를 뽑는다. 2. 곱..