알고리즘
-
[ CS 기술면접 ] 알고리즘 예상질문 모음 !공부 !/Computer Science 2022. 5. 22. 01:01
알고리즘 질문 모음 # Adjacency Matrix, Adjacency List, UnionFind, LIS ✅ 인접 행렬과 인접 리스트의 장단점을 서로 비교하며 설명해 주세요. 어떤 경우에 무엇을 사용하는 것이 더 유리한지를 중점으로 설명해주시면 됩니다. 인접행렬의 경우 구현하기 쉬우며 빽빽한 그래프를 구현할때 좋습니다. 어떤 정점과 어떤 정점 사이 간선이 존재하는지 확인하기도 쉽습니다. 하짐나 어떤 점과 연결된 모든 노드를 방문하려면 O(V) 시간만큼이 걸립니다. 또한 공간복잡도가 O(V^2) 로 정점의 개수 V가 커질수록 메모리가 더 많이 필요합니다. 인접리스트의 경우 듬성듬성한 그래프로 구현할때 좋습니다. 어떤 정점에 연결된 다른 모든 정점들을 쉽게 방문할 수 있습니다. 하지만 어떤 정점과 어떤..
-
[ Algorithm ] 피보나치수열 알고리즘 비교 (재귀, DP, 반복)공부 !/Computer Science 2022. 4. 22. 20:55
피보나치수열 알고리즘 비교 (재귀, DP, 반복) 피보나치 수열에 많이 사용되는 알고리즘 3가지를 비교해보자 ! 피보나치 수열은 첫번째와 두번째 값이 1이며 이후는 f(n) = f(n-1) + f(n-2) 점화식을 갖는다 피보나치 수열에 많이 사용되는 3가지 알고리즘은 재귀, 반복, DP가 존재하는데 먼저 3가지 알고리즘의 복잡도를 비교해보면 재귀 O(2ⁿ) DP O(n) 반복 O(n) 이다 재귀 & DP & 반복 차이점 일반적으로 재귀는 함수가 함수 내에서 자신을 호출하는 것으로 동일한 함수가 여러번 반복되는 것이다 DP 는 큰 문제를 작은 문제로 쪼개고 그 답을 저장해두었다가 재활용한다 그렇기 때문에 재귀에서 동일한 문제가 여러번 반복된다는 비효율적인 부분을 DP로 해결할 수 있다 DP 로 작은 문제..
-
Kruskal Algorithm 크루스칼 알고리즘 ?!Algorithm/Source Code 2022. 3. 22. 14:12
Kruskal Algorithm 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다 다시 말해 최소비용 신장트리를 만들기 위한 대표적인 알고리즘 ! 프로그래머스 섬 연결하기 문제를 풀다가 개념을 정리한다 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 노드와 간선 노드 = 정점 = 도시 를 의미하며 동그라미에 해당하는 부분이고 간선 = 거리 = 비용 을 의미하며 선에 해당하는 부분이다 예시로 살펴보면 아래 그래프는 노드가 4개 간선이 5개 이다 핵심개념 간선을 거리가 짧은..
-
[프로그래머스 알고리즘 문제 해설] 나머지 한 점Algorithm/Source Code 2022. 1. 4. 13:27
문제 설명 직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 구하려고 합니다. 점 3개의 좌표가 들어있는 배열 v가 매개변수로 주어질 때, 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 return 하도록 solution 함수를 완성해주세요. 단, 직사각형의 각 변은 x축, y축에 평행하며, 반드시 직사각형을 만들 수 있는 경우만 입력으로 주어집니다. 제한사항 v는 세 점의 좌표가 들어있는 2차원 배열입니다. v의 각 원소는 점의 좌표를 나타내며, 좌표는 [x축 좌표, y축 좌표] 순으로 주어집니다. 좌표값은 1 이상 10억 이하의 자연수입니다. 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 [x축 좌표, y축 좌표] 순으로 담아 return 해주세요..