반응형 알고리즘 PS/알고리즘 일반17 코드 스니펫 1. class 객체 배열의 정렬 - point의 값을 기준으로 오름차순 정렬 class Build implements Comparable { int point; int height; Build (int p, int h) { this.point = p; this.height = h; } @Override public int compareTo (Build o) { return this.point - o.point; } } Arrays.sort(A); 2. 정수를 한자리씩 분리하는 방법 int Mod(int sum) { int mod = 1; for (int i=1; i 0) { sum += number/mod; // 제일 앞자리를 떼서 더한다. number = number%mod; // 앞자리를 떼고 나머.. 2022. 9. 21. DFS 알고리즘(깊이 우선 탐색) 그래프 탐색은 어떤 정점을 찾거나 아니면 단순히 그래프를 순회하는 데 쓰인다. 어떤 그래프 탐색 이론이든 핵심은 지금까지 어떤 정점을 방문했는지 기록하는 것이다. 이렇게 하지 않으면 무한 사이클에 빠지고 만다. 사이클이 없는 트리에서는 발생하지 않지만, 그래프에서는 사이클이 있을 수 있으므로 이 문제를 해결해야 한다. 방문 배열을 사용하면 해결 할 수 있다. * 깊이 우선 탐색 알고리즘의 동작 1. 그래프 내 임의의 정점에서 시작한다. 2. 현재 정점을 방문 배열에 표시한다. 3. 현재 정점의 인접 정점을 순회한다. 4. 방문했던 인점 정점이면 무시한다. 5. 방문하지 않았던 인접 정점이면 그 정점에 대해 재귀적으로 깊이 우선 탐색을 수행한다. * 코드 구현 void DFS(int v) { // 정점을 .. 2022. 9. 20. 메모이제이션을 통한 동적 프로그래밍 동적 프로그래밍(dynamic programming)은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다. 메모이제이션(memoization)은 하위 문제가 중첩될 때 재귀 호출을 감소시키는 간단하면서도 아주 뛰어난 기법이다. 본질적으로 메모이제이션은 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다. * 메모이제이션 구현 int fib(int n, int[] memo) { if (n == 0 || n == 1) return n; // memo 테이블을 확인해 fib(n)이 이미 계산된 건지 본다. if (memo[n] == 0) { // 값이 없으면 재귀호출 실행 memo[n] = fib(n-2, memo) + fib(n-1, memo); } return memo[n]; // 이미 계산된 값이 .. 2022. 9. 20. 재귀함수 - 재귀적으로 작성하는 법 1. 재귀 카테고리 : 반복 실행 - 반복적으로 한 작업을 실행하는 알고리즘이다. - 파라미터를 전달해 반복 계산한다. - 재귀에는 항상 종료 조건이 있어야 한다.(!) - 재귀 함수는 전체 작업의 일부만 수행하고, 나머지는 재귀 호출에 위임한다. 2. 재귀 카테고리 : 계산 - 하위 문제의 계산 결과에 기반해 계산할 수 있다. - 하위 문제는 입력값을 더 작게 한 똑같은 문제이다. - Factorial 함수가 대표적이다. - 계산 방식은 "상향식"과 "하향식"이 있는데, 상향식은 루프와 재귀의 방식이 같다. - 하향식이야 말로 재귀를 사용하는 주된 이유이다. 3. 하향식 재귀 : 새로운 사고방식 3-1. 하향식 사고 절차 a. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자. b. 문제의 하위 .. 2022. 9. 19. 코딩테스트 대비를 위한 백준 문제 추천 (코딩테스트 준비 관련해서 좋은 글이 있어서 출처를 남기고 퍼왔습니다.) 준비운동 PART1. 튼튼한 기본기 알고리즘 공부를 시작하면 만나게되는 약수, N진수, GCD, LCM, 소수 등의 문제는 변형하여 출제 혹은 어려운 문제를 풀이의 중간 단계에 들어가기도 합니다. 화이트보드 면접을 준비한다면 다양한 정렬 주제와 함께 준비해야할 1순위이기도 합니다. 파이썬으로 코테를 준비하는 분들이라면 내장함수를 사용하지말고 직접 구현해보세요. 약수 구하기 (🥉 브론즈 3티어) 이진수 (🥉 브론즈 3티어) 최소, 최대 (🥉 브론즈 3티어) 지능형 기차 2 (🥉 브론즈 3티어) 피보나치 수 5 (🥉 브론즈 2티어) 일곱 난쟁이 (🥉 브론즈 2티어) 최대공약수와 최소공배수 (🥈실버 5티어) N번째 큰 수 (🥈실버 5티어.. 2022. 9. 19. 문자열 입력 처리 방법 1. 문자열에서 (-) 기호를 기준으로 분리하고, 그 토큰은 (+)를 기준으로 다시 분리할 때 a. 입력받은 문자열은 - 기준으로 분리한다. b. 자른 토큰들을 + 기준으로 다시 분리한다. c. 자른 토큰들을 정구형으로 캐스팅해서 합친다. str = in.next(); String[] sub = str.split("-"); // -로 문자열을 자른다. for (int i=0; i 2022. 9. 19. 온라인 코딩 테스트의 사전준비 1. 연습장과 필기 도구 재귀 구조를 구현할 때 머릿속으로만 구조를 그려내면 실수하기가 쉽다. 처음부터 연습장에 값의 변화나 최종 결과를 기록하고 머릿속에 떠올린 구조와 비교하면서 풀이해나가자. 2. 자신만의 코드 스니펫 준비 코딩테스트 시 자주 쓰이는 동작들에 대해 코드 스니펫을 미리 만들어 두면 도움이 된다. 예를 들어 연결리스트를 뒤집거나 삭제하는 등의 작업들은 갑자기 구현하려면 헷갈리기도 하고 시간이 걸리는데, 이런 작업에 대한 코드를 미리 만들어두면 좋다. 3. 모든 테스트 케이스를 통과하도록 풀어야 코딩 테스트 시에는 충분히 생각하고 문제가 없는지 코드를 다시 한번 더 꼼꼼히 확인 후에 제출하는 편이 유리하다. 실무에서처럼 일단 돌아가는 코드를 제출하고 테스트를 지속적으로 돌려보면서 오류를 수.. 2022. 9. 17. BFS 알고리즘(너비 우선 탐색) ※ 그래프 용어 - 정점(vertex) : 그래프 안의 노드 - 간선(edge) : 각 정점을 잇는 선 - 인접(adjacent) : 간선으로 연결된 정점 - 이웃(neighbor) : 인접한 정점 BFS(Breadth First Search)로 줄여 부르는 너비 우선 탐색은 그래프를 탐색하는 방법이다. 깊이 우선 탐색과 달리 너미 우선 탐색은 재귀를 쓰지 않는다. 대신 큐로 문제를 해결한다. 큐는 FIFO로 먼저 들어간 데이터를 우선 처리한다. * 너비 우선 순회 알고리즘 1. 그래프 내 아무 정점에서 시작한다. 이 정점을 "시작 정점"이라 부른다. 2. 시작 정점을 방문 배열에 추가해 방문 표시를 한다. 3. 시작 정점을 큐에 추가한다. 4. 큐가 빌 때까지 실행하는 루프를 시작한다. 5. 루프 안에.. 2022. 9. 6. 이전 1 2 다음 반응형
