본문 바로가기

전체 글61

구현 아이디어를 코드로 바꾸는 구현 코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 하지만 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제 되기에 다른 알고리즘을 배우기 전에 먼저 다룬다. 알고리즘 문제를 해결할 떄 문제를 읽고 풀이 방법을 고민한다. 이후 구현을 위해 프로그래밍 언어의 문법을 정확히 알고 있어야하고 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야한다. 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드.. 2023. 2. 12.
그리디 알고리즘 당장 좋은 것만 선택하는 그리디 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리지 알고리즘을 이용하면 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형을 앞으로 다루게 된 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 반면 이후에 공부할 정렬, 최단 경로 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 예를 들어 여러 개의 데이터를 빠르게.. 2023. 2. 12.
1/29 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 냅색 알고리즘 (Knapsack Algorithm) 유명한 다이나믹 프로그래밍 문제 혹은 그리디 알고리즘 문제 중 하나이다. 두 가지 유형으로 나뉜다. Fractional Knapsack Algorithm: 주어진 자원을 쪼갤 수 있다는 가정 하에 그리디 알고리즘으로 최적의 조건이 구해진다. 주어진 조건(ex: 가격, 무게) 중 가장 크거나 작은 것부터 대입하여 최적 방식을 구한다.(그리디 알고리즘) 0 - 1 Knapsack Algorithm: 주어진 자원이 0 또는 1, 즉 존재하거나 존재하지 않는, 쪼갤 수 없는 상태면 DP를 사용해야한다. 보통 후자의 문제가 자주 나온다. 그래서 쪼갤 수 없는 보석이 나오면 제로원, 디피.. 2023. 1. 31.
1/22 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 동적 계획법 (Dynamic Programming) DP, 다이내믹 프로그래밍이라 불린다. 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 큰 문제를 해결하는 것이다. 특정 알고리즘이라기 보다는 하나의 문제 해결 패러다임이다. 일반적인 재귀 방식을 사용하면 동일한 작은 문제들의 값이 여러번 반복되어 시간복잡도가 늘어난다. 이를 해결하기 위해 작은 문제의 값들을 저장하여 중복 계산을 제거하는 DP가 사용된다. DP를 사용하기 위해서는 메모이제이션, 작은 문제들의 값을 저장하는 리스트가 필요하다. 수학적 귀납법, 점화식을 생각해서 풀어야한다. 수학적 귀납법 => n = 1일 때, n = 2일.. 2023. 1. 22.

티스토리툴바