꾸준하게 차근차근

[baekjoon 1326] 폴짝폴짝 (BFS) (C++)

www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 문제는 개구리가 징검다리를 뛰어다니는데, 그 징검다리에는 각각 숫자가 써져있고 개구리는 자신이 서있는 징검다리의 숫자의 배수만큼 점프할 수 있다. 즉, 10개의 징검다리에서 1 2 3 4 5 6 7 8 9 1 이 써져있고 2번에서 9번까지 가고 싶다면 처음 징검다리 2번의 경우 : 2가 써져있으므로 2의 배수인 4 6 8 10을 각각 한 번의 점프로 방문이 가능하다. 그 이후 10의 경우 : 1이 ..

[baekjoon 2447] 별 찍기 - 10 (재귀 호출) (C++)

www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 재귀를 이용해서 별 찍기 문제이다. 그림처럼 사이즈가 3일 때는 가운데만 뚫려있고, 나머지 case는 재귀적으로 주위에 이전 단계 도형이 그려지고 가운데가 뚫려있게끔 출력하면 된다. 사이즈가 27이면 주변이 위에 있는 사이즈 9의 도형이 둘러싼다. 처음엔 재귀를 이용하되, 함수 자체에서 cout을 하면 되겠다고 생각했지만, 개행을 해주면 재귀적으로 출력을 하기 힘들다고 판단했고, 2차..

[baekjoon 11729] 하노이의 탑 이동 순서 (재귀 호출) (C++)

www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 유명한 하노이의 탑 문제이다. 재귀를 하나하나 따라가며 이해해보려고 했는데 쉽지가 않았다. 재귀를 이용한 문제는 재귀의 모든 흐름을 파악하기보다는, 호출의 의미와 재귀 함수와 호출의 관계를 생각해야겠다. 하노이의 탑의 공식은 1. N-1개의 원판을 첫 번째 기둥에서 두 번째 기둥으로 옮기고 2. 마지막 하나 남은 원판을 첫 번째 기둥에서 세 번째 기둥으로 옮기고(출력) - 하나의 원판을 옮기는 경우..

[baekjoon 2146] 다리 만들기 (그래프, BFS) (C++)

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 주어진 섬들 중에 최단 경로를 구하면 되는 문제이다. 처음에 어떻게 풀면 할까, 하다가 N이 최대 100이길래 완전 탐색 느낌으로 거리를 구하면 되겠다.라고 생각했다. 내 풀이법은 일단 1. BFS를 통해서 연결된 섬에 대한 정보를 얻는다. 2. 이후에 vector v[5001]의 2차원 벡터에 땅 하나에 맞춰서 벡터에 좌표를 넣어준다. ex) 첫 번째 BFS 수행 -> 첫 번째 땅 탐색이므로 v[0]에 좌표값들 (..

[Linux] 리눅스 관련 정리(+ Putty)

보통 원격 서버를 접속할 때 putty를 이용해서 접속한다. www.putty.org/ Download PuTTY - a free SSH and telnet client for Windows Is Bitvise affiliated with PuTTY? Bitvise is not affiliated with PuTTY. We develop our SSH Server for Windows, which is compatible with PuTTY. Many PuTTY users are therefore our users as well. From time to time, they need to find the PuTTY download link. W www.putty.org download here을 눌러서 여..

[baekjoon 2110] 공유기 설치 (이진탐색) (C++)

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net N개의 좌표점 위에 C개의 공유기를 설치하는 것이다. 각각의 좌표값에 공유기를 설치할 때 가장 인접한 거리 중 최댓값을 출력하는 것이다. 1 4 6 7 9에서 5개의 공유기를 설치한다고 하면 모든 좌표값에 설치하는 경우가 되겠다. 그리고 가장 인접한 거리는 1이 될 것이다. (6-7의 거리가 1로 가장 인접하다.) 3개를 설치한다고 가정하면 1 4 7 또는 1..

[baekjoon 11725] 트리의 부모 찾기- 트리, 그래프, BFS, DFS (C++)

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트는 1로 고정되어있고, 각 노드들의 부모를 출력하면 되는 문제이다. 일단 벡터를 통해 양 노드의 값을 저장해주고, DFS탐색을 노드 1부터 해준다. 트리의 특성상 리프 노드를 제외하고 연결되어 있으므로 연결된 노드를 통해 탐색해주면서, 부모를 저장해준다. 현재 x노드를 방문한 상태에서 x와 연결된 y가 아직 방문되지 않았다는 것은 y는 x의 자식 노드라는 의미이다. 방문하지 않았다면 DFS(연결된 다음 노드)를 진행해주면서 parent [연결된 다음 노드] = 현재 노드..

[baekjoon 2011] 암호코드- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net DP개념을 사용하면 되지만, 나름 처리해야 하는 예외들이 몇 가지 있어서 3번째 제출에 맞췄다. 기본적으로 나는 2차원 배열을 이용해서 1. [n][0]에는 결합하지 못하고 그냥 붙는 경우 2. [n][1]에는 결합할 수 있어서 해석의 가짓수가 늘어나는 경우로 나눴다. 1)의 경우는 42 같은 경우이다. 42는 결합되지 못하고 db라는 해석 한 가지밖에 없다. 2)의 경우 26 같은 경우이다. 26은 bf와 z라는 해석 두 가지..