나만보는개발공부블로그

문제 설명 한 변의 길이가 N인 정사각형이 있다. 플레이어는 이 정사각형 위에 M개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세려고 한다. 플레이어가 반직선을 그리는 과정은 다음과 같다. 1. 반직선을 그리기 시작한 칸 (y,x)를 정한다. (y,x)는 주어진 정사각형 1x1크기의 정사각형을 나눴을 때, y번째 행의 x번째 열에 해당하는 칸이다. 2. 반직선을 그릴 방향 d를 정한다. 상하좌우중 하나이며 항상 테두리의 가로 혹은 세로와 평행하다. 3. 반직선을 그린다. 반직선은 항상 시작 칸의 테두리에서부터 시작하며 같은 칸을 지나는 평행한 직선이 서로 만나지 않도록 한다. 플레이어가 모든 반직선을 그린 뒤 생기는 중첩 점의 개수를 구해보자. 풀이과정 1. graph를 선언하는데 전부 빈 배..

그래프문제로 union find로 통해 분리하고 주어진 조건에 정렬하는 문제이다. const readline = require('readline'); let rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); let input = []; rl.on('line', (line) => { input.push(line); }); rl.on('close', () => { let [n,m] = input[0].split(" ").map((v) => parseInt(v)); let parent = Array.from({length:n + 1}, (_,i)=>i); let edges = Array.from({length:n ..

백트래킹(Backtraking)이란? - 한국어로 퇴각검색이라고 나온다. 뒤로 돌아가면서 찾아가는 방식? - 어떠한 문제의 해결을 모든 방법(부분적 방법)들을 찾아가기위한 일반적인 알고리즘 - CSP를 해결하기 위해 쓰인다. 이제 CSP가 무엇인지 알아야하는데 CSP(Constarain Satisfaction Problems)는 조건적으로 만족하는 문제들을 이야기한다. - 조합 알고리즘 문제에 대해 모든 가능한 해를 나열하는 것. 결과적으로 모든 조합의 수를 살펴보는데 조건을 만족하는 것들을 해결하기 위한것이라 할 수 있다. 모든 경우의 수를 찾는것보다 경우에 따라가면 더 빨라질 수 있다는 점이 있다. 백트래킹의 함수 참고할 문제 N-Queen www.acmicpc.net/problem/9663 9663..

정의 -Brute-force라고 부르기도 한다. 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 모두 찾아내면서 답을 찾는 방법이다. - 가능한 방법을 전부 만들어 보는 알고리즘 (모든 경우의 수를 찾아내는 알고리즘) 완전탐색방법 -Brute-Force : for문과 if문으로 처음부터 끝까지 탐색 -비트마스크 -순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 -백트래킹 : 분할 정복을 이용한 기법, 재귀함수로 이용함. -BFS(너비 우선 탐색) -DFS(깊이 우선 탐색)

문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지..

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘 최단 경로 알고리즘 종류 -다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘 - 여러개의 노드가 있을 경우 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘. 1. 출발 노드를 설정 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 3번과 4번을 반복한다. const readline = require('readline'); const rl = readline.createInterface({ input: process.stdi..