알고리즘/Baekjoon

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

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

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

[C++] 백준 14503번 로봇 청소기

구현 / 시뮬레이션 문제. 구현하는 문제는 뭔가 테스트 케이스가 많이 필요한 것 같다. 아래 올린 링크에서 테스트 케이스를 보고 나서야 풀 수 있었다. 글 읽기 - [로봇 청소기] 테스트 케이스(반례) 공유합니다. 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 구현 문제는 뭔가 이해하기도 어렵고, 이해했다쳐도 이걸 코드로 어떻게 짜야할지 잘 생각이 안난다. 무한루프와 틀렸습니다를 거치고 반례를 통해 문제점을 찾은 후에야 맞출 수 있었다. 처음 이 문제를 봤을 때 처음에는 그냥 현재 보는 방향에 따라 모든 조건을 다 걸어주려고 했다. 그런데 이렇게 짜면 예외처리할 상황이 너무 많기도 하고, 코드도 너무 비효율적으로 길어지는 것 같아서 다른 방법을 생각해봤다. 방향이 0, 1, 2, 3으..

[C++] 백준 10026번 적록색약

그래프 탐색 문제. 그래프 탐색 문제는 문제를 잘 이해하고 코드로 잘 구현하면 어렵지 않게 맞출 수 있다. 골드 문제지만, 쉽게 맞출 수 있는 문제였다. DFS로 풀면 최악의 경우 100 * 100번 탐색하므로 10,000번 이므로 시간 내에 완벽하게 풀 수 있다. 문제풀이 어려운 문제는 아니다. 그냥 연결요소의 개수를 구하는 문제인데, 적록색약이 빨간색과 초록색을 같은 색으로 보는 것을 유의하면서 문제해결을 해주면 된다. memset() 메서드를 사용해서 초기화 하기위해 cstring STL을 사용했다. widthHeight : 입력받는 길이 n board 배열 : 입력받는 그리드를 저장하는 char 배열이다. visit 배열 : DFS를 할 때 이미 방문한 곳인지 체크하는 배열이다. normalRes..

[C++] 백준 15686번 치킨 배달

구현 및 브루트 포스(완전 탐색) 문제. 처음에 잘못된 백트래킹과 dfs로 접근해서 시간초과를 많이 냈다. 백준 게시판에서 도움을 얻고, 겨우 풀었다. 처음 이 문제를 봤을 때 백트래킹으로 폐업시킬 치킨집을 정하고 그래프 탐색으로 (처음에는 BFS로 하려 했으나 코드로는 DFS로 했다.) 최단거리에 있는 치킨집의 거리를 다 구해서 더하고 어떤 치킨집들을 폐업시킬 때 최소 거리가 나오는지 구하려 했다. 이 방법은 시간초과가 났고, 게시판을 참고한 결과 다음과 같은 도움을 얻었다. 폐업시킬 치킨집을 고르는 것이 아닌, 그냥 치킨집들 중 어떤 치킨집들을 open할 지 결정하면 된다. 각 집들의 거리와 치킨집들의 거리를 저장해두고 쓰면, 굳이 도시들을 다시 살펴보지 않아도 된다. 이 두개가 이 문제의 keypo..