For Better Code Tomorrow

[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++] 문자열(문자)을 정수형처럼 다루는 메서드

isdigit(Char c) : c 문자가 정수형으로 변환될 수 있는지 확인한다. atoi(char* c) : c 문자열을 정수형으로 변환한다. 이 때, string 형일 경우 반드시 str.c_str() 메서드를 호출하도록 한다. stoi(string s) : s 문자열을 정수형으로 변환한다.

[C++] Map 자료구조 사용하기

1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net Map 자료구조란? Key, Value를 쌍으로 가지는 자료구조로, Key에 따른 Value가 저장되는 형태를 갖는다. 여러 개의 같은 Value는 가능하지만 여러 개의 같은 Key는 불가능하다. 위 문제가 아마 Map 자료구조의 대표문제일 것 같다. C++에서 사용하는 법은 선언은 위처럼 할 수 있다. map STL을 include한 후, map 이름 으로 선언한다. map은 자동으로 pair자료형을 사용하고 있다. (key와 va..