Brute Force
-
BOJ) 캐슬 디펜스 (17135 번)알고리즘/백준 2021. 2. 3. 18:03
캐슬 디펜스 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 생각보다 많이 어려웠던 문제였다. 적을 제거하는 규칙을 찾아 글로는 정리가 됐지만, 어떻게 코드로 구현해야할지 감이 오질 않았다. 그래서, 다른 블로그 글을 찾았고, 여기글을 많이 참고했다. 궁수가 적을 죽이는 순서는 삼각형을 그렸을 때, 좌측, 상단, 우측의 꼭지점 순서라고 생각하면 편하다. 공격 범위에 따라 위와 같은 순서로 적을 죽이게 된다. 범위 : 1 => y-1 범위 : 2 => (x-1,y-1) ~> (x, y-2) ~> (x+1, y-1) 이런 식..
-
BOJ) 행렬알고리즘/백준 2020. 7. 26. 15:37
행렬 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 풀이 n by m 으로 이루어진 두 행렬이 주어진다. 두 행렬이 같은지 비교하고, 만약 다르다면 3 by 3의 크기만큼 0->1, 1->0 으로 변환할 수 있다. 최소 몇 번을 값을 바꿔야 같아지는지 횟수를 구하는 문제다. 구할 수 없을 때는 -1을 출력한다. Brute force 문제라고 생각해서 전체 탐색을 돌렸다. 특정 알고리즘이 들어가지 않고, 행렬을 비교하고, 다르다면 3 by 3의 행렬값을 뒤짚어주면서 답을 찾았다. 탐색이 끝난 이후에도 한번 더 행렬이 같은지..
-
BOJ) 사탕 게임알고리즘/백준 2020. 7. 24. 22:38
사탕 게임 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고 www.acmicpc.net 풀이 NxN 크기의 보드에 사탕이 가득 채워져 있다. 사탕의 색이 다른 인접한 두 칸을 골라서 서로 교환한다. 이 때, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 or 열)을 고른 다음 그 사탕을 다 먹는다. 사탕을 먹을 수 있는 최대 갯수를 구하는 문제다. 알고리즘을 활용한다기 보다 구현에 가까운 문제라고 느꼈고, 간단하게 풀 수 있었다. 맵을 돌면서, 상하좌우에 있는 사탕과 바꾸고, 상/하로 바꿨을 경우에는 해당 행을 검색..
-
BOJ) 문자열알고리즘/백준 2020. 7. 21. 15:29
문자열 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 풀이 문자열 두개가 주어질 때, 오른쪽 문자열의 길이는 항상 왼쪽보다 크다. 왼쪽 문자열의 맨 앞이나 맨 뒤에 a~z 문자 하나를 적절하게 배치했을 때, 왼쪽과 오른쪽의 문자열의 인덱스가 다른 수의 최소값을 찾는 문제다. 문제의 조건에 최대 길이가 50이라고 주어졌지만, 이를 먼저 확인하지 않고 brute force라 dfs로 그냥 모든 경우의 수를 조합했다. 하지만, 메모리 초과가 떠서 위의 조건을 추가적으로 ..
-
BOJ) 파이프 옮기기 1알고리즘/백준 2020. 7. 8. 19:37
파이프 옮기기 1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 옮길 수 있는 모든 경우의 수를 찾는 문제기 때문에 브루트포스 문제다. 직접 다 돌리는데는 BFS나 DFS만큼 편한게 없다고(?) 생각해서 DFS로 풀었다. 문제를 풀면서 막혔던 부분은 첫째로, 문제 조건을 잘못 이해했다는 것이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수 이 문구에서 N,N을 보지 않고 N,y or x,N으로 이동한 파이프들을 구해줬었다... 두번째로는 실수라기 보다는 기둥의 시작점..
-
BOJ) 계란으로 계란치기알고리즘/백준 2020. 6. 30. 15:01
계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 이 문제가 너무 좋은 점은, 테스트 케이스가 충분히 주어졌기 때문이다. 그래서 그런지 정답 비율이 꽤나 높다. 문제가 제시한 조건을 살펴보면, 계란이 일렬로 나열되어있고 가장 왼쪽 계란부터 오른쪽 끝까지 순차적으로 들어서 계란판에 있는 다른 계란을 내려 치는 것이다. 두 계란의 내구도는 각각 상대 계란의 무게만큼 감소하게 된다. 한번 내리친 다음에, 손에 들고있던 계란을 내려놓고 다음 계란을 든다. 이때, 조건이 손에 쥔 계란..
-
BOJ) 두 동전알고리즘/백준 2020. 6. 29. 16:05
두 동전 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, �� www.acmicpc.net 풀이 블로그에 올리기 창피한 코드지만, 기록을 먼저 해두고 나중에 다시 풀고자 올린다. 브루트 포스를 제대로 사용했다기 보다, 시뮬레이션 문제로 인식하고 풀었기 때문에 메모리와 시간 효율성이 현저히 떨어진다. 그래도 로직을 설명하자면, 입력을 받을 때 먼저 두 동전의 위치를 저장했다. 그리고 해당 동전을 step에 따라 돌면서, 10을 초과하면 -1을 출력하고 10 이하에서 동전이 하나 남는 경우는 step을 출력했다. 동전을 이동시킬 때는, 범위..
-
BOJ) 로마 숫자 만들기알고리즘/백준 2020. 6. 26. 15:51
로마 숫자 만들기 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 풀이 Brute force 문제를 푼지 오래된 것 같아서 도전했다. n=20이기 때문에, 통과하려면 가지치기를 어떻게 해야하나 많은 고민을 해봤다. 질문 탭에도 게시글이 몇 개 없어서, 참고할 수도 없었다. 그래서, 처음 선택한 방법은 로마 숫자 1,5,10,50을 n만큼 2차원 배열을 만들어서 각 숫자가 0~n까지 반복하면 만들어지는 숫자를 저장했다. 이후에, 해당 숫자를 선택하면서 count를 i개 씩 줄여줬는데, 고작 해봐야 13 -> 14 정도까지만 구할 수 있었다. 어떻게 해야하나 고민하다가 Set에서 visit으로 바꿔주었다. 어차..