개발새발 로그

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 효율성 문제이다. 투포인터를 이용해서 조건에 맞는 수열의 부분합을 찾는 것이다. 📋풀이방법 1. lt와 rt를 사용해야하므로 선언한다. - lt는 0으로 초기화해주고, rt는 for문을 이용해 N까지 증가하면서 순회한다. 2. 0 ~ N까지 순회하면서 result 변수 안에 주어진 수열 arr에서 arr[rt]를 하나씩 누적해본다. 3. 만약 result가 S보다 크거나 같다면 wh..

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/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이방법 1. 스고쿠 맵안에서 0인 곳의 좌표를 모두 찾아 저장한다. 2. DFS를 호출해 카운트 0부터 시작한다 -이는 0인 곳에 숫자를 넣은 후 +1해서 다시 DFS를 재귀호출한다. 3. DFS를 0부터 시작했으므로 0인 곳의 좌표를 저장했던 배열도 인덱스 0부터 시작한다. -0인 곳의 좌표를 순차적으로 뽑아내서 그 안에 숫자를 넣을 것이다. 4. 1 ~ 9까지의 숫자를 모두 넣어보고 가로열,..

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/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ' 풀이방법 1. 가려고하는 채널을 기준으로 하는 것이 아닌 0번 채널 ~ 9999999번 채널을 모두 탐색하면서 답을 찾는 것이다. 2.먼저 100번에서 +,- 만 눌렀을 때의 누른 횟수와 3. 0~9999999번 채널을 눌러가면서 찾은 최소 누른 횟수를 비교한다 0~9999999번 채널 탐색 1. 예를 들어 순회하면서 현재 50번이라는 채널까지 왔다고 가정하자, 그리고 가려고하..

https://www.acmicpc.net/status?user_id=oridori2705&problem_id=17298&from_mine=1 채점 현황 www.acmicpc.net 📋풀이방법 1. 스택을 이용해서 문제를 풀어야한다. 2. 위 그림대로 주어진 배열의 숫자를 하나씩 검사한다. 🤟내 제출 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let input = fs.readFileSync(filePath).toString().trim(); input = input.replace(/\r/g, "").split("\n"); let [N, temp] = input;..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 이전에 포스팅했던 알고리즘을 활용한 문제이다. https://ydoag2003.tistory.com/23 그래프 이론(크루스칼 알고리즘) 크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다. 즉 최소 비용 신장트리를 만들기 위한 대표적인 알고리즘이 yd..