본문 바로가기

코딩테스트/인프런12

인프런 JAVA 알고리즘 정리(dp(동적계획법)) 1. 계단오르기 복잡한 문제를 -> 작은 문제로 시작하여 푼다. 계단이 1개일때 부터 2개 3개 4개... 로 풀이 1번째 계단을 가는 경우의 수 : 1 가지 2번째 계단을 가는 경우의 수 : 2가지 ( 1칸 1칸, 2칸 ) 3번째 계단을 가는 경우의 수 : 1번째 계단에서 올라오거나 or 2번째 계단에서 올라온다. -> 첫번째 계단 경우의 수 + 두번째 계단 경우의 수 4번째 계단을 가는 경우의 수 : 2번 째 경우의 수+ 3번 째 경우의 수 - 피보나치형식으로 구할수 있다. static int[] dy; public static void main(String[] args) { Main T = new Main(); Scanner kb = new Scanner(System.in); int n = kb.n.. 2023. 5. 17.
인프런 JAVA 알고리즘 정리(Greedy Algorithm 1~8번) 1. 씨름 선수 키 몸무게가 있고 자신보다 키 몸무게 둘다 큰 사람이 없다면 선택 -> (183, 65) - 키가 제일 큼 -> (180, 70) - 자신보다 키가 큰 사람중 자신보다 몸무게 큰 사람이 없음 -> (170, 72) - 자신보다 키가 큰 사람중 자신보다 몸무게 큰 사람이 없음 1. 사람을 키순으로 정렬한다. ( 첫번째 사람은 일단 키가 제일 크니 픽) 2. 그 뒤로 몸무게가 앞 사람보다 크다면 픽 ( 앞사람보다 키는 작지만 몸무게는 제일 높다는 소리) public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); ArrayList arr = new ArrayList(); .. 2023. 5. 14.
인프런 JAVA 알고리즘 정리(DFS, BFS 활용 8~15번) AccessDenied Access Denied 7VKㄹㄷ7ㄹㄹBS6FQ704K885 qIEAFwzuh+2t2fNXlzFm6QdvDF27FjvRN9nj2hacWFKfOatXaZ3PPoFx/vSRNTt10d60TRXD/nw= 8. ⭐수열 추측하기⭐ // 1부터 N 까지의 숫자가 한 개씩 적혀있는데 그 숫자를 추측해라. // N이 4라고 하고 마지막 값이 16이 주어진다면 맨 위의 숫자는? 여러 값이 있다면 가장 앞에 오는 것을 출력 조합을 먼저 구하고 -> 순열를 바꿔가며 재귀를 돈다. 4 의 값 (3*1) + (1*3) + (2*3) + (4*1) = 16 규칙이 존재 4자리수면 1 3 3 1 을 곱하는 최종 결과라는... 5자리면 1 4 6 4 1 1. 1 3 3 1 b { 1, 3, 3, 1 } 2... 2023. 5. 13.
인프런 JAVA 알고리즘 정리(DFS, BFS 활용 1~7번) 1. 합이 같은 부분집합(DFS : 아마존 인터뷰) // 배열 {1, 3, 5, 6, 7, 10}이 입력되된다면 2 집합으로 나누었을 때 같은 합이 있냐? // { 1, 3, 5, 7 } == { 6, 10 }이 나올 수 있으므로 같은 합이 있다 -> YES 출력 // DFS를 알고리즘을 사용해서 각각의 숫자를 사용할때와 안할때를 비교해서 최종 합이 같은지 비교 public String DFS(int L, int[] arr){ if(L == n){ int sum=0; for(int x : result) sum+=x; int total_t = total-sum; System.out.println(sum); // *현재까지 사용한 값과 사용하지 않은 값의 합이 같으면 YES 리턴* if(sum==total_.. 2023. 5. 11.
인프런 JAVA 알고리즘 정리(DFS, BFS 기초 7~14번) 7. 이진트리 레벨탐색 (BFS) - 최단거리 (목적지 까지 몇번만에 갈 수 있는지) - for문이 끝나면 레벨 증가 - Queue queue = new LinkedList(); 8. 송아지 찾기 (BFS) - 최단거리 - 앞으로 1, 뒤로 1, 앞으로 5칸 갈 수 있다면 송아지 위치까지의 최단거리는? - 나의 위치 4 송아지 위치 5 -> 앞으로 한칸으로 1번 최단거리 - 나의 위치 5 송아지 위치 11 -> 앞으로 한칸 + 앞으로 5칸 2번 최단거리 public static int BFS(int me, int song){ int count = 0; ch = new int[10004]; ch[me] = me; Queue queue = new LinkedList(); queue.add(me); while.. 2023. 5. 5.
인프런 JAVA 알고리즘 정리(DFS, BFS 기초 1~6번) 1. 재귀함수 (스택프레임) public static void DFS(int n){ if(n==0){ }else { DFS(n-1); System.out.println(n); } } 2. 10진수를 2진수로 (재귀사용) public static void DFS(int n){ if(n==0){ }else { DFS(n/2); System.out.print(n%2); } } 3. 팩토리얼 public static int DFS(int n){ if(n==0){ return 1; }else { return n*DFS(n-1); } } 4. 피보나치 ( 재귀 + 메모리제이션 ) public class Main { static int[] arr; public static void main(String[] args).. 2023. 5. 1.
인프런 JAVA 알고리즘 정리(정렬 7번~10번) 7. 좌표정렬 // 일반 숫자 정렬이 아닌 좌표값을 정렬 - implements Comparable 정렬 기준을 정할 수 있다. - implements를 하면 정의해야 하는 compareTo 메서드를 정의해야 한다. class Point implements Comparable{ int x; int y; public Point(int x, int y){ this.x = x; this.y = y; } @Override public int compareTo(Point o) { if(o.x == this.x) return this.y-o.y; return this.x-o.x; } } 리턴해서 x를 기준으로 정렬을 한다면 this가 - 기호 앞에 오면 오름차순 this가 - 기호 뒤에 오면 내림차순 정렬 위의 코.. 2023. 4. 30.
인프런 JAVA 알고리즘 정리(정렬 1번~6번) 1. 선택정렬 - 배열의 가장 작은수를 찾아서 0번째 위치랑 스위칭 - 2중 for문 2.버블정렬 - 이웃한거 끼리 비교해서 앞에가 작고 뒤에가 더 크면 스위칭 - 2중 for문 3. 삽입정렬 - 뒤로 큰수를 비교하여 큰 수면 한 칸 씩 뒤로 밀린다. 4. LRU - ArrayList = list.set(2,5) // 2번 인덱스에 5번을 넣어라, 그럼 뒤의 수는 자랑으로 밀림 - ArrayList = list.add(2,5) // 동일 - ArrayList = list.indexOf(x) // x의 인덱스 위치 -삽입정렬 -캐시 미스 or 캐시가 꽉 차있다 = 뒤로 한 칸씩 미룸 -캐시 적중 = 적중한 인덱스 앞부터 뒤로 한 칸씩 미룸 5. 중복확인 중복 저장 안되는 리스트 - TreeSet 6. 장난.. 2023. 4. 14.
인프런 JAVA 알고리즘 정리(Stack, Queue(자료구조) 1번~8번) 1. 올바른 괄호 // 올바른 괄호인지 확인하는 스택의 기본적인 문제 - (())()()( 이런식으로 단순히 '(' 와 ')' 로만 이루어 있다. - 그래서 Stack으로도 풀어보고 count 변수 선언 하여 풀어보았다. 2. 괄호문자제거 // 스택은 배열 - pop()을 하지 않고 for문으로 순서대로 꺼낼시 LIFO 형식이 아닌 INDEX 순 ( 먼저들어간 순으로 나옴-stack.get(i) ) 3. 크레인 인형뽑기(카카오) - 1. 뽑길 원하는 숫자(라인)이 넘어오면 2차원 행열의 열 기준 for문을 돌려 0이 아닐때 까지 돈다. - 2. 0이 아닌 숫자를 만나면 stack에 넣는 작업을 하는데 - 2.1) 스택이 비어있거나 스택의 위의 숫자와 넣는 숫자가 다르면 그냥 넣는다. - 2.2) 스택이 .. 2023. 4. 10.

티스토리툴바