한걸음씩 천천히

보호되어 있는 글입니다.

👉🏻 이진 탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐핵하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다 - 순차 탐색은 기본적인 형태의 데이터 탐색 알고리즘이다 - Ex) 선택 정렬에 서 매 단계마다 가장 작은 데이터를 찾는 것 - 리스트에서 특정 데이터가 존재하는지 검사할 때 별다른 말이 없다면 기본적으로 순차 탐색을 이용 - 이진 탐색은 기본적으로 리스트가 정렬되어있을 때 사용 가능 - 이 조건을 만족한다면 빠르게 데이터를 탐색할 수 있어 log시간의 시간복잡도를 가질 수 있다 - 탐색 범위를 정해줘야한다 - 중간점: 시작점과..

👉🏻 정렬 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적인 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다 - 데이터의 개수가 적을 때 - 데이터의 개수가 많지만 데이터의 범위가 특정 범위로 한정되어있을 때 - 이미 데이터가 거의 정렬되어 있는 경우 - 값을 기준으로 정렬한 결과를 어떻게?? - 사람은 한 눈에 보이지만, 컴퓨터는 구체적 알고리즘을 통해 명시해주어야한다 1️⃣ 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는데 이터와 바꾸는 것을 반복한다 - 매번 현재의 범위에서 가장 작은 데이터를 골라 가장 앞으로 보내주는 것이다 - 첫 번째 원소 정렬 완료 - 나머지 중에서 가장작은 1 - 처리되지 않은 원소가 하..

👉🏻 DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다 DFS는 스택 자료구조(혹은 재귀함수)를 이용한다 구체적 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다 - 매번 최 상단 원소를 기준으로 해서 방문하지 않은 인접 노드가 있으면 그 인접한 노드로 방문을 수행 👉🏻 DFS 동작 예시 - 방향이 없는 무방향 그래프 - 인접한 노드가 여러개일 수 있다 - 어떤 노드부터 방문할지에 대한 ..

👉🏻 재귀 함수 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다 - DFS를 실질적으로 구현하고자 할 때 자주 사용되는 방법 중 하나 단순한 형태의 재귀 함수 예제 '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다 - 반복적으로 자기 자신을 호출해서 프린트문을 출력함 - 파이썬에서는 최대 재귀 깊이가 정해져있어 별다른 설정 없이 이런 코드를 실행할 경우 오류 메세지와 함께 프로그램 종료 - 컴퓨터 시스템 상에서 함수가 재귀적으로 호출되면 컴퓨터 시스템의 스택 프레임에 이러한 함수가 반복적으로 쌓여 가장 마지막에 호출된 함수가 처리된 이후 그 함수를 불렀던 함수까지 처리되는 방식 - 이러한 형태가 ..

그래프 탐색 알고리즘: DFS / BFS 👉🏻 그래프 탐색 알고리즘: DFS / BFS 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다 DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다 - 다양한 알고리즘에서 특정 조건에 맞는 데이터가 존재하는지, 존재한다면 어떤 위치에 존재하는지 찾고자 하는 목적으로 다양한 탐색 알고리즘을 사용한다 - 국내 대기업 공채에서는 DFS/BFS를 적절히 활용해야 하는 문제가 자주 출제됨 👉🏻 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. - 여러개의 박스를 쌓아..

👉🏻 구현 (Implementation) 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 아무리 알고리즘을 잘 세워도 실제로 코드로 작성해서 프로그램으로 만들지 않으면 알고리즘이 실제로 동작하지 않는다 - 알고리즘 문제를 푸는 과정에서 구현은 반드시 필요한 과정 - 그래서 모든 문제가 구현 유형이라고 할 수 있긴 하다 - 하지만 특별히 '구현 유형'이라고 부르는 것은 문제에서 요구하는 내용이 구현에 맞춰져 있거나 구현이 어려운 문제 흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭 구현 유형의 예시 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제 문..

👉🏻 그리디 알고리즘 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다 그리디 해법은 그 정당성 분석이 중요하다 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다 - greedy: 탐욕적인 - 크루스칼 알고리즘, 다익스트라 알고리즘을 제외하고 그리디 알고리즘이 출제 되면 해당 문제를 풀 수 있는 최소한의 아이디어를 적절히 떠올릴 수 있어야 문제가 풀리도록 출제되는 경우가 많다 🧩 문제 상황 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶다. 이 때 최적의 해는? - 5 + 7 + 9 가 가장 크다 ✅ 단순히 매 상황에..

👉🏻 실전에서 유용한 표준 라이브러리 내장 함수: 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공한다 파이선 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있다 import 구문 없이도 사용 가능 print(), input() 등.. itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공한다 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용된다. 모든 경우의 수를 고려해야하는 경우 효과적 완전 탐색 유형에서 소스 코드를 간결하게 작성하도록 도와줌 heapq: 힙(Heap) 자료구조를 제공한다 일반적으로 우선순위 큐 기능을 구현하기 위해 사용된다 다익스트라(최단경로) 알고리즘 더보기 Dijkstra 알고리즘은 최단 경로를 찾기 위해 사..

👉🏻 함수 함수(Function)란 특정한 작업을 하나의 단위로 묶어 놓은 것을 의미한다 함수를 사용하면 불필요한 소스코드의 반복을 줄일 수 있다 - 특정한 프로그램 안에서 반복적으로 사용되는 작업 자체를 하나의 함수로 묶겠다 - 전체 소스코드의 양을 줄일 수 있다 - 필요할 때 마다 사용한다 🧩 함수의 종류 내장함수: 파이썬이 기본적으로 제공하는 함수 프로그램 개발 전반에서 자주 사용되는 기능을 한데 묶어 파이썬에 준비해 놓고 개발자들이 필요할 때 마다 쓸 수 있도록 제공 input(), print() 등 사용자 정의 함수: 개발자가 직접 정의하여 사용할 수 있는 함수 우리가 어떤 프로그램을 작성할 때 그 프로그램에서 자주 사용되는 기능을 사용자 정의 함수로 정의해서 사용 🧩 함수 정의하기 프로그램에는..