본문 바로가기

Algorithm

[백준 2075번][Javascript][NodeJS] N번째 큰 수 2075번: N번째 큰 수 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,500)이.. 더보기
[백준 9184번][Javascript][NodeJs] 동적 계획법 (DP; Dynamic Programming) DP란? 동적 계획법(DP)이란 복잡한 문제를 부분적인 문제(subproblem)로 나누어 푸는 방법을 말한다 최적 부분구조(Optimal Substructure) 라고 하는 큰 문제와 세부 문제와의 관계를 설정 예를 들어, 1번 줄에서부터 10번 줄까지의 어떤 조건에 따라 계산을 하는데 2번 줄에서의 계산 방식과 7번 줄에서의 계산 방식이 동일하다고 할 때, 생각해볼 수 있다 동적 계획법은 분할 정복과 비슷하나, 분할 정복은 계산한 부분 문제를 한 번만 쓰기 때문에 메모이제이션이 필요하지 않다는 차이점이 있다 메모이제이션이 무엇인가 ? function DFS(n) { if(n == 1 || n == 2) {...} if(memo[n] === 0) { ... DFS(n-1); DFS(n-2); memo[.. 더보기
[C] 위상정렬(Topology Sort) 개념 및 정리 위상정렬 위상정렬(Topology Sort)은 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정해주기 위해 사용하는 알고리즘이다 위상정렬에 대한 이해를 위해 아래의 그래프를 참고해 보자. 아래의 그래 프는 작업의 순서를 그래프로 나타낸 것이다. 이 그래프에는 부분 순서 관계가 있다. 1번 작업을 하기 위해서는 2번 작업을 먼저 완수해야 한다. 7번 작업을 진행하기 위해서는 3번, 또는 6번 또는 8번 작업을 완료해야 한다 이때 작업의 순서는 2, 1, 3, 4, 7과 2, 5, 4, 6, 7과 같은 두 가지 계열로 나누어 있음을 알 수 있다. 1번 작업과 5번 작업은 계열이 다르므로 어떤 작업을 먼저 수행해도 상관없다. 이와 같이 전체 그래프의 모든 노드가 아닌 일부 노드에 대해서 선후 관계를 가.. 더보기
[백준 2178번][C] 미로 탐색 (BFS) snupi.tistory.com/107 [C] 너비 우선 탐색(BFS; Breadth First Search) 개념 및 정리 개념 너비 우선 탐색(BFS; Breadth First Search)은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘으로, 동작 과정이 직관적이여서 이해하기 쉽다 (a)의 그래프에서, a를 탐색의 시작점 snupi.tistory.com 이 문제 역시 기본적인 최단 경로 문제이다 최단 경로 알고리즘은 BFS의 가장 큰 장점이므로 이를 활용해보자 adj 행렬(, 미로)의 크기 및 칸의 정보를 입력받는다 인접한 칸을 queue에 push 시킨다 queue가 빌 때까지 pop 하며 인접한 칸의 정보를 push 시킨다 (BFS) 0. 전역변수 설정 #define MAX 102 .. 더보기
[백준 2667번][C] 단지번호붙이기 (DFS) snupi.tistory.com/106 [C] 깊이 우선 탐색(DFS; Depth First Search) 개념 및 정리 개념 트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색(search) 알고리즘이라고 한다 깊이 우선 탐색(DFS; depth-first search)은 그래프의 모든 snupi.tistory.com 다음 문제는 백준 2667번 단지 번호 붙이기 문제이다 전형적인 DFS 또는 BFS 그래프 경로 순회 문제이다 배열의 인접한 부분을 탐색하며 단지 수를 카운팅한다 더불어 나눠진 컴포넌트가 있는 그래프이므로 몇 개의 컴포넌트인지 파악까지 해야 한다 마지막으로, 단지 수를 오름차순으로 출력한다 0. 전역 변수 설정 #include #define .. 더보기

티스토리툴바