개발새발 로그

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/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 📋풀이방법 1. 가로와 세로 부분, 그리고 가로와세로가 겹치는 윗 부분과 아랫부분을 각각 배열 과 상수로 변수에 저장한다. -이유는 주사위가 계속 굴러갈 때 윗 부분과 아랫부분은 어디에 속해있지않고 계속해서 바뀐다. -하지만 동쪽과 서쪽, 북쪽과 남쪽부분은 굴려도 어디에 영향을 받지 않고 윗부분의 숫자와 아랫부분의 숫자로 정해진다...

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이방법 1.상어좌표 뽑아낸 후 주어진 공간에 상어 좌표는 0으로 만들기! 2. 먹을 수 있는 물고기가 없을 때 까지 반복 -3. BFS로 상어의 현 위치에서 먹을 수 있거나 지나갈 수 있는 물고기가 있는 공간의 좌표와 거리를 배열에 모음(fish_Arr) -4.먹을수 있거나 지나갈 수 있는 물고기 좌표 배열에서 먹을 수 있는 물고기가 있는 좌표와 거리만 추출(pos_Arr) ->이때 먹을..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 📋풀이방법 1. 주어진 문자열을 3개씩 변수로 나눈다. 2. 주어진 명령어 p에 따라 반복한다. 3. p가 R이면 뒤집어준다. 4. p가 D면 앞의 요소를 빼준다. 4-1. 만약 m=0이면 error를 체크해준다. 5. 모든 반복이 끝나면 error체크유무에 따라 error를 정답 배열에 넣거나 명령어수행된 배열을 정답 배열에 넣는다. 내 제출 const fs = require("fs"); const filePath = process.platform =..