본문 바로가기

내가 배운 것들41

항해99 11/12(금) 알고리즘 DFS - 깊이 우선 탐색(Depth Frist Scan) - 자식 노드, 자식의 자식, 자식의 자식의 자식... 계속 찾아가며 탐색하는 방식이다. - 자식이 존재하지 않으면 자신의 부모에게 돌아가 부모가 다른 자식이 있는지 찾아보고 존재할 시 다시 탐색한다. - 스택을 이용해 구현하면 편하다. - A B E K L F C G D H M I J push(A) push(B) push(E) push(K) pop() -- K push(L) pop() -- L pop() -- E push(F) pop() -- F pop() -- B push(C) push(G) pop() -- G pop() -- C push(D) push(H) push(M) pop() -- M pop() -- H push(I) pop() -- .. 2021. 11. 12.
항해99 11/11(목) 알고리즘 기본적인 지식은 이미 있기에 메모할만한 것만 정리해놓으려고 한다. 이진 탐색(binary search) - 시간복잡도는O(logN). 매우 빠르다. - 하지만 반드시 데이터가 정렬된 상태에서만 사용할 수 있다. public static boolean binarySearch(int[] arr, int target){ boolean result = false; int min_idx = 0; int max_idx = arr.length-1; while(min_idx target){ // target보다 크면 max_idx가 내려옴 max_idx = idx-1; }else if(arr[idx] < target){ // target보다 작으면 min_idx가 올라옴 min_idx = idx+1; } } retur.. 2021. 11. 11.
항해99 11/11(목) 알고리즘 - 알아서 푼 것들 같은 숫자는 싫어 코딩테스트 연습 - 같은 숫자는 싫어 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 programmers.co.kr class Solution { public int[] removeRepeat(int[] arr){ List list = new ArrayList(); for(int i = 0; i < arr.length; i++){ if(i < arr.length-1 && arr[i] == arr[i+1]){ continue; } list.add(arr[i]); } System.out.println(list); int[] result.. 2021. 11. 11.
항해99 11/10(수) 알고리즘 - 알아서 푼 것들 실패율 - Entry 사용 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr class Solution { public int[] solution(int N, int[] stages) { // 실패율의 정의 : 스테이지에 도달했지만 클리어하지 못 한 플레이어의 수 / 스테이지에 도달한 플레이어의 수 // N은 전체 스테이지의 개수 // 멈춘 스테이지 리스트가 stages // 실패율이 높은 스테이지부터 내림차순으로 return int[] answer = new int[N]; int[] clearArr = new.. 2021. 11. 10.
항해99 11/9(화) 알고리즘 약수의 개수와 덧셈 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr class Solution { public int solution(int left, int right) { int answer = 0; for (int i = left; i 2021. 11. 9.
항해99 11/9(화) 알고리즘 - 알아서 푼 것들 키패드 누르기 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr class Solution { public int distance(int num, int pos){ int distance = 100; int temp_num = 100; // 현재 위치가 2 5 8일 경우 // 1. |num - pos| 값 구하기 // 2. 3 뺄 수 있으면(세로이동) 3 빼고 거리 + 1 // 3. 3 뺄 거 다 빼고.. 2021. 11. 9.

티스토리툴바