문제https://www.acmicpc.net/problem/10844고민45656, 3234545 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다.N이 주어지면 길이가 N인 계단 수는 총 몇개가 있는지 구한 뒤 1,000,000,000으로 나눈 나머지를 출력한다.단, 0으로 시작하는 수는 세지 않는다. 처음엔 경우의 수를 다 만들어 봐야하나? 생각했지만 알고리즘 분류가 DP였다.DP는 이전에 계산했던 수를 저장해두고 필요할 때 다시 가져와서 불필요한 추가 연산을 없애는 알고리즘이다. 그렇다면 일단 경우의 수를 따져봐야한다.1. 길이가 1일 때 계단 수는?1, 2, 3, 4, 5, 6, 7, 8, 9 2. 길이가 2일 때 계단 수는?10 | 01 | 12 | 23 | ... | 78 | 89..
동식이 취업시키기 작전/알고리즘
문제https://www.acmicpc.net/problem/1753고민올게 왔다.. 바로 다익스트라 다익스트라는 선택된 곳에서 다른 노드들 까지의 거리다.다른 길찾기 알고리즘 에서는 A에서부터 D까지 가는 방법 중 여러가지였다면다익스트라는 A에서 출발할건데 다른 노드들까지 가는 방법의 비용을 산출하는 거다. (이쯤되면 길찾기 알고리즘은 말만 조금씩 다를 뿐 푸는 방식이 같다는 느낌까지 듦) 문제는 간단하다. 주어진 시작점에서 다른 노드들간의 거리를 구하는 것1. 우선순위 큐를 사용하여 시간복잡도를 줄이기2. 거리가 가까우면 업데이트하기 위 두가지만 고민하면 된다. 나는 2번이 너무 헷갈렸다. 업데이트 하는 로직이 떠오르지 않아서 다른 사람 코드도 봤는데 이해가 힘들었다.현재 노드까지 거리에다가 다음 노..
문제https://www.acmicpc.net/problem/11724고민연결요소란?그래프를 그릴 때 연결된 요소들의 개수를 말한다.즉, 노드가 1~6까지 주어졌을 때 그래프를 그려봤더니1-2-43-56이렇게 연결이 되었다고 하자.그러면 연결요소는 3개다. 문제에서 노드가 6개고 간선이 5개인 그래프가 주어졌다. 아래 연결 정보를 따라 그래프를 그려보면1 - 2 - 53 - 4 - 6이렇게 이어진다.그려면 연결요소는 2개다. 위 과정으로 로직을 고민해봤다.1. 인접 요소를 연결한다.2. 연결이 끝나면 카운트를 한다.끝이다! 겁나 간단하다.코드using System;using System.Collections.Generic;using System.Linq;using System.Text;using Syst..
문제https://www.acmicpc.net/problem/14502고민고민이 코드보다 먼저 나오는게 좋을 거 같아서 수정했습니다. 어떠신가요^.^ 문제를 보면1. 연구실에 벽 3개를 임의로 설치하고2. 바이러스를 감염시킨다.3. 감염되지 않은 공간을 센다.위 세 로직을 반복하여 감염되지 않은 공간이 가장 많을 경우를 출력하면 된다. 우선 1. 연구실에 벽 3개를 임의로 설치이 문장을 보고 nCr(조합)을 떠올렸다. 조합은 백트래킹으로 찾아줬다.만약, 3개의 자리에 a, b, c, d, e를 넣는 경우의 수를 생각해보면a b ca b da b ea c da c ea d e...가 나올 것이다. 나는 이것을 백트래킹이라고 이해했다.재귀로 계속 호출해주면서 하나씩 값을 넣으면 모든 경우의 수가 나온다. 2..
