본문 바로가기

자료구조 & 알고리즘 & cs

 (88)
[TIL] 탐욕 알고리즘 - Greedy Algorithm 탐욕 알고리즘 최적의 해에 가까운 값을 구함 매 순간 최적이라고 생각되는 경우 근사치 추정에 활용 -> 반드시 최적의 해를 구하는 것은 아님 관련 문제 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 식을 입력받아 괄호를 적절히 사용하여 값을 최소로 만드는 문제이다. 이 문제에서는 최소의 값을 구하는 것이 최적의 해를 구하는 것이므로 그리디 알고리즘을 사용하여 해결한다. 문제를 분석해보았을 때 - 다음 + 연산이 나올 경우 괄호를 사용하면 최소값을 구할..
[python] 백준 24479번, 24444번 - DFS, BFS 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 (acmicpc.net) 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 24444번: 알고리즘 수업 - 너비 우선 탐색 1 (acmicpc.net) 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v..
[TIL] 그래프- BFS, DFS BFS(Breadth First Search) 너비 우선 탐색 알고리즘 정점들과 같은 레벨의 노드들을 먼저 탐색 (형제 노드들) 파이썬에서 딕셔너리와 리스트를 이용하여 표현 그래프 표현 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'E', 'F'] graph['D'] = ['B', 'G', 'H'] graph['E'] = ['C'] graph['F'] = ['C', 'I'] graph['G'] = ['D'] graph['H'] = ['D'] graph['I'] = ['F'] BFS 구현 큐를 활용 (방문한 노드 저장(visited), 방문할 노드 저장(need-visit) - 파이썬에서 리스트로 구현 d..
[TIL] 그래프- 개념 그래프(Graph) 실제 세계의 현상이나 사물을 정점Vertex(노드)와 간선Edge으로 표현하기 위해 사용 루트 노드, 부모/자식의 개념이 존재하지 않음 용어 정점(Vertex)/노드(Node) : 위치 간선(Edge)/link/branch : 위치 간의 관계를 표시한 선 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(Path Length) : 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path) : 처음/끝 정점을 제..
[TIL] 탐색 알고리즘- 이진 탐색, 순차 탐색 이진 탐색(Binary Search) 작은 문제 해결 후 이를 이용하여 큰 문제를 해결 - 분할 정복 정렬된 상태의 리스트를 이용 def bs(data, search): if len(data)==1 and search == data[0]: return True if len(data)==1 and search != data[0]: return False if len(data) == 0: return False medium = len(data)//2 if search == data[medium]: return True else: if search > data[medium]: return bs(data[medium+1:], search) else: return bs(data[:medium], search) 이..
[TIL] 동적 계획법 - DP, Dynamic Programming 동적 계획법(DP) 작은 문제 해결 후 이를 이용하여 큰 문제를 해결 상향식 접근법 (보텀업) Memoization 기법(하향식/탑다운) Memoization? = caching - 프로그램 실행 시 이전의 값을 저장하여 중복되는 계산 횟수를 줄여 실행 속도를 빠르게 하는 기술 동적 계획법 문제 풀이 1904번: 01타일 (acmicpc.net) 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 동적계획법 문제이다. 피보나치 수열을 해결하는 방법과 똑같아서 코드를 작성하였는데 메모리 초과가 떴다. import sys..
[python] 백준 18870번 - 좌표압축 (시간초과 문제) 18870번: 좌표 압축 (acmicpc.net) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 자체는 어렵지 않았다. 입력받은 리스트에서 중복을 제거하기 위해 set()을 사용한 후 다시 리스트로 변환하고 이를 정렬하여 정렬된 수의 인덱스 값이 곧 그 수의 좌표 압축한 결과가 된다. 시간 초과가 계속 떠서 알아본 결과 처음 인덱스 값을 구하기 위해 index()를 사용하였는데 시간복잡도가 O(n)이기 때문에 시간초과가 발생했다. 그래서 이를 해결하기 위..
[python] 백준 2108번 - 통계학 2108번: 통계학 (acmicpc.net) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 정렬 알고리즘 학습 후 위 문제를 풀었는데 그 중 최빈값을 구하는 알고리즘을 정리하려고 한다. 산술평균, 중앙값, 범위의 경우 이제까지 공부한 내용으로 무리없이 작성하였으나 최빈값을 구하는 과정에서 조금 고민했다. 파이썬에서 최빈값을 구하기 위해서는 collection 모듈의 Counter 클래스를 사용해야한다. Counter 클래스는 dic 클래스의 하위클래스로 리스트나 튜플에서 데이터의 등장 횟수를 사전형식으로 반환한다. Cou..
728x90

티스토리툴바