전체 글

[C++] 백준 1654번 랜선 자르기

이분 탐색 문제. 이분 탐색 문제이고 실버3 문제임에도 고려해줄 사항이 생각보다 많아서 반례를 한번 찾아보고 풀었다. 처음 문제를 봤을 때 처음에는 우선순위 큐로 만들어서 긴 랜선들을 자르는 식으로 구현해보려고 했다. 그런데 문제 아래에 힌트를 보면 이렇게 나와있었고, 결국 우선순위 큐를 이용하는 그리디 방식의 풀이는 틀렸다는 것을 알게됐다. 랜선 자르기 같은 문제를 예전에 풀었던 적이 있었는데, 이분 탐색으로 풀었던 기억이 있어서 이분탐색으로 시도했고, 몇번 구상해보니 확실히 이분탐색이라는 것을 알게됐다. 문제 풀이 문제가 이분탐색이라는 것을 알게되면 그 뒤로는 간단하다. 나같은 경우는 vector 배열에 담고, algorithm STL에 있는 sort 메서드를 사용해서 정렬해 준 후에 1 ~ [입력받..

[C++] 백준 11057번 오르막 수

다이나믹 프로그래밍 문제. 지난번에 풀었던 쉬운 계단 수 문제와 비슷한 문제였다. [C++] 백준 10844번 쉬운 계단 수 다이나믹 프로그래밍 문제. 생각보다 너무 어려워서 이틀동안 계속 머리에 담아두다가 구글링의 도움을 받고 풀었다. 접근 방법 먼저, N자리 수는 N이 1일때는 1~9 2일때는 다음과 같다. 맨 앞자리 kimyunseok.tistory.com 지난 번에 이 문제를 풀었을 땐 풀기 어려워서 못 풀었었는데 비슷한 이문제는 비교적 쉽게 풀어서 이 때 정리를 나름 잘 한것 같아서 뿌듯했다. 문제 접근 방식 처음에 문제를 보자마자 위에서 설명했듯 쉬운 계단수를 풀었던 기억이 떠올렸다. 다이나믹 프로그래밍이라고 바로 생각했고 마지막 수에 따라 자리수의 마지막 수 이전에 어떤 수가 올 수 있는지 ..

[C++] 백준 1541번 잃어버린 괄호

문자열을 파싱하는 문제. 식을 해석하는 문제는 나같은 경우는 큐 자료구조를 이용해서 많이 푼다. 문제 접근 방식 우선 어떻게 해야 식의 값이 최소가 되는지를 알아보려고 했다. 식에 더하기와 빼기밖에 없으므로, 어떤 경우로 식을 처리를 해야 최소값이 될 수 있을지 혼자 식을 따로 적어서 생각해 보았다. 일단 식의 계산을 맨 앞에 숫자부터 해야된다고 가정할때, 10+20-10-20+30-20 -> 10+20-10-(20+30)-20 다음 식 같은 경우를 만들어서 살펴보았는데 다음과 같은 두 가지 경우를 고려하게 되었다. +의 경우는 그냥 앞에서 계산한다. -의 경우, 바로 뒤의 식이 +이면 +를 먼저 계산한다 (즉, 괄호를 씌워준다.) / 아니라면 그냥 앞에서 계산한다. 이렇게 고려해줄 경우 식의 값이 최소..

[C++] 백준 1904번 01타일

다이나믹 프로그래밍 문제. 점화식이 바로 보여서 쉽게 풀 수 있지만 왜 그렇게 되는지도 생각해서 풀어보았다. 문제풀이 나는 위에 같은 경우로 경우의 수를 나누었다. 그림에 대한 설명을 하자면 N = 1, 1 -> 1개 N = 2, 00, 11 -> 2개 N = 3, 001, 100, 111 -> 3개 N = 4, 0000, 0011, 1001, 1100, 1111 -> 5개 N = 5, 00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111 -> 8개 여기까지만 해도 An = A(n-1) + A(n-2)라는 결과를 얻을 수가 있다. 그러면 왜 그렇게 되는 것일까? An은 A(n-1)에서 한 자리가 추가되는 것이다. 한 자리가 추가되는 것은 무조건 타일 1이 추가..

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

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

[C++] 2차원 배열 0, -1로 초기화하기 memset 메서드 사용

C++에서 2차원 배열을 바로 초기화하는 메서드가 있다. memset이라는 메서드이다. memset(배열이름, 초기화시킬 값, 초기화시킬사이즈) 로 사용한다. 사용 예시는 위와같다. 위 처럼 사용할 경우, world배열의 모든 값이 다 0으로 초기화 된다. 초기화는 0 또는 -1로 초기화가 가능하다. memset의 시간복잡도나 이중 포문으로 초기화 시키는 것이나 큰 차이는 없다고 한다.

[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, ..