알고리즘

[C++] 백준 2206번 벽 부수고 이동하기

그래프 탐색 문제. 최단 거리를 탐색하는 문제로, BFS를 응용해서 풀면된다. 조건을 따지지 못해서 검색을 했는데, 코드를 약간 수정해서 맞출 수 있었다. 처음에 이 문제를 접근했을 때 N x M의 맵이고, 벽은 1이고 땅은 0이다. 그리고 상, 하, 좌, 우를 이동할 수 있다. 1로 된 곳 중 하나를 부숴서 갈 수 있다. 나는 다음과같은 조건들을 고려했다. BFS로 점들을 이동하며, 내가 이 점에 왔을 때 벽을 부수고 온 것인지 아닌지를 고려했다. 만일 이전에 벽을 부수고 왔다면, 이번 정점에서는 벽을 가지 못하도록 했다. 이전에 벽을 부순적이 없다면, 벽을 부쉈다는 것을 기록하고 해당 벽을 방문한다. visit 2차원 배열을 만들어서 해당 지점을 방문한 것을 저장했다. 빨간색으로 칠한 이유는 저 부분..

[C++] 백준 2447번 별 찍기 - 10

분할 정복 / 재귀 문제. 알고리즘 분류를 보고나서, 이 문제를 어떻게 분할 정복 / 재귀로 풀 수 있을까 하는 생각을 많이 했던 것 같다. 규칙을 찾으면 쉽게 풀 수 있던 문제였다. 문제풀이 그동안 백준에서 풀어왔던 분할 정복 / 재귀문제는 색종이 자르기와 같이 자기 자신과 같거나 다르면 나누는 문제였다. 그래서 이 문제를 보았을 때 처음에 어떻게 분할해서 나눌수 있을까 생각을 많이했다. 위처럼 그림을 다 그려보고(9x9 그려서 복붙했다.)나서 어떻게 일반화할 수 있을지 생각해보았다. 그리고 어떤 조건에서 '*'이 그려져야 하고, 어떤 조건에서 ' '이 그려져야 하는지 생각해보았다. 아무리 생각해도 조건이 그려지지 않았다. 그래서 다르게 생각해 보았다. 어떤 경우에 공백이 그려져야 하는가? 공백이 나오..

[C++] 백준 1992번 쿼드트리

분할 정복 / 재귀 문제 예전에 이 문제를 풀려고 고민을 많이 해봤는데 도저히 모르겠어서 검색해봤는데, 분할 정복 알고리즘을 재귀로 구현해서 푸는 문제였다. 오늘 분할 정복 알고리즘을 정리해서 풀었더니 쉽게 풀 수 있었다. 정답 비율이 높은 이유가 있었다. 문제풀이 예전에 색종이 만들기 문제와 비슷하다. 다만 이 문제같은 경우에는 자를 때 해당 색이 무엇이고, 출력을 어떻게 해야하는지가 추가된 문제이다. 가로, 세로의 길이를 입력받는 widthHeight와 판의 정보를 입력받는 board 배열이 있다. 먼저, 현재 좌표의 숫자를 받는다. 그 후 해당 색종이의 모든 색이 같은지 확인하는 same 변수를 만든다. 만일 이중 for문에서 다른 색이 있으면 same 변수를 false로 만들어 준다. 다른색이 있..

[C++] 분할 정복 & 재귀 정리

최근 백준 문제를 푸는데, 분할 정복 & 재귀 알고리즘을 사용하는 문제가 있는데 못 풀어서 정리를 해야할 것 같아서 개념 정리를 한다. 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 위 문제는 분할 정복 & 재귀의 아주 간단한 문제이다. 분할 정복이란? 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 빠른 정렬이나 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸..

[C++] 백준 1107번 리모컨

브루트 포스 완전탐색 문제. 이 문제는 두 번 풀게됐는데, 처음에 푼 완전탐색 코드에서 시간이 다른 사람들에 비해 너무 많이 나와서 백준 게시판을 참고해서 다시 풀게됐다. 정답 비율이 낮지만 반례를 보면서 디버깅을 하다보면 풀 수 있었던 문제다. 글 읽기 - [반례모음] 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 반례는 위 사이트를 참고했다. 문제풀이 TV를 보는데 현재 채널이 100이다. 그리고 채널을 돌리려고 하는데, 일부 숫자가 고장이 났다. +버튼은 +1채널, -버튼은 -1채널인데 0채널에서는 변화하지 않는다. 조건은 간단하다. 위 조건만 고려해주면된다. 처음에 푼 방식은 조건을 나누어서 계산해서 풀었다. 모두 +로 계산했을 때, 모두 -로 계산했을 때, 숫자로 최대한 가까..

[C++] 백준 3190번 뱀

구현 문제. 표현이 애매해서 처음에 이해하기가 어려웠던 문제였던 것 같다. (예를들어 벽에 부딪히는게 1 또는 마지막 칸을 의미한다고 생각했는데, 그게 아니고 그냥 최대 범위를 넘어가는 게 부딪힌다는 뜻이였다.) 그래서 방향이 위일때 위 벽에, 오른쪽일때 오른쪽 벽에 이런식으로 고려를 해주다 보니 예외처리가 상당히 많아졌었다. 그러나 그냥 DFS처럼 범위만 예외처리 해주면 되는 조건이였다. 테스트 케이스들로 그림을 그려보면서 풀면 풀 수 있는 문제. 문제 풀이 맨 처음 뱀은 1, 1의 좌표에서 시작을 하고 방향은 오른쪽(→)이다. 그리고 뱀은 1초마다 이동을 하는데 다음과 같은 조건이 붙는다. 이동한 곳에 사과가 있다면 꼬리를 그대로 둔다. (길이가 1 늘어난다.) 이동한 곳에 사과가 없다면 몸을 한칸 ..

[C++] 백준 14500번 테트로미노

브루트 포스 / 구현 문제. 모든 경우를 다 확인하는 코드를 작성하면 맞출 수 있다. 문제풀이 문제는 위와같은 경우의 수들로 나뉘어져 있다. 이 모든 경우의 수를 고려해주면 된다. 빨간색으로 칠해진 원은 시작점이 저기일때라고 가정한 것이라고 생각하면 된다. 처음에는 해당 부분을 탐색하는 것을 일일이 따로 예외로 두어서 구현해 보았는데 틀렸습니다가 나왔을 때 고려해 줄 부분을 찾기가 너무 어려웠다. 따라서 이 코드를 다 지우고 새로운 방법으로 찾았다. 코드를 살펴보자. 우선 결과값을 매번 갱신하기 위해, max() 메서드를 사용하려고 algorithm STL을 사용했다. 그리고 위처럼 하드코딩을 하지 않게 하기위해 Direction 클래스를 만들어서 현재 좌표에서 각 네 칸을 어떻게 더해줘야 할지 pair..

[C++] 백준 7562번 나이트의 이동

그래프 탐색 문제. 나는 보통 배열을 쓸 때 1부터 쓰는 습관이 있는데, 이 습관이 이 문제에서는 정말 좋지 않게 작용했다. 초기화만 잘 해준다면 어렵지 않게 풀 수 있는 문제였다. 문제 풀이 문제가 대놓고 BFS (너비 우선 탐색)이라는 것을 말해주고 있다. 친절하게 그림으로도 나와있다. 각 테스트 케이스마다 좌표를 입력받고 BFS를 돌려가면서, 현재 몇 번째 탐색인지를 기록해나가며 최초로 발견한 곳에서의 번째 탐색을 찾으면 할 수 있다. 바로 코드로 살펴보자. BFS를 하기 위해 queue STL을 사용했다. testCase : 입력받는 테스트 케이스의 개수이다. widthHeight : 각 테스트 케이스마다 입력받는 가로 세로의 길이이다. board 배열 : 해당 지점을 탐색했는지 flag를 세우기..

[C++] 백준 2583번 영역 구하기

그래프 탐색 이론 문제. 백준에서 최근에 판에 색종이 올리고 남은 공간에 넓이를 구하는 문제가 있었는데, 그 문제를 푼게 도움이 많이 됐다. 어렵지 않게 풀 수 있는 문제 문제풀이 문제가 연결요소의 개수를 구하는 것을 물어보고 있다. 그리고 좌표를 알려주면서 해당 영역에 사각형이 붙여져 있다는 것을 알려준다. 좌표계를 처럼 나타내려면 조금 복잡해서, 편하게 위 아래로 뒤집은 형태로 구현해서 풀었다. 어차피 연결요소 개수는 달라지지 않을테니까. 101x101 짜리 배열을 하나 선언해서 입력받는 좌표에 따라서 해당 영역들에 이미 사각형이 있다는 것을 표시해주고, 표시되지 않은 곳에서 DFS를 해서 표시되지 않은 곳 끼리 한 영역이 되게 구현하면 된다. 좌표는 나같은 경우는 한 칸을 좌표 다음으로 보아서 (0..

[C++] 백준 2003번 수들의 합 2

처음에 DP라고 생각하고 풀어서 맞췄다. 알고보니 투 포인터 문제였다. 투 포인터가 무엇인지 몰랐는데 이 문제가 대표적인 투 포인터 문제라고 한다. 투 포인터란? 1차원 배열에서 두 개의 포인터를 가지고 조작하면서 원하는 값을 얻는 알고리즘이다. 이 때 배열의 모든 원소는 자연수여야만 투 포인터 알고리즘이 가능하다. 문제 접근방식 처음 내 풀이는 DP로 풀었다. 시간 제한을 보아도 DP밖에 방법이 떠오르지 않았다. 동적 계획법 Bottom Up 방식을 사용해서 문제를 풀었다. 그리고 각 자리수가 증가할 때마다 해당 다음 번째 수에 있는 값을 더해 나간다고 생각하고 풀었다. 예시 입력을 예로들면, dp가 결과값을 담는 배열이고 num이 각 값을 담는 배열이라 할 때 N = 10, M = 5이고 원소가 1 ..