인생은 파도타기

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

문제 문제의 요구사항은 결국 길이 (갯수)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

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

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

문제 설명 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요. 제한 조건 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 입출력 예 abresult 5 24 "TUE" class Solution { public String solution(int a, int b) { String answer = ..

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예participantcompletionreturn ["leo", "kiki",..