Coding Test/알고리즘 개념
자바를 사용한 코딩 테스트
Coding Test/알고리즘 개념
[목차] Do it! 알고리즘 코딩 테스트 자바
목차 문제 풀이 01 코딩 테스트 준비하기 시간 복잡도 X 디버깅 X 02 자료구조 배열과 리스트 숫자의 합 구하기 평균 구하기 구간 합 구간 합 구하기 1 구간 합 구하기 2 나머지 합 구하기 투 포인터 연속된 자연수의 합 구하기 주몽의 명령 좋은 수 구하기 슬라이딩 윈도우 DNA 비밀번호 최솟값 찾기 1 스택과 큐 스택으로 오름차순 수열 만들기 오큰수 구하기 카드 게임 절댓값 힙 구현하기 03 정렬 버블 정렬 수 정렬하기 1 버블 소트 프로그램 1 선택 정렬 내림차순으로 자릿수 정렬하기 삽입 정렬 ATM 인출 시간 계산하기 퀵 정렬 K번째 수 구하기 병합 정렬 수 정렬하기 2 버블 소트 프로그램 2 기수 정렬 수 정렬하기 3 04 탐색 깊이 우선 탐색 연결 요소의 개수 구하기 신기한 소수 찾기 친구 ..
Coding Test/알고리즘 개념
[기하] 기하
✔ 기하 기하 알고리즘이란? 점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘 실제 코딩 테스트에서의 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀이 CCW란? 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘 CCW 공식 세 점을 A(X₁, Y₁), B(X₂, Y₂), C(X₃, Y₃) 라고 가정했을 때, CCW = (X₁Y₂+ X₂Y₃+ X₃Y₁) - (X₂Y₁+ X₃Y₂, X₁Y₃) 세 점이 주어졌을 때 CCW 공식을 사용해 세 점에 관한 다양한 관계를 도출할 수 있음 CCW는 부호에 따라 다른 의미를 가짐 CCW 결과 0 : 반시계 방향 부호와 별개로 CCW 결과의 절댓값은 세 점의..
Coding Test/알고리즘 개념
[동적 계획법] 동적 계획법
✔ 동적 계획법 동적 계획법이란? 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 동적 계획법은 다음을 만족할 때 사용 큰 문제를 작은 문제로 나눌 수 있어야 함 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 함 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용함 (메모이제이션 기법) 톱-다운 방식과 바텀-업 방식으로 구현할 수 있어야 함 피보나치 수열이란? 각 항이 바로 앞의 두 항을 이루어진 수열 피보나치 수열로 동적 계획법 이해하기 동적 계획법으로 풀 수 있는지 확인하기 6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합 즉..
Coding Test/알고리즘 개념
[조합] 조합
✔ 조합 조합이란? n개의 숫자에서 r개를 뽑는 경우의 수 nCr로 표현 nCr = n! / (n - r)! * r! (이때, r!는 순서가 다른 경우의 수를 제거하여 같은 경우로 취급하기 위한 것) 순열이란? n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수 nPr로 표현 nPr = n! / (n - r)! 조합의 점화식 특정 문제를 가정하기 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정 마지막 데이터의 선택 여부에 따른 경우의 수를 계산 만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서..
Coding Test/알고리즘 개념
[트리] 최소 공통 조상 (LCA)
✔ 최소 공통 조상 최소 공통 조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드 일반적인 최소 공통 조상 찾기와 최소 공통 조상 빠르게 찾기가 존재 트리의 높이가 크지 않을 때는 일반적인 최소 공통 조상 찾기 사용 (1개씩 올라가기) 트리의 높이가 커질 경우, 시간 제약 문제가 직면할 수 있으므로 최소 공통 조상 빠르게 찾기 사용 (2^K씩 올라가기) 일반적인 최소 공통 조상 구하기 부모 노드와 깊이 저장 배열 만들기 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장함 이때 탐색은 DFS 또는 BFS를 이용 선택된 두 노드의 깊이가 다를 경우, 더 깊은 노드의 노드를 부모 노..
Coding Test/알고리즘 개념
[트리] 세그먼트 트리 (인덱스 트리)
✔ 세그먼트 트리 세그먼트 트리란? 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태 더 큰 범위는 인덱스 트리라고 불림 코딩 테스트에서 구간 합만 수행할 경우 합 배열과 구간 합 사용, 구간 합과 데이터 업데이트를 둘 다 수행할 경우 세그먼트 트리 사용 세그먼트 트리의 종류는 구간 합, 최대 구하기, 최소 구하기로 나누어짐 구현 단계는 트리 초기화하기, 질의값 구하기 (구간 합, 최대, 최소), 데이터 업데이트하기로 나누어짐 세그먼트 트리 과정 트리 초기화하기 리프 노드의 개수가 데이터의 개수 이상이 되도록 트리 배열을 만듦 2^k ≥ N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 배열의 크기로 정의 리프 노드에 원본 데이터를 입력 리프 노드의 시작 위치를 트리 배..
Coding Test/알고리즘 개념
[트리] 이진 트리
✔ 이진 트리 이진 트리란? 각 노드의 자식 노드의 개수가 2 이하로 구성돼 있는 트리 이진 트리의 종류 편향 이진 트리 : 노드들이 한 쪽으로 편향돼 생성된 이진 트리 포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 조하되고 공간이 많이 낭비 일반적으로 코딩 테스트에서 데이터를 트리에 담는다고 하면 완전 이진 트리 형태를 사용 이진 트리의 순차 표현 트리 자료 형태는 배열 이진 트리는 1차원 배열의 형태로 표현할 수 있음 트리의 노드와 배열의 인덱스 사이 상관 관계 루트 노드 : in..
