방주영의 코딩 블로그

CS 공부/알고리즘

누적 합

데이터 배열에서, 특정 구간의 합을 빠르게 계산하기 위해 미리 배열의 앞부터 각 위치까지의 합을 저장해두는 기법int[] arr = {3,2,1,6,3,4,8,6};int[] prefixSum = {3,5,6,12,15,19,27,33}; 구간 합 계산시에 용이하다// [i,j] 구간 합int rangeSum = prefixSum[j] - prefixSum[i-1];

CS 공부/알고리즘

[그래프] 무방향 그래프 표현 방식

1. Adjacency matrix (boolean array) 두 노드가 연결이 되어있으면 1, 연결이 되어있지않으면 0으로 표시하는 방법 1 2 3 4 5 1 0 0 0 1 0 2 0 0 0 1 1 3 0 0 0 0 1 4 1 1 0 0 1 5 0 1 1 1 0 이걸 코딩으로 응용한다고 생각하면 2D boolean 배열을 생각해볼 수 있다. 다만, 이때 node 값을 조심해야한다. 그냥 0번 index를 버릴수도 있고 모든 index에 1을 빼는 방법도 있다. 개인적으로 iteration을 돌 때 오히려 헷갈리기 때문에 index에서 1을 빼는것을 더 선호하나 마지막 output에 신경을 써야한다. boolean[][] graph = {{false, false, false, true, false}, ..

CS 공부/알고리즘

[JAVA] 위상정렬 (Topology Sort) 알고리즘

질문 및 이론 밑의 질문에 대한 답을 역으로 사용해서 위상 정렬 문제인지 판별해라 요약: DAG인가? 선후 관계를 활용하는 문제인가? 순서를 정하는 문제인가? Q) 기본 개념 선행 노드가 없는 노드들부터 탐색을 하고 후행 노드들과의 edge를 끊은 다음 순서에 넣어준다. 모든 선행 노드와의 edge가 끊긴 후행 노드를 queue에 추가해 탐색을한다. Q) 어떤 조건에서 사용하는가? 유형 (방향이 있는) 그래프 싸이클이 없음 즉 DAG (Directed Acyclic Graph) Q) 어떤 문제들에서 사용하는가? 선후관계가 정의된 그래프 구조에서 정렬 순서가 정해져 있는 작업들의 목록들을 가지고 전체 작업 순서를 결정 응용 : 어떤 일을 처리할 때 다른 일들이 처리 되어있어야한다, 이럴 때 일을 진행하는 ..

CS 공부/알고리즘

[그래프] 다익스트라 (Dijkstra) 알고리즘

질문 및 이론 밑의 질문에 대한 답을 역으로 사용해서 다익스트라인지 판별해라 요약: 최단거리를 찾아야하나? 유형 그래픈가? 간선에 가중치가 있나? 시작점(이나 도착점)같은게 하나 주어지나? 근데 최단거리면 그냥 거의 무조건 다익스트라인 경우가 많다.. 일반 기업 코테 레벨 기준 Q) 어떤 그래프에서 사용하는가? 유형 그래프 모든 edge에 (음이 아닌) 가중치가 있음 Q) 어떤 문제들에서 사용하는가? 시작점이 주어졌을 때 다른 모든 점들에게 도달하는 최단거리를 찾는 문제 응용 : 시작점이 아니라 도착점이 하나 정해졌을 때 : 그래프 정보를 받을 때 출발 노드와 도착 노드를 바꿔서 저장해서 간선의 방향을 반대로한 reversedGraph를 만들 수 있다. Q) 어떤 정보를 알고있나? 그래프 정보 노드 갯수..

CS 공부/알고리즘

[Java] 조합 (Combination)과 순열(Permutation)

'모든 경우의 수를 구하시오'(완전탐색)에 대한 문제에서 가장 많이 등장하는 알고리즘이다. 조합 (Combination) 조합 nCr은 n개의 값 중에서 r개의 값을 순서를 고려하지 않고 뽑는 것이다. 간혹 문제와 함께보면 어떤걸 써야하는지 헷갈리는데 필자의 경우 주며니에 담는다라고 생각하면 이해가 빠르다고 느꼈다. 주머니에 공을 넣은 후 주머니의 상태는 공을 어느 순서로 넣었는지는 중요하지 않다. 아래 예시로 조합을 백트래킹과 재귀로 구현하는 법을 알아보겠다. 조합 구현 public class Combination { public static void main(String[] args) { int[] arr = { 1, 9, 5, 4, 3 }; int n = 5; int r = 3; System.out..