백준
-
BOJ) 달팽이는 올라가고 싶다알고리즘/백준 2020. 7. 26. 17:27
달팽이는 올라가고 싶다 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 풀이 달팽이가 막대의 높이 V까지 올라가는 데, 걸리는 날을 구하는 문제다. A는 달팽이가 낮에 올라갈 수 있는 높이이고, B는 밤에 잠을 자는 동안 아래로 미끄러지는 높이다. 정상에 올라간 후에는 미끄러지지 않는다. 위의 조건으로 미루어 봤을 때, 막대까지 오르는 날 * A 만큼 위로 올라가고, (막대까지 오르는 날 -1) * B 만큼 아래로 미끄러진다. 잠을 자는 동안만 미끄러지고, 높이까지 올랐을 때는 미끄러지지 ..
-
BOJ) 합분해알고리즘/백준 2020. 7. 26. 15:48
합분해 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0~ N까지의 정수 K 개를 선택하여 N을 만드는 경우의 수를 구하는 문제다. 덧셈의 순서가 다르면 다른 경우로 체크한다. (1 + 2 와 2 + 1 은 다른 경우) 각각의 수는 여러번 이용 가능하며, 1,000,000,000으로 나눈 나머지를 출력해야한다. 우선 k개를 이용했을 때, 특정 숫자 n을 구할 수 있는 경우의 수를 담기 위해 2차원 배열의 dp를 선언했다. int[][] dp = new int[k][n]; 우선 k = 1 일 때, (0 ~ N까지 하나만 이용했을 때) 숫자를 만들 수 있는 경우를 1로 저장해줬다. (0이든, 1이든 ... N이든 자기 자신을 딱 하..
-
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 이론을 살펴보면 다음과 ..