코드 한 줄

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 정수 배열(int array)과 정수 N이 주어지면, N번째로 큰 배열의 원소를 찾아라. 예제 } Input : [-1, 3, -1, 5, 4], 2 Output : 4 Input : [2, 4, -2, -3, 8], 1 Output : 8 Input : [-5, -3, 1], 3 Output : -5 이 문제는 “Quick Select”의 알고리즘을 사용하는 대표적인 문제이다. Quick select는 퀵 정렬(quick sort)를 이용하는 알고리즘이다. 퀵 정렬의 pivot을 정하고 1차 정렬을 하면 pivot의 원소 위치는 최종 정렬된 배열의 위치가 된다. 이것을 이용하여 모든 배열을 정렬 하지 않고, pivot의 값을 비교하여, 찾는 값에..

사용자 환경 : IntelliJ IDEA 2017.3.2 (Community Edition)Build #IC-173.4127.27, built on December 26, 2017JRE: 1.8.0_152-release-1024-b8 x86_64JVM: OpenJDK 64-Bit Server VM by JetBrains s.r.oMac OS X 10.12.6 콜라츠 추측이란? 어떤 수 n에 대하여 n이 홀수일 경우, 3을 곱하고 1을 더한다. n이 짝수일 경우, 2로 나눈다. n이 1이 될 때까지 반복하며 그 과정을 출력하는 프로그램을 만들어보자. 먼저, 본인은 다음과 같은 변수를 선언했다. private int N; private boolean tf; private int cnt; 입력받을 N과, wh..

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 정수로된 배열이 주어지면, 각 원소가 자기 자신을 제외한 나머지 원소들의 곱셈이 되게하라. 단, 나누기 사용 금지, 시간 복잡도 0(n) 예제 } Input : [1, 2, 3, 4, 5] Output : [120, 60, 40, 30, 24] 여기서 중요한 것은 나누기 사용이 안된다는 것과 O(n) 시간 복잡도여야 한다는 것이다. 여기 input 예제를 보면 Input a = [a[0], a[1], a[2], a[3], a[4]] output = [ a[1]*a[2]*a[3]*a[4], a[0]*a[2]*a[3]*a[4], a[0]*a[1]*a[3]*a[4], a[0]*a[1]*a[2]*a[4], a[0]*a[1]*a[2]*a[3] ] 그럼 여기..

사용자 환경 : IntelliJ IDEA 2017.3.2 (Community Edition)Build #IC-173.4127.27, built on December 26, 2017JRE: 1.8.0_152-release-1024-b8 x86_64JVM: OpenJDK 64-Bit Server VM by JetBrains s.r.oMac OS X 10.12.6 동전 거스름돈 알고리즘이란? 만약 1300원의 거스름돈을 손님에게 건네줘야 한다면 어느 조합으로 건네줘야 가장 적은 수의 동전을 건네주는가를 구하는 문제이다. 1300원의 경우, 500원짜리 2개, 100원짜리 3개로 총 5개가 가장 적은 수를 건네는 조합이다. public class CoinChange { private int ten; privat..

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 길이가 같은 두 문자열 A와 B가 주어지면, 서로 1:1 암호화가 가능한지 찾아라. 예제 } Input : "EGG", "FOO" Output : True // E->F, G->O Input : "ABBCD", "APPLE" Output : True // B->P, C->L, D->E Input : "AAB", "FOO" Output : False 이 문제는 해쉬맵(hashmap)을 써서 A의 문자를 B의 문자 매칭을 저장하면 된다. A의 문자가 해쉬맵의 키로 있다면, B의 문자와 해쉬맵의 있는 값과 비교한다. A의 문자가 해쉬맵의 키로 없다면, B의 문자가 해쉬맵의 값으로 있는지 확인하고 없으면 해쉬맵에 더해준다. bool solve(String..

사용자 환경 : IntelliJ IDEA 2017.3.2 (Community Edition) Build #IC-173.4127.27, built on December 26, 2017 JRE: 1.8.0_152-release-1024-b8 x86_64 JVM: OpenJDK 64-Bit Server VM by JetBrains s.r.o Mac OS X 10.12.6 먼저 유클리드 호제법이란? 두 정수의 최대 공약수를 구하는 방법 중 하나이며 최대 공약수를 구하는 방법은 다음과 같다. 매개변수로 a와 b를 받는다.b가 0이라면, a가 최대 공약수이다.b가 0이 아니라면, 매개변수로 b와 a%b를 받는다.반복한다. public int euclidean(int a, int b) { if(b == 0) { re..

먼저 1번 문제를 들어가면 다음과 같은 화면이 나온다. 가장 먼저, 소스를 확인해보자. 위 코드를 살펴보면 유저레벨이란 쿠키가 이 문제의 핵심이란 것을 알 수 있다. 그러나, 0부터 9의 값이 들어가면 유저레벨을 1로 초기화하며, 6보다 큰 경우에도 1로 초기화 한다. 마지막 if문을 보면, 문제를 풀기위해서 유저레벨을 5보다 크게 만들어야 한다. 5보다 크면서 6보다 크지 않아야 한다... 정답은 실수를 입력하면 된다. 크롬의 확장 프로그램은 EditThisCookie를 이용해 간단히 해결해주자. 유저레벨의 쿠키값이 1로 설정되어 있는 것을 볼 수 있다. 이를 5.5로 수정하여 체크를 하고, 새로고침을 해주면 다음과 같이 해결할 수 있다. 본인은 이미 풀었기 때문에 다른 화면이 나왔다.

사용자 환경 : macOS Sierra 10.12.6, Python 3.6.4, PyCharm 2017.3.4 build PC-173.4674.37. 인덱싱에서는 문자열 중에서 어느 위치에 있는 문자를 뽑아낼 때 사용했다. 그렇다면 파이썬 문자열 인덱싱에 대해 다룬 게시글에서 사용했던 예제인 "Life is too short, You need Python"이라는 문자열에서 단순히 한 문자만을 뽑아내는 것이 아니라 "Life" 또는 "You" 같은 단어들을 뽑아내는 방법은 없을까? 다음과 같이 슬라이싱 기법을 이용하면 간단하게 처리할 수 있다. >>> a = "Life is too short, You need Python" >>> a[0:4] 'Life' 눈치가 빠른 사람들은 이미 알겠지만, a[0:4]가..

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. String이 주어지면, 중복된 char가 없는 가장 긴 substring의 길이와 문자열을 찾아라. 예제 } Input : aabcbcbc Output : 3 // abc Input : aaaaaaa Output : 1 // a Input : abbbcedd Output : 4 // bced 이 문제는 해쉬맵을 사용하여 char와 char의 인덱스를 저장하여 풀면 된다. string의 각 char를 보면서 해쉬맵에 있다면 substring 시작점을 char의 인덱스+1 로 두면 된다. 그리고 현재 char의 인덱스와 시작점의 거리를 계속 계산하여 가장 큰 값을 리턴하면 된다. int longestSubstringLength(String s) { ..

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다. 정수 배열이 주어지면 0이 아닌 정수의 순서를 유지하며 모든 0을 배열의 오른쪽으로 옮겨라 예제 } Input : [0, 5, 0, 3, -1] Output : [5, 3, -1, 0, 0] Input : [3, 0, 3] Output : [3, 3, 0] 이 문제는 0을 오른쪽으로 옮기는 것보다 0이 아닌 정수를 왼쪽으로 옮긴다고 생각하면 쉽게 풀 수 있다. void solve(int[] input) { int position = 0; // 0이 아닌 정수가 들어갈 곳 for (int i = 0; i < input.length; i++) { if (input[i] != 0) { swap(input, i, position); position++; ..