본문 바로가기

전체 글

 (120)
그리디 알고리즘 (문제 풀이) 1. 설탕 배달 (백준 2839번) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 직접 작성한 코드) n=int(input()) count=0 k=n five= k//5 k=k%5 three=k//3 k=k%3 while True: if k==0: print(five+three) break elif five 0: n -= 3 p += 1 if n % 5 == 0: p += n // 5 print(p) break elif n == 1 or n == 2: ..
최단 경로 알고리즘 최단 경로 알고리즘이란? - 가장 짧은 경로를 찾는 알고리즘 - 지점은 그래프에서 노드로 표현, 지점 간 연결된 도로는 그래프에서 간선으로 표현 문제 상황 1) 한 지점에서 다른 한 지점까지의 최단 경로 2) 한 지점에서 다른 모든 지점까지의 최단 경로 3) 모든 지점에서 다른 모든 지점까지의 최단 경로 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. - 음의 간선이 없을 때 정상적 동작 - 그리디 알고리즘으로 분류된다. (매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.) - 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다. 다익스트라 알고리즘의 동작 과정 1) 출발 노드를 설정한다. 2) 최단..
다이나믹 프로그래밍 다이나믹 프로그래밍이란? (동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 일반적으로 두가지 방식으로 구성된다.(top down, bottom up) * 자료 구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미하지만, 다이나믹 프로그래밍에서 다이나믹은 별 다른 의미 없이 사용된 단어이다. - 다이나믹 프로그램인 문제가 다음의 조건을 만족할 때 사용할 수 있다. 1) 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2) 중..
다이나믹 프로그래밍 2 (이론 정리) Dynamic Programming(DP)는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임이다. DP는 왜 사용할까? 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 발생한다. 그럼 한 번 구한 작은 문제의 결과 값은 저장해두고 재사용하자! 가 DP의 사용 이유이다. 분할 정복과 무엇이 다를까? 작은 문제가 중복이 일어나는지, 안일어나는지에 따라 차이가 있다. 분할 정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나지 않는다. 동적 프로그래밍은 작은 부분 문제들이 반복이된다. Memoizat..
이진 탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. -> 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. ex. 시작점, 중간점, 끝점을 기준으로 내가 찾고자하는 원소가 중간점보다 작을 경우 중간점~ 끝점 까지는 탐색을 하지 않아도 된다. ➡️ 끝 점을 중간점 왼쪽으로 옮기고 중간점을 다시 설정한다. ➡️ 위 과정을 반복한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2 N에 비례한다. 즉 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)을 보장한다. 파이썬 코드 def binary_sear..
기본 정렬 알고리즘 정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 기준에 맞게 정렬하여 출력하는 알고리즘이다. 많은 종류의 알고리즘이 있고, 시간 복잡도와 공간 복잡도가 다 다르다. 대표적으로 많이 사용하는 몇가지만 우선적으로 학습할 예정이다. 1. 선택 정렬 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다. progress 1) 주어진 배열 중 최소값을 찾는다. 2) 그 최소값을 가장 앞에 위치한 값과 바꾼다. 3) 가장 앞에 위치한 값 뺀 나머지 배열에서 동일한 동작을 반복한다. 8 7 2 5 4 ➡️ 최소값 2와 가장 앞에 위치한 8을 바꾼다. 2 7 8 5 4 ➡️ 2는 자리가 고정된 상태이다. 이는 제외하고 동일한 과정을 반복한다. 최소값 4와 가장..
정렬 정렬이란?? - 데이터를 특정한 기준에 따라 순서대로 나열하는 것. - 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨. 1. 선택 정렬 - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. #직접 작성한 초기 코드 array=[7,5,9,0,3,1,6,2,4,8] for i in range(len(array)-1): min_num=array[i] num=array[i+1] index=i+1 for j in range(len(array)): if(jarray[j]: index=j num=array[j] if min_num>num: array[index]=min_num array[i]=num print(array) #답안 for i ..
DFS vs BFS 그래프를 탐색하는 방법에는 DFS, BFS가 있다. DFS는 Depth-First Search 즉 깊이 우선 탐색을 말하고, BFS는 Breadth-First Search 너비 우선 탐색을 말한다. (그래프란 node와 node를 잇는 edge로 이루어진 자료구조를 말한다.) 그럼 DFS와 DFS의 차이점을 알아보자. ✅ DFS의 개념 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 먼저 다 탐색하는 방식을 말한다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. BFS보다 간단하지만 느리다. ✅ BFS의 개념 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다. 루트 노드에서 시작해서 인접한 노드를 먼저 탐색을 하는 방식이다. 시작 정점으로부터 가까운 정점을 먼저..

티스토리툴바