알고리즘31 인프런 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. 인프런 JAVA 알고리즘 정리(HashMap, TreeSet 1번~5번) 1. 학급 회장 // 15 명의 학생이 각각의 학생(알파벳)을 투표하여 투표수가 가장 많은 학생(알파벳을) 회장으로 BACBACCACCBDEDE // 알파벳하고 투표수(카운트)랑 짝이 되어야 되기때문에 키값으로 구성이 되는 해시맵을 생각할 수 있다. // 알아두면 좋은 메서드 map 이름을 가지 해시맵을 선언하고 map.getOrDefault(x, 0) x라는 키값이 있으면 그 값을 리턴하고 x라는 키값이 해시맵에 없으면 0을 리턴해라 . 2. 아나그램 // AbaAeCe baeeACA 2개의 문자열이 각각의 원소의 개수가 같으면 TRUE // 결국 A-2개 , b-1개, a-1개, C-개, C-1개의 원소로 같으므로 두 문자열은 같다고 할 수 있다. // 해시맵은 순서가 존재하지 않기에 순서에 상관없이.. 2023. 4. 8. 인프런 JAVA 알고리즘 정리(Two pointers, Sliding window 1번~6번) 1. 두 배열 합치기 // 두 개의 배열을 합쳐서 오름차순 정렬 -> 효율적으로 접근해봐라 - 투 포인터 - Arrays.sort 의 시간복잡도는 평균 O(nlog(n)) , 최악O(n^2) - O(n) 으로 접근하도록 -> 투 포인터 알고리즘 2. 공통원소 구하기 // 두 개의 배열에서 공통 원소를 추출해사 오름차순 정렬 시켜 - 투 포인터 - 두 배열을 오름차순 정렬 - 변수 2개 선언 - 두 배열이 같으면 출력, 한쪽이 크다? 작은쪽 변수를 1증가 - 한쪽이 끝날 때 까지 진행. 3. 최대 매출 // 배열이 있으면 N일 동안의 최대 매출 출력 - 슬라이딩 윈도우 10일의 매출중 연속된 3일의 매출의 최대 값은 4. 연속부분수열 // 투 포인터 + 슬라이딩 5. 연속된 자연수의 합 // 15가 입력되.. 2023. 4. 5. 인프런 JAVA 알고리즘 정리(배열 1번~12번) 1. 큰 수 출력하기 // 앞이랑 큰값 비교하여 출력 (바로 앞보다 큰 지) 2. 보이는 학생 // max 값 설정하여 큰 값 비교 (전체의 앞보다 큰 지) 3. 가위바위보 // if else 문의로 가위 바위 보 기준에따라 설정 4. 피보나치 수열//(재귀 x) for 문을 돌며 앞 과 뒤수를 바꿔가며 + 5. 소수 // Math.abs(x) 절대값 = x가 -3 이면 3 출력 // Math.pow( x, y ) 제곱 = x 가 2 이며 y 3이면 2의 3승 8 출력 // Math.sqrt(x) 제곱근 = x 25 이면 5 출력 -에라토스테네스 체 (순서대로 소수 체크할 때 활용) for문을 돌면서 소수를 발견하면 소수의 배수는 모두 1로 체크한다 (체크된 배수들은 소수를 배수로 가지고 있기 떄문에) .. 2023. 4. 3. 인프런 JAVA 알고리즘 정리(문자열 1번~12번) 1. 문자찾기 - //char 입력 = sc.next().charAt(0) -//char Character.toUpperCase(문자); 2. 대소문자 변환 // Character 클래스 활용 isUpperCase(문자) 대문자인지 // 97~122 소문자- 65~95 대문자 아스키 코드 대 소문자 32 차이 3. 문장 속 단어 // 스페이스 포함 문자열 입력 nextLine() // split()메서드 활용하여 가장 긴 문자열 찾기 // String.indexOf(문자) 문자가 맨 처음~ 발견되는 인덱스 번호 4. 단어 뒤집기 // StringBuilder reverse() 단어 뒤집기 // toString() 문자열로 변환 // String 배열-> String = String.join("", 스트링.. 2023. 3. 28. 이전 1 2 3 4 다음
