알고리즘

[C++] 백준 4963번 섬의 개수

그래프 탐색 문제. 연결 요소의 갯수를 찾아서 출력하는 문제이다. 문제 접근 방식 문제를 읽어보면 섬의 개수를 세는 것을 말한다. 섬은 그래프를 의미하며, 그래프가 총 몇 개가 만들어지는지, 즉 연결요소의 개수가 몇 개인지를 물어보는 문제이다. 그리고나서 DFS를 이용해서 재귀함수로 풀었다. 코드를 살펴보자면, w, h를 입력받고 땅과 바다를 입력받는 world배열을 만들었다. 그리고 연결요소의 갯수를 나타내는 result 변수를 만들었다. dfs 메서드에서는 높이나 너비가 1보다 작거나 최대값보다 클 경우 return하도록 만들었다. 그리고 1이 아닌경우, 즉 바다인 경우(0)나 이미 방문한 경우(2) 리턴하도록 만들었다. 이 둘도 아니고 땅을 방문했을 경우 방문한 상태(2)로 만들어놓고 해당 섬에서 ..

[C++] 백준 11052번 카드 구매하기

다이나믹 프로그래밍 문제. 재귀로도 해보고 그리디로도 해보는 등 시도를 많이해보고 맞췄다. 처음 이 문제를 봤을 때 1. 처음에는 재귀함수를 사용해서 풀었었다. 카드의 시작번호를 함수에 설정해두고, 수열을 만드는 방식을 사용해서 1,1,1,1 1,1,1,2 1,1,1,3 ... 이런식으로 호출하는데 카드의 총 갯수가 n을 넘지 않는 선에서만 함수를 호출하도록 했다. 결과는 시간초과였다. 따라서 다른 방식으로 시도하려고 했다. 2. 두번째는 그리디를 사용해서 풀었다. 카드마다 가성비가 좋은 것을 골라서 그 카드를 최대한 많이사서 갯수를 맞추는 식으로 풀었다. 우선순위 큐를 사용해서 풀었다. 우선순위 큐에서 각 각 수를 입력을 받을때 카드의 갯수가 최대가 됐을 때에 가격에 따라 정렬했다. 예를들어 4개의 카..

하노이의 탑 알고리즘 공식

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 백준에 있었던 하노이의 탑 이동 순서 문제. 공식만 알면 쉽게 풀 수 있는 문제인 개념이므로 개념을 정리해 보겠다. 하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 ..

[C++] 백준 1966번 프린터 큐

자료구조 큐를 사용해서 푸는 문제. 큐의 선입선출 구조를 이용해서 문제를 풀면된다. 문제 풀이 문제를 다 읽으면 어떤 방식으로 구현해야 하는지는 이해하기 쉽다. 테스트 케이스 중 6 0 / 1 1 9 1 1 1을 입력하게 되면 pop되는 순서를 알아보자면 최대값 9, 맨 앞 1 맨 뒤로 간다. 최대값 9, 맨 앞 1(원래 첫번째) 맨 뒤로 간다. 최대값 9, 맨 앞 9(원래 두번째) pop된다. 최대값 1, 맨 앞 1(원래 세번째) pop된다. 최대값 1, 맨 앞 1(원래 네번째) pop된다. 최대값 1, 맨 앞 1(원래 다섯번째) pop된다. 최대값 1, 맨 앞 1(원래 0번째) pop된다. 최대값 1, 맨 앞 1(원래 첫번째) pop된다. 따라서 우리가 구하고 싶은 0번째 수는 5번째에 pop되는 것..

[C++] 백준 1874번 스택 수열

자료구조를 이용해서 푸는 문제. 스택 ADT에 대한 이해가 잘 돼있다면 쉽게 머리속에 그려낼 수 있다. 접근 방법 우선 예시로 주어진 테스트 케이스 1번 [4, 3, 6, 8, 7, 5, 2, 1]을 이용해서 살펴보자. 입력은 오름차순으로 이루어지므로 1, 2, 3, ...의 순서로 입력된다. 입력을 받을때마다 다음의 상황을 고려한다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 같다면 스택에 push한 후 pop한다. 이 때 수열에 넣어야하는 수와 스택에 있는 수가 같다면 계속해서 pop해준다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 다르다면 스택에 push만 한다. 예시상황으로 한번 살펴보겠다. 1 : 스택에 push하면 스택이 { 1 }의 상황이고 수열 [4, 3, 6, ..

[C++] 백준 10844번 쉬운 계단 수

다이나믹 프로그래밍 문제. 생각보다 너무 어려워서 이틀동안 계속 머리에 담아두다가 구글링의 도움을 받고 풀었다. 접근 방법 먼저, N자리 수는 N이 1일때는 1~9 2일때는 다음과 같다. 맨 앞자리가 1일때 : 10, 12 맨 앞자리가 2일때 : 21, 23 ... 맨 앞자리가 9일때 : 98 3일때는 다음과 같다. 맨 앞자리가 1일때 : 101, 121, 123 맨 앞자리가 2일때 : 210, 212, 232, 234 ... 맨 앞자리가 9일때 : 987, 989 따라서 다음과 같은 정리가 가능하다. 마지막 숫자가 0이라면 다음으로 갈 수 있는 수는 1 뿐이다. -> 마지막 숫자 앞의 수가 1인 경우만 마지막 숫자가 0이 가능하다. 마지막 숫자가 9라면 다음으로 갈 수 있는 수는 8 뿐이다. -> 마지..

[C++] 백준 9461번 파도반 수열

다이나믹 프로그래밍 문제. 친절하게 P(1)부터 P(10)까지의 값이 모두 주어졌다. DP는 Bottom Up 방식으로 풀면 주어지는 값이 많으면 많을수록 유추하기 쉽기 때문에 풀기 쉽다. 문제풀이 주어지는 값들의 규칙을 찾아보면 점화식을 바로 찾을 수 있다. n>=4일때, An = A(n - 2) + A(n - 3) 이다. 코드가 짧다. n이 4부터 시작하므로 1, 2, 3값은 초기화를 미리 시켜준다. 그리고 자료형은 long long으로 해주어야 오버플로우가 나지 않는다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creating ..

[C++] 백준 11727번 2xn 타일링 2

다이나믹 프로그래밍 문제. 처음에 이 문제를 풀 때 점화식을 잘못잡아서 계속 답이 이상하게 나왔었다. 그래서 어떤 방식으로 푸는지 구글링의 도움을 좀 받았는데, 역시 점화식을 구해서 푸는 방식이였다. 이런 문제 유형도 있음을 알아두어야 될 것 같다. 문제 접근 방법 먼저 An을 구할 때, A(n-1)에서 한 칸만 더 추가되는 방식이다. 이 때 2x1이 추가되는 것과 마찬가지 이다. 따라서 A(n-1)에서 2x1을 추가한 것 A(n-2)에서는 2 x 1 두개 추가한 것 : 그러나 이 방식은 A(n-1)에서 2x1을 추가한 것에 포함되어 있다. 1 x 2 두개 추가한 것 2 x 2 추가한 것 A(n-3)부터는 어차피 이미 다 포함되어 있으므로 생각할 필요가 없다. 따라서 점화식은 An = A(n-1) + 2..

[C++] 백준 10773번 제로

0을 부르면 최근에 적은 값을 지우고 아니라면 값을 넣는 문제. 최근에 있는 값을 빼야한다. -> 스택 문제 스택 자료구조를 쓰면 쉽게 풀 수 있다. 쉽게 맞출 수 있는 문제라 생각한다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creating an account on GitHub. github.com 코드는 위에서 확인이 가능하다.

[C++] 백준 2193번 이친수

DP 문제 이런 류의 DP 문제는 항상 1부터 차례대로 해 보면서 점화식을 세우는 것이 중요하다. 시도 방식 & 문제 풀이 점화식을 구해서 코드로 구현했다. 규칙성이 바로 보이므로 점화식을 찾는데는 문제가 없었다. 근데 여기서 N이 90이 되면 엄청나게 큰 수가 된다. 따라서 dp배열을 int가 아닌, long long형태의 배열로 만들어 주는 것이 중요하다. 처음 시도는 TOP DOWN방식의 재귀형태로 시도했는데, 시간초과가 났다. 그리고 위 방식대로 풀었는데, OVERFLOW가 나서 틀렸습니다 가 나왔다. 자료형을 바꾸고 나서는 바로 맞출 수 있었다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kim..