BOJ
-
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:47
로봇 청소기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 푸는데 많은 시간을 소요했다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방..
-
BOJ) 사탕 게임알고리즘/백준 2020. 7. 24. 22:38
사탕 게임 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고 www.acmicpc.net 풀이 NxN 크기의 보드에 사탕이 가득 채워져 있다. 사탕의 색이 다른 인접한 두 칸을 골라서 서로 교환한다. 이 때, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 or 열)을 고른 다음 그 사탕을 다 먹는다. 사탕을 먹을 수 있는 최대 갯수를 구하는 문제다. 알고리즘을 활용한다기 보다 구현에 가까운 문제라고 느꼈고, 간단하게 풀 수 있었다. 맵을 돌면서, 상하좌우에 있는 사탕과 바꾸고, 상/하로 바꿨을 경우에는 해당 행을 검색..
-
BOJ) 벽 부수고 이동하기알고리즘/백준 2020. 7. 23. 15:51
벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 풀이 BFS 문제로, (1,1)에서 시작해서 (n,m)에 최소 경로로 도달하기 위해 몇 개의 칸을 밟는지 구하는 문제다. 처음에는 단순하게 visit을 좌표만 체크하면서 (2차원 배열) 답을 구해줬다. 50퍼센트 쯤 넘어갈 때 틀렸다고 뜨는 것을 보고, 벽을 허물고 이동한 경우와 벽을 허물지 않고 이동한 경우가 물린다는 것을 알아챘다. 그래서 visit 변수를 3차원 배열로 생성해주었는데, 벽을 한 번 허물었을 경..
-
BOJ) LCS알고리즘/백준 2020. 7. 23. 15:44
LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 이 문제를 통해 LCS 알고리즘을 처음 학습했다. LCS(Longest Common Subsequence)는 최장 공통 부분 수열을 의미하며, 두 수열이 주어졌을 때, 부분 수열이 되는 수열 중 가장 긴 것을 찾는 것이다. 이 문제에서는 알파벳으로 이루어진 두 문장이 주어졌으므로, 두 문자열에서 알파벳의 부분 수열이 공통으로 가장 긴 길이를 찾아야 한다. 문제의 예시를 통해 LCS 이론을 살펴보면 다음과 ..
-
BOJ) 기타줄알고리즘/백준 2020. 7. 22. 15:16
기타줄 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 첫째 줄에 갈아야하는 기타 줄의 수 n과 기타줄 브랜드 수 m이 공백을 두고 주어진다. 다음 m줄에 대해서 각 브랜드의 기타줄 패키지 가격과 1개의 가격이 차례대로 주어진다. 이 때, 기타줄을 갈 수 있는 최소 가격을 구하는 문제다. dfs로 dp로 할까 생각하다가 dfs로 먼저 짜봤다. 하지만, n이 최대 100이어서 빠르게 손절했다. (가지치기를 한다해도 비효율적) 다음은 dp를 생각했다. 줄 하나를 갈 때, 2개를 갈 때, ... n개를 갈..
-
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로 그냥 모든 경우의 수를 조합했다. 하지만, 메모리 초과가 떠서 위의 조건을 추가적으로 ..