본문 바로가기

algorithm

[algorithm] 좋은 단어 좋은 단어 문제이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다. 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 갯수를 세는 것을 도와주자. 입력첫째 줄에 단어의 수.. 더보기
[algorithm] 문자열 폭발 문자열 폭발 문제상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이 때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 입력첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1.. 더보기
[algorithm] 탑 탑 문제KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높.. 더보기
[algorithm] ABC ABC 문제세 수 A, B, C가 주어진다. A는 B보다 작고, B는 C보다 작다.세 수 A, B, C가 주어졌을 때, 입력에서 주어진 순서대로 출력하는 프로그램을 작성하시오. 입력첫째 줄에 세 숫자 A, B, C가 주어진다. 하지만, 순서는 A, B, C가 아닐 수도 있다. 세 숫자는 100보다 작거나 같은 자연수이다. 둘째 줄에는 A, B, C로 이루어진 세 글자가 주어지며, 이 순서대로 출력하면 된다. 출력주어진 세 수를 주어진 출력 순서대로 출력하면 된다. 예제 입력1 5 3ABC 예제 출력1 3 5 문제 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.. 더보기
[algorithm] 2007년 2007년 문제오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오. 입력첫째 줄에 빈 칸을 사이에 두고 x(1≤x≤12)와 y(1≤y≤31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. 출력첫째 줄에 x월 y일이 무슨 요일인지에 따라 SUN, MON, TUE, WED, THU, FRI, SAT중 하나를 출력한다. 예제 입력1 1 예제 출력MON 문제 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public .. 더보기
[algorithm] 문자열 조합 문자열 조합 문제문자열이 하나 주어졌을때, 문자열의 각 문자들을 조합하여 만들 수 있는 모든 경우를 출력하는 프로그램을 작성하라.대문자 알파벳으로 이루어진 길이가 N인 문자열 (1≤N≤100) 입력 예제ABC 가능한 모든 문자열 출력 (알파벳순으로 출력, 각 문자열은 공백으로 구분) 출력 예제ABC ACB BAC BCA CAB CBA 문제 풀이package algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ private static String[] charData; private static char[] words; public stat.. 더보기
[algorithm] 배열 요소 중 누락된 부분 찾기 배열 요소 중 누락된 부분 찾기 문제임의의 크기의 배열 A[N-1]가 있다. 배열의 길이 N은 입력으로 받는다. 길이 N을 입력한 후 배열 A[N-1]의 배열 요소를 임의의 정수로 입력한다. A[N-1] 배열에 1 부터 N까지의 정수가 모두 들어가 있어야 한다고 가정한다면 입력된 배열에서 가정에 어긋난 값을 출력하라 1. 배열의 길이 N 2. 배열요소 N개의 값 입력 샘플5 1,2,1,3,2 출력 샘플(1부터 N 중에서 누락된 요소)4,5 문제 풀이package algorithm; import java.io.*; public class Main { private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.. 더보기
[algorithm] 팰린드롬 만들기 팰린드롬 만들기 문제앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “anonona”를 만들 수도 있고, “a”를 붙여서 “anona”를 만들 수도 있지요. 물론 S를 뒤집은 문자열을 S 뒤에 붙이면 항상 팰린드롬이 되므로, 결과 팰린드롬이 가능한 한 짧았으면 합니다. S가 주어질 때 S에서 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하세요. 입력입력의 첫 줄에는 테스트 케이스의 수 C(= 0; i--) { char.. 더보기
[algorithm] 크로아티아 알파벳 크로아티아 알파벳 문제예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 다음과 같이 변경해서 입력했다. 크로아티아 알파벳변경 č c= ć c- dž dz= ñ d- lj lj nj nj š s= ž z=예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다.단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. 입력첫째 줄에 최대 100글자의 단어가 주어진다. 알파벳 소문자와 '-', '='로만 이루어져 있다.문제 설명에 나와있는 크로아티아 알파벳만 주어진다. 출력입력으로 주어진 단어가 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. 예제 입력ljes=njak 예제 출.. 더보기
[algorithm] 반복되지 않는 첫 번째 문자 찾기 반복되지 않는 첫 번째 문자 찾기 문제문자열에서 처음으로 반복되지 않는 문자를 찾아내는 함수를 작성하라. 예를들어, "total"에서 처음으로 등장하는 반복되지 않는 문자는 'o'이며, "teeter"에서 처음으로등장하는 반복되지 않는 문자는 'r'이다. 입력첫째 줄에 문자열이 주어지고, 둘째 줄에 반복되지 않는 문자가 출력된다 출력첫째 줄에는 반복되지 않는 첫 번째 문자열이 출력된다. 예제 입력 total 예제 출력o 문제 풀이package algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; public class Main .. 더보기
[algorithm] KMP는 왜 KMP일까? KMP는 왜 KMP일까? 문제KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다. 또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다. 사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다. 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.두 번째로 짧은 형태는 만든 사람의 성의 첫글자만 따서 부르는 것이다. 예를 들면, KMP이다.동혁이는 매일매일 자신이 한 일을 모두 메모장에 적어놓는다... 더보기
[algorithm] 상수 상수 문제상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 숫자 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다. 상수는 수를 다른사람과 다르게 거꾸로 읽는다. 예를 들어, 734과 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 상근이가 칠판에 적은 두 수 A와 B가 주어진다. 두 수는 같지 않으며, 0이 포함되어 있지 않다. 출력첫째 줄에 상수의 대답을 출력한다. 예제 입력734 .. 더보기

티스토리툴바