알고리즘/Baekjoon

[C++] 백준 2468번 안전 영역

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net (문제가 길어서 캡쳐화면 대신 링크로 대체) 그래프 탐색 문제. 그래프 탐색에 브루트 포스(완전 탐색)를 곁들인(?) 문제이다. 문제를 이해하는 것도 어려웠고, 생각해야할 조건들도 까다로웠다. 문제풀이 일단 문제를 잘 해석해보면 연결 요소의 개수(ConnectedComponents)를 구하는 문제라는 것은 알 수 있다. 그리고 고려해야할 사항들이 있다. 물의 높이보다 낮거나 같으면 물에 잠긴다. 모든 도시가 물에 잠기지 않을 수도 있다. (연결 요소의 개수는 최소 0이..

[C++] 백준 11403번 경로 찾기

그래프 이론 문제. i에서 j로 가는 경로가 있다면 인접 행렬(AdjacentMatrixGraph)로 1을 나타내고 없다면 0을 나타내면 된다. DFS나 BFS를 이용해서 인접 행렬을 업데이트 하면 된다. 처음에는 자기 자신은 무조건 방문하므로 1인줄 알았는데, 두번째 테스트 케이스를 보고서 자기 자신을 돌아올 수 있는 경우에만 1이고 시작에만 자기 자신이 있다면 0이였다. DFS, BFS는 구현만 할 줄 알면 쉽게 풀 수 있다. 문제풀이 그래프 이론 문제는 개념만 알고 있으면 문제를 이해하는 것은 쉬우므로 바로 코드해석을 하겠다. 먼저 정점의 개수 vertex변수. 인접한 정점들의 번호를 담을 벡터 adjList, 각 정점마다 어떤 정점들을 갈 수 있는지 정보를 담을 인접행렬 check 2차원 배열을 ..

[C++] 백준 2293번 동전 1

다이나믹 프로그래밍 문제. 처음에 문제에 접근할 때, 재귀함수로 접근하려 했는데 시간제한을 보고 포기했고, 알고리즘 분류를 보고 DP인 것을 봐도 어떻게 풀어야 할 지 감이 잘 오지 않았던 문제. 많이 고민해봤지만 생각하기 어려워서 결국 솔루션을 보고 해결했다. 이런 방법으로 생각할 수도 있구나라고 생각했다. 풀이를 정리할 겸 글을 적는다. 문제 풀이 먼저 DP문제를 풀 때에는 항상 규칙을 찾아야 한다. 어떻게 Bottom Up 방식을 적용할 것인지 생각해야한다. 예시 케이스인 n = 3 / {1, 2, 5}, k = 5일때의 규칙을 찾아 보자면 1 2 3 4 5 6 7 8 9 10 1가지 { 1 } 1 1 1 1 1 1 1 1 1 1 2가지 { 1, 2 } 1 2 2 3 3 4 4 5 5 6 3가지 {..

[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++] 백준 11052번 카드 구매하기

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

[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되는 것..