개발새발 로그

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 📋풀이방법 1. BFS를 이용한다 2. visited라는 100100정도 크기의 배열을 선언해서 0으로 초기화해준다 -이 배열은 걷기와 순간이동을 할 때 같은 곳을 방문하지 않도록하기 위한 배열임 3. queue에 시작점 N과 시간초 cnt를 넣어주고 visited[N]=1로 방문표시를 해준다. 4. queue에서 하나씩 빼면서 N이 K가 되면 반복을 종료해준..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프(Bipartite Graph)란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는( 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 한다. 풀이방법 1. 테스트 케이스마다 다른 그래프가 형성된다. 2. u ->..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 📋풀이방법 1. 상하좌우 DFS로 뻗어나간다. 2. 이때 -1로 초기화한 2차원 배열 dp에 목적지까지 도착했는지에 대한 값을 기록한다. 3. 기록하면서 만약 -1이 아니고(방문을 했고) 그 좌표에 값이 있다면 그 값을 return함으로 써 뻗어나가지 않고, 미리 도착을 예상할 수 있다. 🤟내 제출 const fs = require("fs"); const filePath = process.platfor..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 문제이다. 최소힙을 구현했어야했지만 나는 queue을 이용해서 방믄하지않은 노드 중 가장 짧은 거리의 노드를 선택하는 기능을 넣어 구현했다. https://ydoag2003.tistory.com/41 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단경로탐색 알고리즘입니다. 이전에 배운 크루스칼 알고리즘은 최소비용 신장트리이다. ..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 이전에 포스팅했던 위상정렬의 문제다 https://ydoag2003.tistory.com/43 위상 정렬 위상정렬 순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정하기 위해 사용하는 알고리즘 위상정렬을 통해 여러개의 순서를 조건에 부합하는 일직선의 순서로 만든다. 배고픔 -> ydoag2003.tistory.com 📋풀이방법 1. 연결되어있음..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 📋풀이방법 ✅서로소집합 알고리즘을 이용하면 간단하게 풀 수 있다. https://ydoag2003.tistory.com/22 그래프이론(서로소집합) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 합집합(uni ydoag2003.tist..

https://www.acmicpc.net/status?user_id=oridori2705&problem_id=11404&from_mine=1 채점 현황 www.acmicpc.net 전형적인 플로이드 와샬 알고리즘문제이다. 플로이드 와샬 알고리즘이란? 기존에 다익스트라 알고리즘은 [하나의 정점에서 출발 했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘]입니다. 만약 [모든 정점에서 모든 정점으로의 최단 경로]를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야합니다. https://ydoag2003.tistory.com/42 플로이드 와샬(Floyd warshall)알고리즘 다익스트라 알고리즘은 [하나의 정점에서 출발 했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘]입니다. 만약 [모든..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 📋풀이과정 1. 이동하는 중에 벽을 부셔야한다 -> 이 조건이 중요하다 2. 이동하는 중에 벽을 부수므로 BFS를 뻗어나갈 때 방문표시할 visited 배열을 3차원배열로 해야한다. -> 이유는 만약 가다가 벽을 부수게 된다면 새로운 방문 배열로 간다 -> 새로운 방문배열은 벽을 부순 후의 방문 배열이다. -> 새로운 방문배열에서 새롭게 다시 BFS를 뻗어나간다 ( 즉 벽..