목록알고리즘 (41)
시간이 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. 곱..
길이 N의 순열이란, 1부터 N까지의 자연수를 적당한 순서로 섞어서 만든 수열을 의미한다. 예를 들면, (3, 4, 1, 2)는 길이 4의 순열이다. (2, 3, 4, 4, 5)는 길이가 5이지만 1부터 5까지의 자연수를 적당한 순서로 섞어서 만들 수 없기 때문에 순열이 아니다. 어떤 길이 N의 수열이 주어지면, 이것이 길이 N의 순열인지 판단하여라. 너무 간단하다.. 컴파일러 없이도 그냥 메모장에 코딩하고 그대로 붙여서 제출하여도 통과할만큼 이건 D1, D2 문제이라 해도 믿을 것이다.... 사실상 순열이라고 하였지만 N을 입력받으면 1~N까지 숫자가 다 있는지 확인만 해주면 끝나는 문제이다.... 그래서 설명이랄 것도 없다.... 코드를 보세요... import java.io.BufferedReade..
아기 광직이는 열심히 받아쓰기를 했지만, 아직 알파벳을 다 떼지 못했다. 아기 민정이는 그런 광직이가 반 친구들에게 놀림 받지 않을까 걱정이 되어 직접 학습지를 만들어 광직이에게 알파벳을 가르쳐 주려고 한다. (아기 민정이는 광직이보다 동생이지만, 알파벳을 잘 알고 있다.) 민정이는 광직이가 따라 적을 수 있도록 알파벳 연습용 단어 세트를 여러 개 만들 것이다. 광직이는 현재 N개의 영어 단어를 알고 있고, 이 중 몇 개를 골라 하나의 세트로 만드는데, 각 세트 안에 포함된 단어의 순서는 중요하지 않다. 광직이가 모든 알파벳을 골고루 공부할 수 있도록, 단어 세트에는 26개의 알파벳 소문자가 모두 포함되어 있어야 한다. 즉, 모든 알파벳 소문자에 대해, 단어 세트 안에 그 문자를 포함하는 단어가 적어도 ..