![]()
자료 구조에 대해 왜 알아야 할까? 프로그래밍 문제 중 "탐색" 유형은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 코딩 테스트에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 DFS, BFS가 있는데, 해당 알고리즘을 잘 이해해야만 탐색 유형 문제들을 잘 풀어갈 수 있다. 탐색 알고리즘을 이해하기 위한 필수적인 자료구조로는 스택, 큐, 재귀 함수 등이 있다. 해당 개념을 완벽히 이해하고 넘어가보자! (재귀 함수는 다음 포스팅에서 다루고자 한다. ) 자료 구조, 스택과 큐 자료 구조는 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 자료 구조 중 스택과 큐를 쓰기 위해서는 이를 이루는 두가지 주요 함수에 대해 알아야 한다. 삽..
알고리즘 코딩 테스트 유형 그리디 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 구현: 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 DFS/BFS: 그래프를 탐색하기 위한 대표적인 알고리즘 정렬: 연속된 데이터를 기준에 따라서 정렬 이진 탐색: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하기 다이나믹 프로그래밍: 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 최단 경로: 특정 지점까지 가장 빠르게 도달하는 방법 찾기 그래프 이론: 기타 그래프 관련 이론들 활용한 문제 무작위로 프로그래머스와 백준에 있는 문제를 풀어왔는데, 개념 정리가 필요할 것 같아 책을 보며 정리를 시작한다. 개념 정리 + 관련 문제 풀이 형식으로 포스팅해야겠다. [reference] 도서 "이것..
코테 문제를 풀다보면 "복잡도"라는 개념을 만나게 된다. 알고리즘 문제를 풀때는 보통 시간 복잡도를 의미한다. 프로그래머스를 통해 문제를 풀다보면 몇개의 테스트 케이스에서 시간 제한을 넘겨 통과하지 못한 적이 종종 있었다. 그래서 우선 시간 복잡도에 대한 개념을 정리해보고자 한다. 복잡도의 종류 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘 trade-off 관계 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 알고리즘을 위해 필요한 메모리의 양 표현 방식 빅오 표기법 명칭 $O(1)$ 상수 시간 $O(logN)..
