잡담연구소

www.acmicpc.net/problem/12611261번: 알고스팟첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미www.acmicpc.netIDEA좌측 상단에서 우측 하단 까지 가는데 벽을 최소 몇 개 부숴야 하는 지 묻는 문제다. 여러가지 방법으로 풀 수 있겠지만, 이 또한 다익스트라 로 풀었다. 풀고보니 bfs 같은 느낌도 있다,,,좌측 상단 = 시작 지점 부숴야 하는 벽의 개수 = 비용 으로 바라보면 시작지점부터 어떤 한 정점(우측 하단) 까지의 최소비용을 묻는 문제로 바꿔 생각할 수 있다. 음,,, 다익스트라 예제를 검색하면 ..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net IDEA 버스의 출발도시 , 도착도시 , 버스 비용이 차례대로 주어지고 , 출발점의 도시번호로부터 도착점의 도시번호까지 가는 최소비용을 구하는 문제다. 즉, 한 점에서 다른 한 점까지 가는 최소비용을 구하는 문제이다. 다른 풀이법도 있을 수 있겠지만, 한 점에서 모든 정점까지 가는 최소비용을 구할 수 있는 다익스트라 알고리즘을 이용해서 풀었다. 다익스트라 알고리즘의 대표예제 수..

1 ) 다익스트라란 ? : 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘 그래프의 방향 유무는 상관없다 간선 중 하나라도 가중치가 음수라면 사용할 수 없다. 이런 경우는 벨만포드를 사용한다. 플로이드 와샬은 모든 정점에서 모든정점까지의 최단 거리를 구하지만 , 다익스트라는 한 정점에서부터 모든 저점까지의 최단 거리를 구하는 알고리즘이다. 다익스트라가 DP문제인 이유는 최단 거리는 여러개의 최단 거리로 이루어져있기때문이다. 코드를 보면 한 점까지의 최단거리를 구할 때 이전까지의 최단거리로 사용하는걸 확인할 수 있다. ✨최단 거리를 구하는 알고리즘이 꽤 많다. 각 알고리즘마다의 어떤 점이 다른 지를 기억하고 있어야한다. 2 ) 다익스트라 알고리즘의 원리 리스트로 단순구..

www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1

www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net IDEA DP를 풀고나서 풀었더니 또 DP스럽게 생각을 하게 돼버렸다. 난 초반에 문제 이해가 잘 안됐는데 문제 설명을 다시 해보자면 K개 이상의 라이언 인형 = 1 을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력하는 문제다. -> 어차피 가장 작아야하므로 라이언 인형이 k개일때의 부분집합의 크기를 생각해주면 된다. N= 10, K =3일 때, 1 2 2 2 1 2 1 2 2 1 이렇게 보면 라..

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net IDEA LIS 알고리즘을 이용하는 문제다. 최근에 공부했어서 그런지 보자마자 보이네 헿 기존 LIS의 알고리즘의 문제점은 길이는 알 수 있어도 그 길이에 해당하는 원소들을 알 수 없다는 것이었다. 11055번은 그걸 물어보는 문제같다. 어떤 원소들이 가장 긴 부분 수열을 이루는지! 수열의 크기가 1000이라서 시간 복잡도 O($n^{2}$) 풀이를 사..