순간을 기록으로

문제 풀이 카드 3개의 합을 중에서 K번째로 높은 값을 구해야하는 문제이다. 우선 여러 카드 중에서 3개의 카드를 뽑는 건 3중 For문을 사용해서 할 수 있다. 그리고 그렇게 3개의 카드를 더한 값을 저장해야한다. 하지만 문제가 있는데 이렇게 뽑은 값들에 중복이 있다. 따라서 중복을 제거하기 위해 Set 자료구조를 사용할 것이다. 그리고 k번째로 높은 합을 구할거니깐 TreeSet을 사용한다. TreeSet은 안의 원소가 오름차순으로 정렬되어있다. 코드 package 인프런.해시맵과트리셋.K번째큰수.방법1; import java.util.Collections; import java.util.Scanner; import java.util.TreeSet; public class Main { private ..

문제 유형 연속된 값과 관련되느 투포인터 알고리즘 문제 풀이 방법 1.이중 FOR문 시간복잡도 O(N^2) 데이터의 갯수가 늘어날 수록 시간이 엄청 걸린다. 2.투포인터 알고리즘 O(N^2)를 O(N)으로 풀 수 있도록 해준다. 코드 import java.util.Scanner; public class Main { public int solution(int N, int M, int[] arr) { int count = 0; int sum = 0; int start = 0; for (int end=0; end =M) { sum -= arr[start++]; if (sum == M) coun..

문제 유형 DP(다이나믹 프로그래밍)이고 DP 알고리즘의 핵심 중 하나인 메모이제이션 알고리즘을 이용해서 풀어야 한다. 메모이제이션 알고리즘은 중복되는 결과를 저장함으로써 알고리즘의 실행 속도를 향상시킬 수 있다. 재귀를 이용해서 풀 수도 있지만 재귀의 경우 숫자가 커지면 중복되는 메소드가 많아져서 실행 속도가 느려진다. fibo(2)를 구할 때 fibo(1)을 한 번만 구해도 되지만 fibo(6)을 구하려면 fibo(1)을 8번 호출해야한다. 이미 구한 값을 또 계산할 필요가 있을까? 따라서 메모이제이션 방법을 추천한다. 풀이법 1.재귀적으로 푼다. 2. for문과 배열을 이용해 메모이제이션 알고리즘을 사용한다. 코드1: 재귀 public class Main { public int fibo(int N)..

문제 유형 LRU문제. 주의할 점 구현력을 기르는 문제. 코드 import java.util.Scanner; /* * size만큼의 배열을 선언합니다. * 작업의 갯수만큼 반복합니다. * 만약 캐시미스라면(=배열에 들어갈 값과 같은 값이 없다면) * i = size - 1부터 1까지 하나씩 줄면서 * cache[i] = cache[i-1] * cache[0]에 현재 작업 할당 * 만약 캐시히트라면(=배열에 들어갈 값과 같은 값이 있다면) * 히트가 난 지금의 인데스부터 i가 1까지 하나씩 줄면서 반복 * cache[i] = cache[i-1] * cache[0] 히트난 값을 할당 * */ public class Main { public int[] solution(int size, int numOfJobs..

유형 후위식 연산은 대표적인 스택 문제이니 꼭 한번 풀어보자. 풀이 /* * Integer를 담을 스택을 선언 * 문자열을 문자 하나하나씩 접근한다. * 만약 문자가 숫자형 문자이면 * 스택에 넣는다. * 만약 문자가 연산자라면 * 스택에서 상단 숫자 2개를 꺼낸다. * 2개의 숫자를 연산자로 계산한다. * 계산한 결과를 스택에 다시 넣는다. * * 마지막 스택에 남아있는 숫자를 출력한다. * */ 코드 import java.util.Scanner; import java.util.Stack; /* * Integer를 담을 스택을 선언 * 문자열을 문자 하나하나씩 접근한다. * 만약 문자가 숫자형 문자이면 * 스택에 넣는다. * 만약 문자가 연산자라면 * 스택에서 상단 숫자 2개를 꺼낸다. * 2개의 숫자..

문제 유형: 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 창문이 옆으로 이동하는 것처럼 문제를 푸는 방식이다. 어떤 배열이나 리스트에서 연속되는 원소의 최대합을 구한다고 가정해보자. 만약 이중for문을 이용해서 풀게 된다면 데이터에 접근할 때 중복이 생기게된다. 예를 들면, {1, 2, 3, 4, 5, 6,}에서 4개의 연속되는 원소의 합을 구할 때 이중 for문을 이용하면 첫 번째: 1, 2, 3, 4를 접근하게 되고, 두 번째에서 2, 3, 4, 5에 접근하게 된다. 즉 2, 3, 4는 중복되서 값을 읽어야 하기 때문에 낭비가 발생하게된다. 슬라이딩 윈도우 알고리즘을 이용하면 이러한 중복을 해결할 수 있다. 슬라이딩 윈도우는 일단 첫 4개의 값을 읽은 다음에 다음번 부터는 한 개의 for문을 이용해서 ..

문제 유형 재귀 풀이 방법 재귀 문제는 다음과 같이 푼다. 재귀 함수는 반드시 1.탈출문 2.함수 안에서 자신 메소드 호출 두 가지가 필요하다. 그리고 이 두가지는 if - else 구조를 사용해서 풀어야한다. 코드 import java.util.Scanner; public class Main { public int factorial(int n) { if (n == 1) // 탈출문 return 1; else return n * factorial(n-1); // 자기 자신 호출 } public static void main(String[] args) { Main T = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); Syste..

삽입정렬이란 현재 원소를 타깃으로 한다. 그리고 현재 원소의 이전 원소들을 비교해서 이전 원소가 크면 이전 원소를 현재 원소로 밀어준다. 그리고 이전 원소가 크지 않을 때 타깃 원소를 넣어주는 정렬 방법이다. 삽입 정렬 특징 데이터를 비교하면서 정렬하므로 비교 정렬이다. 데이터 비교할 때 추가적인 공간을 요구하지 않으므로 제자리 정렬(in-place sort)이다. 삽입정렬 장점 제자리 정렬이라서 추가적인 메모리 소모가 적다. 만약 거의 정렬된 상태라면 매우 효율적이다. 즉 최선의 경우 시간 복잡도는 O(N) 안장 정렬이 가능하다. 삽입정렬 단점 정렬이 역순으로 되어있으면 매우 비효율적이다. 즉 최악의 경우 시간 복잡도는 O(N^2) 데이터의 정렬 상태에 따라 성능 편차가 크다. 코드 import jav..