반응형 개인공부/코테 및 알고리즘4 [알고리즘] 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence) 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence) 혹은 최장 증가 부분 수열은 대표적인 동적 계획법(Dynamic programming) 문제다. 아래와 같이 특정 길이의 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 찾는 것이 문제이다. 아래 예시에서는 {10, 20, 30, 50}의 부분 수열이 수열 A의 가장 긴 증가하는 부분 수열이고 길이는 4이다. A = {10, 20, 30, 15, 25, 50} 가장 긴 증가하는 부분 수열 문제는 간단한 O(N^2)의 알고리즘과 조금 복잡한 O(N log N) 두 가지 알고리즘으로 해결 가능하다. O(N^2) 알고리즘 동적 계획법에서는 어떻게 값을 재사용하는가를 결정하는 .. 2021. 1. 31. 코딩테스트 준비할 때 필수 개념! <완전탐색> 알아보기 이번에 알아볼 주제는 완전탐색이다. 흔히 브루트-포스 알고리즘(Brute-force algorithm)이라고 불리는데 특별한 알고리즘은 아니고 무식하게 모든 경우를 탐색해보는 알고리즘이다. 모든 경우를 다 탐색하는 알고리즘이기에 정확성은 100% 보장되지만 반대로 속도는 최악이다. 따라서 문제에서 주어진 데이터가 매우 적을 때만 사용 가능하다. 예시로 든 문제들 모두 데이터의 개수가 매우 적은 것을 확인할 수 있다. 보통 완전탐색 문제는 for문과 if 문을 활용하거나 BFS/DFS를 활용하는 경우가 대부분이다. 다른 블로그를 찾아보면 백트래킹이나 비트마스크를 활용한다고 하는데, 사실 백트래킹도 주로 DFS를 활용해서 구현하고 비트마스크도 특정 알고리즘이라기보다 bit를 활용한 일종의 테크닉이기 때문에 .. 2020. 12. 14. 코딩테스트 준비할 때 필수 개념! <기본 자료구조> 알아보기 이번에 알아볼 주제는 기존 자료구조이다. 기본 자료구조라고 하면 스택, 큐, 힙 등을 말하는데 코딩 테스트에서 출제되는 빈도는 보통 정도이다. 하지만 기본 자료구조는 다른 문제를 풀 때 기초가 되기에 꼭 알아야 한다. 스택이나 큐 같은 경우는 구현이나 DFS/BFS 문제를 해결할 때 자주 사용되고, 또 힙 같은 경우는 스택과 큐에 비해서 조금 생소하지만 모르면 못 푸는 문제들이 있기 때문에 꼭 알아둬야 한다. 사실 코딩 테스트에서 출제되는 문제들은 응시자가 기본 자료구조를 알고 있는지 확인하기 위해서 출제되는 것은 아니고, 기본 자료구조를 활용해서 어떤 아이디어로 어떻게 구현할지를 물어보는 문제가 대부분이다. 이번 포스팅에서는 기본 자료구조의 개념에 대해서 설명하기보다 파이썬에서 어떻게 기본 자료구조를 .. 2020. 12. 10. 코딩테스트 준비할 때 필수 개념! <문자열 처리> 알아보기 기본적으로 코딩 테스트를 준비할 때 그리디, 구현(Implementation), DFS/BFS, 다이나믹 프로그래밍을 주로 공부한다. 물론 이 네 가지의 출제빈도가 높기 때문에 중요한 것은 사실이다. 하지만 항상 이 부분만 출제되는 것은 아니다. 특히 카카오 같은 경우 문자열 처리가 필요한 문제를 많이 내기 때문에 문자열 처리와 정규표현식을 알고 있다면, 남들보다 쉽고 빠르게 알고리즘 문제를 해결할 수 있을 것이다. 출제된 문자열 처리 문제 2018 카카오 블라인드 채용 1차 "다트게임" 2019 카카오 개발자 겨울 인턴쉽 "불량사용자" 2019 카카오 블라인드 채용 1차 "매칭 점수" 꼭 알아둬야 할 Python 문자열 처리 함수들 개인적으로 가장 많이 쓰는 언어가 파이썬인 영향도 있지만 코딩 테스트를.. 2020. 12. 7. 이전 1 다음 반응형
