개발새발 로그

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로www.acmicpc.net 풀이방법1. 세 개의 장대 -> 시작 장대, 나머지 장대, 목적지 장대라는 기준을 둔다.2.  두 번의 수행과정을 거쳐야함  - 1. 첫번째로 맨 밑의 원반을 제외한 원반들은 모두 나머지 장대에 옮겨져야한다.    -그래야 맨 밑의 원반이 목적지 장대로 갈 수 있다.    -원반의 개수가 몇개던 간에, 시작 장대(start)에서 목표기둥(final)으로 모든 원반을 옮기기 위해서맨 밑의 ..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net push나 pop을 사용하면 시간초과가 뜨는 문제다 배열의 연산시간상 맨 앞 요소의 삭제 & 추가하는 연산이 index 수정시간하는 시간이나 다름없기 때문에 연결리스트를 만들어서 사용해야 한다. JS는 연결리스트가 없어서 직접 만들어주면 된다. ☝링크드리스트 링크드리스트는 노드로 이루어져 있고 val, ref,add 저장 - find 를 위해서는 시간복잡도 O(n) - random access를 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📋풀이방법 1. 주어진 빨강, 초록, 파랑의 값을 아래의 점화식으로 처리한다. dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + rgb[n][0] dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + rgb[n][1] dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + rgb[n][2] - dp배열안에 각각의 색..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 📋풀이방법 1. 1과 2와 3으로 만드는 것이므로 일단 1, 2, 3의 숫자를 만들 수 있는 경우의 수를 수동으로 세본다. 2. 그럼 아래와 같이 나오게 된다. 3. 이후의 숫자를 다시 수동으로 적으면서 찾아보자 4. 이때 규칙이 생기는데 이전에 구했던 1, 2, 3 의 경우의 수를 이용할 수 있게 된다. 🤟내 제출 var fs = require('fs'); var inputs = fs.readFileSync('/dev/stdin').toString().split('\n').map(v=>Numb..

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/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 📋풀이방법 1. 주어진 탑의 높이를 차례로 순회하면서 스택의 top부분과 비교한다. - 1. 스택의 top의 높이가 더 작을 경우 스택의 top부분이 검사하는 높이보다 커질 때까지 pop하면서 반복한다. - 2. 만약 스택의 top높이가 더 클 경우 정답에 해당 높이의 인덱스를 넣고, 검사하는 높이를 스택에 넣어준다. - 3. 만약 스택이 비어있을 경우 검사하는 높이의 값을 스택에 넣어준다. 그..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선순위 큐를 활용해야하는 문제이다. 📋풀이방법 1.최소힙 구조로 우선순위 큐에 주어진 값을 넣고, 루트노드를 두 개 A와 B의 뺀 값 C를 total값에 누적하고, 다시 최소힙에 더한 값 total을 넣으면 원하는 결과가 나온다. 2. 이 때 중요한 것은 우선순위큐 구조를 만드는 것이다. https://chamdom.blog/heap-using-js/ [자료구조] JavaScrip..