본문 바로가기

728x90

알고리즘

(102)
[알고리즘][KOTLIN] 이진 탐색 정의 입력된 배열이 오름 차순 혹은 내림 차순의 배열일 때 선형 탐색보다 빠르게 검색할 수 있는 알고리즘 검색 방법 배열을 오름 차순으로 정열 한다. 배열의 중앙 값을 찾는다. 검색하고자하는 값과 중앙값의 크기를 비교한다. 3번에서 중앙값이 클 경우 중앙 값 기준으로 왼쪽의 배열로 검색 값을 찾는다. 3번에서 중앙값이 작을 경우 중앙 값 기준으로 오른 쪽의 배열로 검색 값을 찾는다. 4, 5 번 과정을 반복한다. 코드 import java.util.* fun main(args: Array) { val sc = Scanner(System.`in`) print("요소수 : ") val num = sc.nextInt() val x = IntArray(num) { sc.nextInt() } x.sorted() ..
[KOTLIN] 주어진 입력을 역순으로 출력하기 ### 문제 N 개의 입력이 주어진다. 각 수는 양의 정수가 값으로 100보다 작은 값이다. ### 출력 입력된 수를 역순으로 출력한다. ### 입력 첫 줄에는 입력의 개수이다. 다음 줄 부터 공백을 기준으로 N 개의 숫자가 입력된다. ### 예제 입력1 2 ### 예제 출력1 2 ### 예제 입력2 11 27 ### 예제 출력2 27 11 ### 예제 입력3 22, 57, 11, 32, 91, 68, 70 ### 예제 출력3 70, 68, 91, 32, 11, 57, 22 ## 풀이 import java.util.* fun main(args: Array) { val sc = Scanner(System.`in`) val N = sc.nextInt() val input = Array(N) { sc.next..
[KOTLIN][알고리즘] Brute Force(BF, 완전탐색) 정의 모든 경우의 수를 탐색하여 결과를 찾아내는 알고리즘 비교적 만들기 쉽고 접근법이 간단하다. 재귀 호출이나 For 문 같은 루프를 통해서 완전 탐색을 구현할 수 있다. 하지만 모든 경우의 수에 대해서 탐색을 하기 때문에 시간적인 효율성이 떨어진다. 따라서 시간 초과가 발생할 경우 좀 더 효율적인 탐색으로 구현해야 한다. 관련 문제 https://www.acmicpc.net/step/22
[BOJ][KOTLIN] 11729 하노이 탑 이동 순서 풀이 기둥 세개를 시작, 중간, 끝 위치로 설정한다. 3개의 탑을 옮길때 1, 2 를 하나의 묶음으로 생각하고 N = 2 와 동일한 이동으로 생각한다. 2번 과정을 통해서 아래와 같은 알고리즘 규칙을 도출 한다. hanoi(N - 1, start, mid, end) // N - 1 개의 원탑을 끝 기둥을 이용하여 중간 기둥으로 이동 hanoi(1, start, end, mid) // 1개의 원탑을 끝 기둥으로 이동 hanoi(N - 1, mid, end, start) // 첫번째에서 이동된 N - 1 원탑을 중간 기둥에서 시작 기둥을 이용하여 끝 기둥으로 이동 import java.io.* var count = 0 var result = mutableListOf() fun main(args: Array)..
[BOJ][KOTLIN] 1316 그룹 단어 체커 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다. 출력 첫째 줄에 그룹 단어의 개수를 출력한다. 예제 입력1 3 happy new year 예제 출력1 3 예제..
[BOJ][KOTLIN] 2941 크로아티아 알파벳 문제 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= 예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다. 입력 첫째 줄에 최대 100글자의 단어가 주어진다. 알파벳 소문자와 '-', '='로만 이루어져 있다. 단어는 크..
[BOJ][KOTLIN] 1152 단어의 개수 문제 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열은 공백으로 시작하거나 끝날 수 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 예제 입력1 The Curious Case of Benjamin Button 예제 출력1 6 예제 입력2 The first character is a blank 예제 출력2 6 예제 입력3 The last character i..
[BOJ][KOTLIN] 1157 단어공부 문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 예제 입력1 Mississipi 예제 출력1 ? 예제 입력2 zZa 예제 출력2 Z 예제 입력3 baaa 예제 출력3 A 풀이 입력된 문자열을 대문자로 변환한다. 변환된 문자열에서 사용된 알파벳을 알파벳 Array 에 저장한다. 초기 값은 0으로 설정 한다. 알파벳 Array ..