Opal1031

최단 경로(Shortest Path)와 그리디(Greedy) 알고리즘의 기본 개념을 다룹니다. 최단 경로는 그래프에서 출발점부터 도착점까지의 비용이 가장 작은 경로를 찾는 문제입니다.그리디는 매 순간 현재 상황에서 가장 좋아 보이는 선택을 하는 방법입니다.두 주제는 서로 다른 알고리즘이지만, 문제의 조건을 분석하고 적절한 선택 기준을 세우는 것이 중요하다는 공통점이 있습니다.Part 1. 최단 경로1. 최단 경로 문제그래프의 간선에 거리, 시간, 비용과 같은 가중치가 주어질 수 있습니다.A --2-- B| |5 1| |C --1-- D단순히 거치는 간선의 수가 가장 적은 경로가 아니라, 가중치의 합이 가장 작은 경로를 찾아야 합니다.최단 경로 알고리즘은 그래프의 조건에 따..

그래프를 탐색하는 대표적인 방법인 BFS와 DFS를 다룹니다. BFS(Breadth-First Search)는 가까운 노드부터 탐색하고, DFS(Depth-First Search)는 한 방향으로 최대한 깊게 탐색합니다.두 알고리즘은 그래프뿐 아니라 2차원 격자, 연결 요소, 경로 탐색 문제에서도 자주 사용됩니다.1. 그래프란?그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조입니다.노드는 각각의 대상을, 간선은 대상 사이의 연결 관계를 나타냅니다. 예를 들어 사람을 노드, 친구 관계를 간선으로 표현할 수 있습니다.1 - 2| |3 - 4그래프는 간선에 방향이 있는지에 따라 방향 그래프와 무방향 그래프로 구분할 수 있습니다.2. 인접 리스트Python에서는 그래프를 인접 리스트 형태로 표현..

동적 계획법(Dynamic Programming, DP)의 개념과 문제 해결 방법을 다룹니다. DP는 큰 문제를 작은 문제로 나누어 해결하고, 이미 계산한 결과를 저장하여 같은 계산을 반복하지 않는 방법입니다.모든 문제를 DP로 해결할 수 있는 것은 아닙니다. 문제에 반복되는 부분 문제가 있는지, 작은 문제의 결과로 큰 문제를 만들 수 있는지 확인하는 것이 중요합니다.1. 동적 계획법이란?피보나치 수열은 다음과 같이 정의됩니다.F(0) = 0F(1) = 1F(N) = F(N - 1) + F(N - 2) 이를 재귀 함수로 그대로 구현할 수 있습니다.def fibonacci(n): if (n 구현은 간단하지만 같은 값을 여러 번 계산합니다. 예를 들어 fibonacci(5)를 계산하는 과정에서 fibo..

프로그램의 효율성을 판단하는 기준인 시간복잡도를 다룹니다. 같은 결과를 만드는 코드라도 데이터가 많아지면 실행 시간에 큰 차이가 생길 수 있습니다.시간복잡도를 이해하면 단순히 정답을 만드는 것을 넘어, 입력 크기에 맞는 풀이를 선택할 수 있습니다.1. 시간복잡도란?시간복잡도는 입력 데이터의 크기가 증가할 때 연산 횟수가 얼마나 증가하는지를 나타냅니다.실제 실행 시간을 초 단위로 계산하는 것이 아니라, 입력 크기에 따른 연산량의 증가 정도를 표현합니다. 입력 크기는 일반적으로 N으로 나타냅니다.numbers = [1, 2, 3, 4, 5] 위 리스트의 길이가 N이라면, 모든 값을 한 번씩 확인하는 코드는 약 N번의 연산을 수행합니다.for number in numbers: print(number)이 ..

Python에서 자주 사용하는 자료구조인 리스트, 튜플, 집합, 딕셔너리의 특징과 활용 방법을 다룹니다. 자료구조는 여러 데이터를 저장하고 관리하는 방법입니다.같은 데이터를 저장하더라도 어떤 자료구조를 선택하는지에 따라 코드를 더 간결하고 효율적으로 만들 수 있습니다.1. 리스트(List)리스트는 여러 값을 순서대로 저장하는 자료구조입니다. 값의 추가, 삭제, 수정이 가능하며 같은 값이 여러 번 들어갈 수 있습니다.numbers = [10, 20, 30]numbers.append(40)numbers[0] = 5numbers.remove(20)print(numbers) # [5, 30, 40] 리스트는 다음과 같은 상황에 적합합니다.데이터의 순서가 중요할 때값을 추가하거나 삭제해야 할 때같은 값의 중복을..

Python의 반복문을 조금 더 다양하게 활용하는 방법을 다룹니다. 기본적인 for, while 사용법에서 한 단계 더 나아가 중첩 반복문, enumerate(), zip(), break, continue 등을 함께 살펴보겠습니다. 반복문 문제에서는 단순히 코드를 여러 번 실행하는 것보다, 무엇을 반복하고 언제 멈출지를 먼저 정하는 것이 중요합니다.1. 중첩 반복문반복문 안에 또 다른 반복문을 작성할 수 있습니다. 바깥 반복문이 한 번 실행될 때마다 안쪽 반복문은 처음부터 끝까지 실행됩니다.for i in range(3): for j in range(2): print(i, j) 실행 결과는 다음과 같습니다.0 00 11 01 12 02 1 중첩 반복문은 표, 행렬, 좌표처럼 두 개 이상..

이번 글에서는 완전탐색과 백트래킹을 함께 정리합니다. 완전탐색은 가능한 경우를 모두 확인하는 방법입니다.백트래킹은 그 중 의미 없는 경우를 중간에 잘라내며 탐색 효율을 높이는 방식입니다. 코딩테스트에서는 둘을 따로 쓰기도 하고, 함께 섞어서 쓰는 경우도 많습니다.1. 완전탐색이란완전탐색(Brute Force)은 가능한 모든 경우를 빠짐없이 확인하는 방법입니다.문제를 빠르게 푸는 핵심은 "모든 경우를 직접 만들어볼 수 있는가"를 판단하는 것입니다.경우의 수가 작으면 가장 확실한 방법입니다.조건이 복잡해도 일단 전부 검사하면 정답을 찾을 수 있습니다.대신 경우의 수가 너무 크면 시간 초과가 날 수 있습니다.예를 들어 숫자 3개를 골라 합을 구하거나, 문자열의 모든 부분집합을 확인하는 문제는 완전탐색으로 접근..

Python에서 핵심 자료구조 중 하나인 딕셔너리에 대해 다룹니다. 딕셔너리의 기초 문법부터 주요 메서드 및 기능까지 함께 살펴보겠습니다.1. 딕셔너리 (Dictionary)딕셔너리는 데이터를 Key-Value쌍으로 저장하며, 여러 값들을 효과적으로 관리할 수 있는 자료구조입니다. Key데이터를 식별할 수 있는 고유 값 ValueKey와 연결된 데이터 리스트 (List) vs 딕셔너리 (Dictionary) 딕셔너리 생성 및 기본 사용법# 딕셔너리 생성info = {"name": "Alice", "age": 25}# 값 접근print(info["name"]) # 출력: Alice# 값 수정info["age"] = 26print(info["age"]) # 출력: 26 2. 딕셔너리 주요 메서드 및 기능..

이번 글에서는 정렬을 간단히 짚고, 이분 탐색을 중심으로 다룹니다. 정렬은 이분 탐색을 위한 전제 조건이 되는 경우가 많습니다.그래서 정렬 자체는 짧게 보고, 이분 탐색의 원리와 활용에 더 집중해보겠습니다. 정렬에 대한 세부적인 내용은 기초 트랙을 참고하시면 되겠습니다.[Python] Basic #03: 정렬 [Python] Basic #03: 정렬Python에서 정렬을 다루는 방법을 다룹니다. 리스트를 정렬할 때 자주 사용하는 sort()와 sorted(), 정렬 기준을 바꾸는 key, 간단한 함수를 만드는 lambda, 그리고 역순 정렬까지 함께 살펴보겠습니다.1.opal1031.tistory.com1. 정렬은 왜 필요한가이분 탐색은 정렬된 데이터에서만 제대로 사용할 수 있습니다.데이터가 정렬되어 있..

Python에서 정렬을 다루는 방법을 다룹니다. 리스트를 정렬할 때 자주 사용하는 sort()와 sorted(), 정렬 기준을 바꾸는 key, 간단한 함수를 만드는 lambda, 그리고 역순 정렬까지 함께 살펴보겠습니다.1. sort()와 sorted()sort()와 sorted()는 모두 데이터를 정렬할 때 사용합니다. sort()리스트 자체를 직접 정렬nums = [5, 2, 9, 1, 3]nums.sort()print(nums) # [1, 2, 3, 5, 9]list형의 method 중 하나이므로 list.sort()의 형태로 작성한다. sorted()정렬된 새로운 리스트를 반환nums = [5, 2, 9, 1, 3]result = sorted(nums)print(result) # [1, 2, ..