본문 바로가기

자바 자료구조 알고리즘

 (15)
Java 코딩 테스트 그리디 알고리즘 문제 풀이 개요 목적 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 좋은 결과를 내기를 바라는 풀이법이다. 씨름 선수 5 172 67 183 65 180 70 170 72 181 60 풀이 먼저 키가 큰 선수가 앞으로 오게 내림차순을 한다. 이제 자신 앞 선수들 중 가장 큰 몸무게보다 자신이 더 나가기만 한다면 뒤에 있는 선수들보다는 키가 크고(몸무게 비교 불필요) 앞에 있는 선수들보다는 몸무게가 많이 나가기 때문에 선발이 된다. 선발이 되면 cnt ++ 출전 선수 1명을 추가하고 가장 무거운 몸무게를 해당 선수 몸무게로 변경한다. import java.util.*; class Body implements Comparable{ publi..
코딩 테스트 Java BFS 활용 문제 풀기 개요 목적 Java BFS 기초 이해와 문제 풀이 해당 글에서는 재귀함수와 BFS기초를 알아보았다. 이번 시간에는 BFS 활용 문제를 풀면서 BFS 문제 풀이 실력을 늘려보자. 동전 교환 3 1 2 5 15 풀이 최소 개수를 구하는 문제이기 때문에, BFS를 사용하는 것이 유리하다. DFS의 경우, 1,2,5로 시작할 때, 1+1+1+1+1 1에서 1을 더하는 모든 경우의 수를 구한 후에, 값이 나오지 않으면, 2로 넘어가고 5로 넘어간다. 반면에, BFS는 L=1인경우 동전을 하나 사용했을 경우 합을 구한 후에 답이 없다면, L=2 동전 두개 사용한 경우 합을 구하는 방식으로 메소드가 진행된다. 그래서 동전을 3개 사용했을 때, 5+5+5를 구하는 경우의 수를 빠르게 찾을 수 있다. import jav..
코딩 테스트 Java DFS 활용 문제 풀기 개요 목적 Java DFS 기초 이해와 문제 풀이 해당 글에서는 재귀함수와 DFS 기초를 알아보았다. 이번 시간에는 DFS 활용 문제를 풀면서 DFS 문제 풀이 실력을 늘려보자. 합이 같은 부분집합(DFS : 아마존 인터뷰) 6 1 3 5 6 7 10 풀이1. ch 배열( 해당 숫자 포함될 때, 안될 때 - 사용) import java.util.*; class Main { static int n; static int[] arr; static int[] ch; static int half; static boolean result; public void DFS(int v) { if (v == n+1) { System.out.println(Arrays.toString(ch)); int sum = 0; for ..
Java 그래프 문제 -인접 행렬, 인접 리스트 ,DFS, BFS 개요 목적 이번 시간에는 코딩 테스트 그래프 문제를 풀기 위한 그래프 인접 행렬 인접 리스트 표현 문제 풀이 방식에 대해서 알아본다. DFS, BFS 방식의 그래프 문제들을 풀어보면서 심화 그래프 문제 풀이 방법도 알아보자. 그래프와 인접 행렬 무방향 그래프, 방향 그래프, 가중치 방향 그래프를 컴퓨터가 이해할 수 있는 인접 행렬로 표현을 해보자. 1. 무방향 그래프 무방향 그래프는 양방향 그래프라고도 한다. 해당 그래프가 이루어진 노드와 엣지(간선)의 숫자 집합을 나열해보면, 1 2 1 3 2 4 2 5 3 4 3 1 4 2 5 2 이 들어온 수를 grab[a][b] = 1 grap[b][a]로 체크를 하면 인접 행렬을 구할 수 있다. 1 2 3 4 5 1 1 1 2 1 1 1 3 1 1 4 1 1 5..
Java BFS 기초 이해와 문제 풀이 개요 목적 이번 시간에는 BFS 쉬운 문제들을 풀어보면서 BFS 동작 원리와 풀이 방법에 대해서 알아보자. BFS 넓이 우선 탐색 문제를 통해서 알아보기 이진 트리 노드가 주어졌을 때 목표 0: 1 1: 2 3 2: 4 5 6 7 이런식으로 각 레벨 별로 탐색하는 알고리즘을 한번 작성해보자 풀이 import java.util.LinkedList; import java.util.Queue; public class 이진트리순회 { static class Node{ int data; Node lt, rt; public Node(int val) { data=val; lt=rt=null; } } public static void BFS(Node node) { Queue queue = new LinkedList()..
Java DFS 기초 이해와 문제 풀이 개요 목적 DFS 깊이 우선 탐색을 재귀 함수로 많이 표현하기 때문에 재귀 함수 동작 과정을 먼저 이해해야 한다. 아래 문제들을 풀면서 재귀 함수가 어떻게 진행되는 지 파악하면서 공부해보자. 그리고 기초적인 DFS 문제들을 풀면서 DFS에 대한 이해를 해보자. 재귀 함수 문제 풀이 1. 해당 재귀 함수가 어떻게 진행될까 생각해보기 public class Main { public static void DFS(int n) { if (n == 0) { return; } else { DFS(n - 1); //6번 라인 System.out.print(n + " "); //7번 라인 } } public static void main(String[] args){ DFS(3); } } DFS(3) 에서 6번 라인에 D..
코딩 테스트 Java 정렬 문제 풀이 선택 정렬 알고리즘 작성하기 해당 숫자들을 선택 정렬을 사용해서 정렬한 값을 출력하시오 6 13 5 11 7 23 15 풀이 import java.util.Arrays; import java.util.Scanner; public class 선택정렬 { public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n=kb.nextInt(); int[] arr=new int[n]; for(int i=0; i
코딩 테스트 Java Hash, Set 문제 풀이 개요와 목적 코딩 테스트 대표적인 Hash, Set 문제들을 풀어보고, Hash, Set의 문제 풀이 방식에 대해서 알아본다. 아나그램 AbaAeCe baeeACA abaCC Caaab 풀이 정렬로도 풀 수 있지만, hashMap과 getOrDefault를 사용해서 풀어보자 public class 아나그램 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.next(); char[] aChars = a.toCharArray(); char[] bChars = b.toCharArray(); HashMap map = new HashMap(); String ..
반응형

티스토리툴바