CS Study (29) 썸네일형 리스트형 DFS & BFS 문제 풀이 1. DFS와 BFS (백준 1260번) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2. 스택 (백준 10828번) 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 직접 작성한 코드) n=int(input()) stack=[] for i in range(n.. 정렬 알고리즘 (문제 풀이) 1. 단어 정렬 (백준 1181번) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 참고 답안) n=int(input()) array=[] for i in range(n): array.append(input()) set_list=set(array) new_array=list(set_list) new_array.sort() new_array.sort(key=len) for i in range(len(new_array)): print(n.. 그리디 알고리즘 (문제 풀이) 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 2 3 4 다음