Jun's TID

일단 문제의 핵심은 조이스틷의 조작 횟수의 최솟값을 구하는 것이다. 즉, 만들어야할 문제가 어느 방향으로 움직여야 하는 지 정해야한다. 문제에서 문자는 모두 대문자로 주어진다고 했으니, 아마 아스키코드 값을 이용하여 판단하면 될 것이다. 표에서 A ~ Z가 65 ~ 90이므로 78번인 N을 기준으로 N 뒤 문자들은 조이스틱을 아래로 조작하여 만들게 코드를 작성하면 풀 수 있다. ... 라고 매번 처음에는 생각한다. 그러나 여기서 반드시 생각하고 넘어가야 하는 아주 중요한 사항이 있다! A일때는 조이스틱을 조작하지 않아도 문자가 이미 완성되어 있는 상태이다. 즉, JAAAAAAAAAJ 라면 굳이 A들을 모두 거치고 가는 방법보다는 첫 문자를 입력 후 마지막 문자로 커서를 이동시켜 마지막 J를 입력하는 것이..

조건을 하나 정해놓고 근사치를 뽑을 때까지 반복하면 되는 전형적인 Greedy 문제이다. 체육복의 여벌이 있는 학생이 체육복을 도둑맞았을 때는 자신의 체육복을 써야 하므로, reserve 배열에서 빠져야 한다는 점을 제외하고는 크게 문제 될 게 없는 문제이다. 정석대로 풀면 이중 for문이 2번 들어가게 된다. 이, 삼중 for 문에 좀 많이 당해봤던터라...그 풀이가 좀 보기 싫어서 Set도 만들어보고, List도 만들어보고 했지만, 이 문제는 그냥 이게 정답이지 싶어서 포기했다...ㅎㅎ package com.choonham; class Solution { public int solution(int n, int[] lost, int[] reserve) { int answer = 0; int lostN ..

Greedy(탐욕) 알고리즘은 직전에 다뤘던 동적 계획법과 대조되는 개념으로, 큰 문제를 쪼갠 부분 문제를 전부 검토하여 정답을 도출하는 것이 아니라, 풀이를 진행하는 순간순간마다 최적이라고 생각하는 정답을 도출해내는 방법이다. 즉, 모든 경우의 연산을 전부 수행하여 "완전한 정답"을 찾기보다는 각 상황마다 최적이라고 생각하는 연산만 골라 수행하여 좀 더 빠르게 "근사치"를 찾는 기법이라고 할 수 있다. 예를 들어보면, 더보기 https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohi..

프로그래머스 연습 문제를 바로 들어가기 전에, 동적 계획법과 탐욕 알고리즘은 확실하게 짚고 넘어가야 할 거 같아서 따로 포스팅하기로 했다. 우선 동적 계획법 알고리즘부터 자세하게 다뤄보자. 1. Dynamic Programming? 동적 계획법이란 하나의 큰 문제를 쪼개어 부분적인 부분을 풀어 큰 문제를 해결할 수 있도록 고안된 알고리즘이다. 개념만 딱 들어보면 분할 정복과 다르지도 않은 것 같지만, 큰 차이점이 존재한다. 분할 정복 알고리즘은 큰 문제를 쪼개어 나온 부분 문제를 전부 해결하여 큰 문제에 대한 정답을 도출할 수 있었다면, 동적 계획법 알고리즘은 이미 도출한 부분 문제의 정답을 저장해놓았다가, 중복의 연산을 해야할 때 이를 스킵하고 저장한 값을 사용하여 좀 더 효율적인 연산이 가능하다. -..

딱 보자마자, "이건 뭐지..." 하고 한참을 생각한 문제이다. 각 격자의 개수는 기억해놓고 그 넓이를 기억을 못한다는 LEO.... 사실 복잡해보이지만, 진짜 단순하게 생각하면 결국 카펫의 넓이는 노란 타일 부분의 가로와 세로 부분에 각각 +2씩하여 넓이를 구하면 된다. 두 타일의 개수를 더하여 나온 타일의 총 개수 = 카펫의 넓이이므로, 노란 타일의 개수를 받아와 1부터 나누어가며 딱 나누어 떨어지면서 나눈 수와 몫을 곱했을 때 총 타일의 개수가 되는 순간, 도출한 가로와 세로 크기에 2씩을 더하여 추출하면 되는 문제이다. package com.choonham; class Solution { public int[] solution(int brown, int yellow) { int[] answer =..

이 문제를 오늘 오전 8시부터 보고 풀기 시작했는데... 처음에는 "17"이라는 문자열이 들어오면, 1부터 17까지의 소수의 개수를 구하는 문제라고 덜컥 생각하고 풀어버려서... 오전 풀이 시간을 날려버렸다... 하하.. 문제는 항상 2번씩 읽읍시다. 본질은 "17"이라는 문자열을 받으면 받은 문자열을 한자리 숫자로 쪼갠 뒤, 만들 수 있는 모든 숫자 조합에서 소수를 찾는 문제이다. 즉, 받은 문자열을 쪼개고, 배열에 넣은 뒤 수열을 구하여 풀어야한다. 수열을 만드는 알고리즘은 직전 포스팅에서 열심히 구현해 놨으니, 이제 쓰기만 하면 된다. package com.choonham; import java.util.ArrayList; import java.util.HashSet; import java.util..

완전 탐색 알고리즘에서 임의의 숫자로 되어있는 문자열을 준 뒤, 이 문자열에서 조합이 가능한 경우의 수를 뽑는 문제가 자주 나오는 것 같다. LV2 문제를 풀다가 도저히 선정리 없이는 풀기가 힘들고, 입사 코딩 테스트에도 등장할 개념 같아서 자세하게 다루고 넘어가려고 한다. {1,2,3,4,5,6,7}의 배열을 가지고 3자리의 수를 전부 뽑는다고 가정하면, {1, 2, 3}과 {3, 2, 1}을 같은 경우로 생각하냐 마냐의 2가지 경우로 나눌 수 있다. 1. 중복을 허용하는 수열 뽑기 수열은 123을 뽑는 경우와 321을 뽑는 건 다르다고 생각하는 경우이다. 즉, {1,2,3,4,5,6,7} 중 3개를 뽑는 "모든" 경우의 수를 구하는 개념이다. 재귀함수를 이용하여 코드를 작성하면, private sta..

완전 탐색을 푸는 첫날인데, 아침부터 굉장히 마음에 드는 문구를 봤다. 네, 무식한 게 최곱니다. ㅎㅎ 가끔 무지성으로 푼 풀이가 딱 들어맞으면, 그거만큼 기분 좋은 게 없어요. 아무튼, 문제로 들어가면 수포자 1, 2, 3 의 찍는 패턴을 배열로 저장한 뒤에 인자로 받은 정답의 배열과 하나하나 비교하여, 각자 몇 문제를 맞혔는지 확인하면 되는 문제이다. 사실 완전 탐색은 말 그대로, 모든 경우의 수를 다 탐색하면 끝인 문제들이라, 효율적인 검색 방법을 찾는 것을 제외하고는 딱히 복잡하게 생각할 게 없는 거 같다. 나머지 연산과 문제를 가장 많이 맞힌 1등 수포자 여러 명일 수도 있는 경우를 생각하여 코드를 작성하면 된다. package com.choonham; import java.util.ArrayL..

"생각보다 간단했다." 고 말할 뻔했다. 인용 횟수를 저장할 h와 해당 h값보다 큰 인용 횟수를 가진 정수의 개수를 가지는 n을 선언해준 뒤, citations 배열을 오름차순 정렬해주고, h 값에 해당하는 iterator를 ciataions의 길이에 빼주면 h보다 큰 수의 개수를 구할 수 있고, h의 최대 값은 n이 h보다 같거나 커지는 최초의 순간이므로, 그렇게 코드를 작성해주면 끝날 줄 알았다. package com.choonham; import java.util.Arrays; class Solution { public int solution(int[] citations) { int answer = 0; int h = 0; int n = 0; Arrays.sort(citations); for(int..

어....꽤나 어려운 문제가 걸린 거 같다. 첫 인상은 어제 풀었던 Heap LV3보다 더 생각할 것이 많아 보였다. 처음에는 하나하나 붙여서 따로 배열을 생성한 뒤 내림차순으로 정렬하여 String변환 후 내보내는 코드를 짜려고 했는데... 이게 테스트케이스 2번 같은 경우만 해도, 나올 수 있는 경우의 수가 5 x 4 x 3 x 2 x 1 = 120 이 나오는 미친 효율성을 보여줄게 뻔해서...포기했다. 다시 처음으로 돌아와서 애초부터 String Array로 변환을 시킨 후에 내림차순 정렬을 하는 방법을 생각해봤지만, 문자열은 첫번째 자리가 큰 순서, 문자열이 긴 순서로 정렬이 되기 때문에 테케 2번에 9534303이 나와버린다...하하... 한참을 고민하다가, Sort의 기준을 두 인자를 합친 값..