반응형 알고리즘&코딩테스트24 [알고리즘&코딩테스트] 투 포인터 알고리즘 (Two Pointers) 투 포인터란? · 화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법이다. · 두 개의 화살표 우치를 기록하면서 문제를 처리한다. 카테고리 1. 1차원 배열 위에 2개의 포인터를 만드는 경우 · 해당 카테고리는 두가지로 나뉜다. 1. 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동 2. 2개의 포인터가 양 끝에서 서로를 향해 이동 2. 관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우 ex) A와 B 변수의 곱의 최소 값 구하기 꿀팁 · 다음의 키워드가 등장하면 두 포인터 접근을 시도해 볼 가치가 있다. - 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로" - 곱의 최소 예제 BOJ 1806 - 부분합 · 문제링크: https://www.ac.. 2022. 1. 19. [알고리즘&코딩테스트] 매개 변수 탐색 (Parametric Search) 매개 변수 탐색(Parametric Search)란? · 이진 탐색(이분 탐색)을 사용하여 조건을 만족하는 최대값을 구하는 방법이다. · 핵심 1. 정답을 매개 변수로 만들고, Yes/No 문제(결정 문제)로 바꿔 보기 2. 모든 값에 대해서 Yes/No를 채웠다고 생각했을 때, 정렬된 상태인가? 3. Yes/No를 결정하는 문제로 풀기 · 문제를 거꾸로 푸는 것이기 때문에 통찰력이 요구된다. · 최근 코딩테스트 빈도로 굉장히 높게 나온다. · 키워드에 "~~의 최댓값/최솟값 을 구하시오"가 포함되면 매개 변수 탐색을 접근해볼 가치가 있다. · 자주 하는 실수 1. 매개 변수에 대한 결정이 Nooooooo Yessssss 꼴이 아닌데 이분 탐색을 하는 경우 2. L, R, M, Result 변수의 정의를.. 2022. 1. 15. [알고리즘&코딩테스트] 이분 탐색 (Binary Search) 문제 목차 · 수열에서의 탐색이란? · 이분 탐색이란? - 이분 탐색의 시간 복잡도 - 이분 탐색에서 자주 하는 실수 - 이분 탐색 작동 방식 수열에서의 탐색이란? · 수열과 탐색 대상 X가 주어졌을 때, 다음의 질문을 던지는 것 - X가 존재하는가? - X [이하, 미만, 이상, 초과]의 원소는 몇 개가 있는가? - X와 가장 가까운 원소는 무엇인가? · 아래 그림 처럼 정렬 되지 않은 수열이 주어지면 탐색 속도는 O(N)이다. X = 63 72 19 38 58 10 92 18 11 87 · 아래 그림 처럼 정렬된 수열이 주어지면 이분 탐색으로 더 빠르게 탐색할 수 있다. 10 11 18 19 38 58 72 87 92 이분 탐색이란? · 정렬이 보장된 배열에서 기준 X를 가지고 범위를 이분하면서 탐색하는 .. 2022. 1. 9. [알고리즘&코딩테스트] 완전 탐색(Brute Force) 완전 탐색(Brute Force) · 문제를 해결하기 위해 확인하는 모든 경우를 탐색하는 방법이다 - 정답은 무조건 구하는 치트키 · 백 트래킹을 사용해야 하는 상황을 해결한다. · 모든 코딩테스트 문제에게 기본적으로 접근해 봐야 한다. · 장점: 부분점수를 얻기 좋다. · 단점: 전부 탐색하기 때문에 일반적으로 시간 복잡도가 높다. 코딩테스트에 나오는 완전 탐색 문제 종류 · 4가지: (중복없이 or 중복을 허용해서) N개 중 M개를 (고르기 or 순서 있게 나열하기) · 완전 탐색은 함수 정의가 50% // Recurrence Function (재귀 함수) // 만약 M 개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것! // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건.. 2022. 1. 4. [Algorithm] 다이나믹 프로그래밍(동적계획법, Dynamic Programming) 다이나믹 프로그래밍이란? · 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 · 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킨다. · 2가지 방식이 존재한다. 1. 탑다운, 2.보텀업 · 최적해를 구하는데 시간 또는 메모리 공간이 매우 많이 필요한 문제는 컴퓨터를 활용해도 해결하기 어려울 수 있다. 이럴 때 사용하면 효과적인 기법이다. ▶ 예시 - 피노나치 수열 · 점화식으로 나타낸 피보나치 수열 · 점화식: 인접한 항들의 관계식. 수열의 항이 이어지는 형태를 간결하게 표현. ▶ 예시 - 재귀를 사용한 피보나치 소스코드 public class 피보나치_재귀적 { public static void main(String[] args){ Sys.. 2021. 11. 18. [Algorithm] 구현 문제란? 학습 목표 · 구현 문제란? · 구현 시 고려해야 할 메모리 제약 사항 · 채점 환경 · 구현 문제에 접근하는 방법 구현 문제란? 코딩 테스트에서 구현 · 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 구현 문제 · 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다. - ex) 완전 탐색, 시뮬레이션 유형 ▶ 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 ▶ 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 구현하기 어려운 문제란? 1. 알고리즘은 간단한데 코드가 치나칠 만큼 길어지는 문제 2. 특정 소수점 자리까지 출력해야 하는 문제 3. 문자열이 입력으로 주어졌을 때 한 문자 .. 2021. 11. 6. 이전 1 2 3 4 다음 반응형
