본문 바로가기

🧑‍💻코딩 테스트/알고리즘5

[코딩테스트/알고리즘] 그래프(Graph) - 그래프의 표현 이번 글에는 그래프를 표현하는 방법에 대해 알아보도록 하겠다. 정점 : {1, 2, 3, 4, 5, 6} 간선 : {(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 6), (3, 6), (4, 6)} 1. 인접 행렬 V개의 정점이 있을 때 V ☓ V 사이즈의 이차원 배열을 통해 나타낸다. 정점 i와 정점 j가 연결되어있을 때 A[i][j] = 1 정점 i와 정점 j가 연결되어있지 않을 때 A[i][j] = 0 예시 1 2 3 4 5 6 1 1 0 0 1 0 2 1 1 0 1 0 3 0 1 1 0 1 4 0 0 1 1 1 5 1 1 0 1 0 6 0 0 1 1 0 2. 인접 리스트 리스트(배열)를 이용해서 구현한다. 리스트는 크기를 동적으로 변경할 수 있어야 한.. 2022. 12. 9.
[코딩테스트/알고리즘] 그래프(Graph) - 그래프 종류, 그래프 용어 1. 그래프란 그래프는 자료구조의 일종으로 정점과 간선으로 나타낸다. 정점(Vertex) : 노드(Node)라고도 불리며 데이터가 저장된다. 간선(Edge) : 정점 간의 관계를 나타낸다. V개의 정점과 E개의 간선을 가진 그래프 G는 G = (V, E)로 나타낸다. 2. 그래프의 종류 1) 방향이 있는 그래프 그래프의 간선 간에 방향이 있는 그래프 A → C로 가는 간선은 있다. C → A로 가는 간선은 없다. 2) 방향이 없는 그래프 (양방향 그래프) 그래프의 간선 간에 방향이 없는 그래프 A - C 간에 간선의 방향이 없다. A - C는 A → C 와 C → A를 나타낸다. 3) 간선이 여러개인 그래프(Mumtiple Edge) 두 정점 사이에 간선이 여러 개인 그래프 아래 그래프는 A - B를 연.. 2022. 10. 27.
[코딩테스트/알고리즘] 브루트 포스(Brute Force) 브루트 포스 브루트 포스는 가능한 모든 경우의 수를 다 시도해보면서 문제를 푸는 방식이다. 이때, 경우의 수를 모두 해보는데 걸리는 시간이 문제의 제한시간을 넘기지 않아야 한다. 예시) 숫자로만 이루어진 n자리 비밀번호 알아내기 비밀번호의 자리수 가능한 범위 경우의 수 입력 하나에 1초로 따진 소요시간 4자리 0000 ~ 9999 10000가지 10000초 = 약 2.7시간 5자리 00000 ~ 99999 100000가지 100000초 = 약 1일 3시간 6자리 000000 ~ 999999 1000000가지 1000000초 = 약 11일 12시간 12자리 000000000000 ~ 999999999999 1000000000000가지 1000000000000초 = 약 31688년 브루트 포스로 문제를 풀기.. 2022. 9. 2.
[코딩테스트/알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. 1940년 Richard Bellman이 처음으로 Dynamic Programming이란 단어를 사용했는데 멋있어 보여서 이름 붙였다고 한다. (궁금해서 찾아보니까 벨만-포드 알고리즘의 그 벨만이 맞았다.) 다이나믹 프로그래밍으로 문제를 풀기 위한 조건 1. Overlapping Subproblem 문제를 작은 문제로 쪼갤 수 있다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. 2. Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 각 문제들은 Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정.. 2022. 8. 29.

티스토리툴바