인생은 파도타기

개요 그리디 (greedy) 알고리즘이란 현재 상황에서 지금 당장 좋은 방법으로만 풀이를 해나가는 것을 그리디 알고리즘이라고 합니다. 그리디 알고리즘의 핵심은 정당성 분석을 통한 풀이 입니다. 단순히 가장 좋아보이는 것만을 반복해도 최적의 해가 나올 수 있는지 검토해야 합니다. 출처 이것이 코딩테스트다 예시 루트 노드부터 시작하여 거쳐가는 노드의 값들의 합을 최대값으로 구하고 싶을 때 최적의 해를 구하려면 어떻게 해야할까요? 최적의 해는 5 - 7 - 9 노드일겁니다. 하지만 그리디 알고리즘은 현재 상황에서 가장 큰 값만 선택하게 되는 경우입니다. 그러므로 보통은 5 - 10 - 4노드를 선택합니다 그렇다면 이 경우 최적의 해가 아니게 됩니다. 일반적인 상황에서 그리디 알고리즘은 최적의 해가 보장받을 수..

문제 설명 숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다. 예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무..

문제 설명 "명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다. 이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수..

문제 문제의 요구사항은 결국 길이 (갯수)N 의 카드와 길이 (갯수)M 의 카드를 비교해 일치하는 index 는 1 아니면 0을 출력한다. 맨처음엔 이분탐색 문제인지도 모르고 그냥 단순히 완전탐색으로 찾으려고만 했다.. import java.util.*; public class main { public void card() { List aList = new ArrayList(); List bList = new ArrayList(); String result = ""; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); for(int i=0; i

이번 포스팅에선 지난 재귀함수 1편에 이어서 공부해보겠습니다! 재귀함수를 제거하거나 비재귀적으로 표현하려면 어떻게 해야할까요? 꼬리 재귀의 제거 메서드의 꼬리에서 재귀 호출하는 메서드 recur(n-2)라는 말은 '인자로 n-2를 전달하여 recur 메서드를 호출한다.' 는 의미 입니다. 따라서 이 호출은 다음과 같이 바꿀 수 있습니다. n 의 값을 n - 2로 업데이트하고 메서드의 시작 지점으로 돌아갑니다. static void recur(int n) { while (n > 0) { recur(n - 1); System.out.println(n); n = n-2; } } 이렇게 하면 메서드의 끝에서 실행하는 꼬리 재귀(tail recursion) 는 쉽게 제거할 수 있습니다. 일반 재귀의 제거 그런데 ..

개요 나는 현재 개발자로 솔루션회사에서 근무중인 주니어개발자이다. JAVA 언어가 베이스인 회사에서 자바와 스프링 프레임워크로 코딩하는 것은 당연하지만, 일을 할수록 공부하는 시간이 줄어들고 알고리즘등 혹시 나중에 코딩테스트가 필요할텐데 싶은 생각에 앞으로 꾸준히 문제를 풀어야겠다고 생각이 들어 문법은 건너뛰고 검색 알고리즘부터 재귀, 큐, 스택등으로 개념정리부터 해보려고 한다. 열심히 정리해보자! 선형검색(linear search) 간단하게 생각하자면 선형 = 일자로 쭉 늘어진 것 따위 일것이다. 그렇게 key 와 일치하는 값을 찾기위해 하나씩 검색하면서 진행하는 알고리즘으로 보통 for문이나 switch문으로 loop를 돌려서 index 를 증가시키며 찾는 것이다. 가장 단순한 알고리즘으로 구현하기도..

개념 큐(queue), 역시 스택과 비슷하게 데이터를 일시적으로 쌓아놓기 위한 자료구조입니다. 다만 차이점은 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 구조입니다. 실 생활에서 예를 들자면 마트의 대기열이나, 은행 창구에서 차례를 기다리는 순서라고 이해하면 편합니다. enqueue : 인큐 라고 불리며, 큐에 데이터를 삽입하는 작업을 뜻합니다. dequeue : 디큐 라고 불리며, 인큐의 반대로 데이터를 꺼내는 작업을 뜻합니다. front : 프런트는 데이터를 꺼내는 out 쪽을 뜻합니다. rear : 리어는 데이터를 넣는 쪽을 뜻하며 back이라고도 불립니다. 큐를 구현하기 쉬운방법은 역시 배열입니다. public class IntQueue { p..

링크 https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 문제 설명 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 ..

문제 설명 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다. 1478 → "one4seveneight" 234567 → "23four5six7" 10203 → "1zerotwozero3" 이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요. 참고로 각 숫자에 대응되는 영단어는 다음 표와 같습니다. 숫자영단어 0 zero 1 one 2 two 3 three 4 four 5 five 6 six 7 s..

코딩테스트 풀이.. 알고리즘이나 코딩테스트를 공부하지만 아직 너무어렵다.. 혼자풀기엔 힘들어서 구글링으로 블로그글중 이해하기 쉽게 쓴 글이 있어서 가져왔다. https://codevang.tistory.com/293 문제 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 ..