목록자바 (15)
시간이 NullNull
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 처음에 이 문제를 보고 TRIE 알고리즘을 떠올렸으나... 오늘 더 공부해보면서 약간 느낌만 알았으므로 다른 방법으로 푼 방법을 올리겠습니다. 이 문제의 경우 사실 시간만 충분하다면 모든 경우를 다..
장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 처음에 그 높이만 물에 잠기는 줄 알고 많이 틀렸었다. 문제를 잘 읽도록 하자... ( 오랜만에 알고리즘 하니까 재미는 있지만 어렵네요 ㅠ ) 1. 생각해보면 비가 내리지 않았을 경우? 혹은 최소 높이보다 비가 작게 내렸을 경우? 안전 영역의 최소 값은 1이 된다. ( Key point) ( 내 생각에는 문제의 오류라고 생각한다. 최소 높이가 1이라면 비가 내리지 않았다가 된다. ) ( 이 생각 때문에 몇번 틀렸다. ) 2. 비는 최소 높이 부터 최고 높이의 - 1 까지만 내리는 것을 확인하면 된다. ( 최고 높이 이상으로 내릴 경우 어차피 안전영역은 0 이다. 최소 안전 영역이 1이 되는 것을 위배한다. ) 3. ..
문자열 P는 스스로를 계속 복제해서 매우 긴 문자열이 되었다. 복제하는 방법은 다음과 같다. P0 = “0” Pi+1 = Pi + “0” + f(g(Pi)) 여기서, f(A) 함수는 문자열 A의 모든 문자를 반전시킨다. 예를 들어서, f(“10110”) = “01001”이다. g(A)함수는 문자열 A를 좌우 반전 시킨다. 예를 들어서, g(“10110”) = “01101” 이다. 위와 같은 복제 방법을 무한히 반복한 문자열 P의 K번째 문자가 무엇인지 구하여라. P1 = “001” P2 = “0010011” P3 = “001001100011011” 위와 같이 복제가 이루어질 것이다. 따라서 3번째 문자는 1, 7번째 문자는 1, 10번째 문자는 0이다. 이 문제는 문자들의 규칙을 보고 점화식만 세워서 ..
콩을 사랑하는 민석이의 취미는 n*m 크기의 사각형 밭에 콩을 늘어놓는 것이다. 한 칸에 콩 하나씩을 놓을 수 있는데, 2가 싫은 민석이는 콩들 사이의 길이가 2가 되지 않도록 하면서 최대한 많은 콩을 놓으려고 한다. 예를 들어 다음과 같이 콩을 배치할 수 없다. 콩1(x1, y1)과 콩2(x2, y2) 사이의 길이는 이다. 민석이를 도와서 사각형 밭에 최대로 콩을 늘어놓자. 이 문제의 경우 처음에는 콩을 배치하고 규칙을 위반하였는지 확인하여하지 않았다면 모든 경우 중에서 규칙을 위반하지 않고 콩이 최대로 많은 경우가 생길 때 콩의 개수를 세는 것이라 생각하였다. 하지만 밑에 가로와 세로의 길이가 주어지게 되는데 최대가 각각 1000이며 이경우 1000 * 1000 이 되어 결국 모든 경우를 다 보기엔 ..
N명의 사람들이 어떤 프로그래밍 대회에 참가했다. 대회에는 M개의 문제가 나왔다. 동철이는 이 프로그래밍 대회가 열렸다는 소식을 접했고, 간단한 웹 서핑으로 각 사람들이 문제를 풀었는지 아닌지를 나타내는 NⅹM 개의 값 ai,j를 구할 수 있었다. 사람에 1에서 N까지의 번호를 붙이고, 문제에도 1에서 M까지의 번호를 붙일 때, ai,j 는 대회가 끝나고 i번 사람이 j번 문제를 풀었다면 1, 풀지 못했다면 0을 가지는 값이다. 동철이는 이 대회에는 나가지 못했지만, 다른 프로그래밍 대회에 나갈 계획이고 목표는 우승이다. 그러므로 지금 열린 이 대회에서 1등을 한 사람들을 찾아 라이벌로 삼기로 했다. 이 대회에서 모든 문제의 점수는 같고 프로그램을 제출한 시간은 따지지 않는다. 그러므로, 푼 문제 수가 ..