오지이 오지이

구현이 왜 어려울까?구현 문제는 이미 알고 있는 알고리즘이나 자료 구조를 응용하는 것뿐만 아니라 직접 문제를 해결할 수 있는 규칙을 세우고, 이를 코드로 만들어야 합니다. 규칙을 복잡하게 설정해야 할수록 또, 작성해야 하는 코드가 복잡할수록 구현 문제를 풀 때 실수를 많이 하게 됩니다.문제 나누어서 생각하기: 모듈화실수를 줄이는 가장 쉬운 방법은 모듈화하는 것입니다. 코드를 한 번에 작성하지 않고 역할별로 나누어 부분적으로 작성해 나가면 한 번에 한 가지만 집중할 수 있습니다. 모듈화의 핵심은 코드를 역할별로 나눈다는 것입니다. 코드 역할을 고려하지 않고 단순히 코드를 짧게 분리시키기만 한다면 오히려 로직을 따라가고자 이곳저곳 옮겨 다니며 코드를 읽어야 하므로 코드가 번잡해집니다. 모듈화에서 가장 작은 ..

로직범위가 100,000 이하이고 같은 답을 반복해서 계산하는 피보나치 수이기 때문에 동적 프로그래밍, 메모이제이션 기법을 사용하는 것이 좋다!import java.util.*;class Solution { private final int[] f_arr = new int[100001]; // 제한 사항 내 범위까지 배열 생성 private int f(int n) { // 피보나치 메소드 if (n == 0 || n == 1) {return n;} // f(n) = 0, f(n) = 1 if (f_arr[n] != -1) {return f_arr[n];} // 피보나치 수 계산 결과를 담은 배열에 -1이 아니라는 것은 이미 계산을 한 결과가 있다는 것임. 따라서..

로직각 participant를 키로 정해두고, 기본 밸류는 1, 동명이인의 경우는 밸류++을 한다. completion을 키로 가지고 있는 각 밸류들을 -1 해주고, 밸류가 0보다 큰 키로 answer을 초기화해 준다.import java.util.*;class Solution { public String solution(String[] participant, String[] completion) { String answer = ""; HashMap map = new HashMap(); for (String s : participant) { map.put(s, map.getOrDefault(s, 0) + 1); ..

스택스택은 LIFO(Last In First Out: 후입선출) 특징이 있는 자료 구조입니다. 사전적 정의는 '쌓다', '더미'로서 접시 스택처럼 접시를 쌓아 놓는 것을 말합니다. 즉, 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. 아래 그림과 같이 스택은 마지막에 저장한 데이터를 먼저 꺼내게 되는 구조 특징이 있습니다.스택 사용법자바는 java.util.Stack 클래스를 통해 스택 동작을 제공하고 있습니다.import java.util.Stack;메서드설 명 boolean empty() Stack이 비어있는지 알려준다 Object peek() Stack의 맨 위에 저장된 객체를 반환 pop과 달리 Stack에서 객체를 꺼내지는 않는다 비어있을 경우 EmptyStackExc..

완전 탐색의 문제점완전 탐색은 가능한 모든 경우의 수를 탐색하는 방법입니다. 서로 다른 여러 경우의 수를 탐색하는 데 중복된 과정이 필요할 때는 해당 과정을 여러 번 연산하게 됩니다. 이러한 중복 과정이 많으면 많을수록 탐색 과정은 매우 비효율적입니다. 피보나치 수열은 하나의 항이 이전 두 항의 합으로 나타나는 수열로, 그 점화식은 아래와 같습니다.F(n) = F(n-1) + F(n-2)F(0) = 0F(1) = 1 이를 재귀 함수로 구현하면 다음과 같습니다.private static long fibonacci(int n) { if (n == 0 || n == 1) return n; return fibonacci(n - 1) + fibonacci(n - 2);}위 그림과 같이 이미 했던 연산을 계속..

문제 설명제한사항입출력 예입출력 예 설명입출력 예 #1예제 1번은 2, 3, 6번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 4미터이므로 한 번의 페인트칠에 연속된 4개의 구역을 칠할 수 있습니다. 처음에 3, 4, 5, 6번 영역에 페인트칠을 하면 칠해야 할 곳으로 2번 구역만 남고 1, 2, 3, 4번 구역에 페인트칠을 하면 2번 만에 다시 칠해야 할 곳에 모두 페인트칠을 할 수 있습니다.2번보다 적은 횟수로 2, 3, 6번 영역에 페인트를 덧칠하는 방법은 없습니다. 따라서 최소 횟수인 2를 return 합니다.입출력 예 #2예제 2번은 1, 3번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 4미터이므로 한 번의 페인트칠에 연속된 4개의 구역을 칠할 수 있고 1, 2, 3, 4번 영역..

문제 설명경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로..

해시란?해시는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다. 다른 말로는 '해시 값', '해시 코드', '체크섬'이라고도 합니다. 이러한 해시는 뒤에서 알아볼 '해시 함수'에 의해서 얻게 됩니다. 즉, 데이터의 KEY 값이 해시 함수를 통해서 변환된 간단한 정수입니다. 이렇게 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용됩니다.예를 들어, 다음과 같이 학번 데이터 id를 가지고 있는 학생 데이터 Student로 생성된 객체를 배열 students에 저장한다고 생각해 봅시다.class Student { final int id; final String name; Student(int id, String name) { this.id = id..