본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/구현, 시뮬

 (65)
[백준 / BOJ] 1248 맞춰봐 문제 출처 : www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net 규현이는 -10 ~ 10 까지 총 21개의 숫자를 알고있으며, 이 수를 구간합으로 나타냈다. S[i][j] 는 i번째 숫자부터 j번째 숫자까지의 구간합이며 이 값이 양수면 +, 음수면 -, 0이면 0이 된다. S[i][j]의 각 원소들이 모두 주어졌을때 원래 수열이 무엇인지 찾는 문제였다. 풀이 완전탐색(백 트래킹)으로 풀리는 문제였다. 각 칸에 숫자를 넣어보고 숫자를 넣을수있다면, 재귀를 호출..
[백준 / BOJ] 10875 뱀 문제 출처 : www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 www.acmicpc.net 2차원 그리드에서 뱀이 움직인다. 뱀은 1초가 지날때마다, 바라보는 방향으로 한 칸씩 몸의 길이를 늘려가며 움직인다. 뱀은 자신의 몸과 닿거나 2차원 그리드 범위 밖으로 나가면 몸을 늘리며 숨을 거둔다. 뱀이 머리를 회전하는 시간과 방향이 주어질때, 뱀이 언제 숨을 거두는지 출력하는 문제다. 풀이 시뮬레이션 문제다. 문제의 조건을 읽어보면, 그리드의 길이가 가로 세로 각각 최대 4..
[백준 / BOJ] 1052 물병 문제 출처 : www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 지민이는 N개의 물병을 갖고있다. 각 물병에는 물을 무한대로 부을 수 있는데, 처음에 모든 물병에는 물이 1리터씩있다. 지민이는 N개의 물병을 적절히 합쳐 K개이하의 물병으로 만들려하는데, 물병을 합칠때 는 다음 규칙에 따라 합칠수있다. - 같은 물이 들어있는 물병만 합칠수있다. 이때, 물병을 더 이상 합칠수없다면, 1리터의 물이 들어있는 물병을 추가할수있다. K개 이하의 물병을 만들기위해 추가해야할 ..
[백준 / BOJ] 1035 조각 움직이기 문제 출처 : www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5*5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 5*5크기의 보드에 최대 5개의 조각이있다. 이 조각을 적절히 움직여서 모든 조각이 연결되도록 할려고한다. 조각은 상하좌우 한칸으로 이동시킬수 있다고할때, 모든 조각을 연결하는 최소한의 이동 횟수를 구하는 문제다. 풀이 처음에는(1년전??) BFS로 풀려했는데, BFS는 항상 최단경로를 보장하므로 하나의 조각을 기준으로 잡고 나머지 조각을 해당 조각으로 이동하는 횟수를 BFS로 구해주는로직을짰..
[백준 / BOJ] 10830 행렬 제곱 문제 출처 : www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 크기가 N*N인 행렬A가 주어졌을때, 해당 행렬을 B제곱한 결과를 구하는 문제다. 수가 매우 커질수있으니 A^B의 각 원소를 1000으로 나눈 나머지를 출력한다. 풀이 B가 최대 100,000,000,000까지 가서 일반적인 곱셈(A*A*A*A*A)으로는 시간초과가 난다. 분할정복을 이용해 풀어야하는데, A*A = A^2 A*A*A*A = A^2*A^2 = A^4 A*A*A*A*A*A*A*A = A^2*A^2..
[백준 / BOJ] 17144 미세먼지 안녕! 문제 출처 : www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구사과는 미세먼지를 제거하기위해 공기청정기를 설치하려고한다. 공기 청정기는 항상 1번 열에 설치되어있고, 크기는 두행을 차지한다. 공기청정기가 없는 칸에는 미세먼지가 있다. 미세먼지는 매초 마다 확산을 하는데, 확산되는 양은 다음과같다. 확산되는 양 : Ay,x / 5 y,x에 남는양 : Ay,x - (Ay,x/5 * 확산된 방향의 개수) 미세먼지가 확산을 한 이후에는 공기청정기가 작동하여 미세..
[백준 / BOJ] 2638 치즈 문제 출처 : www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net N*M크기의 모눈종이에 치즈가 있다. 모눈종이의 가장자리부터 공기가 들어오는데, 공기에 2면 접촉해있는 치즈는 1초후 녹기시작한다. 가장자리에는 치즈가없을때, 모든 치즈가 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제다. 풀이 BFS,DFS를 이용한 시뮬레이션 문제다. N,M이 최대 100,100이라서 총 칸수가 10000칸 까지 갈수있다. 한번 치즈를 녹일때마다 모든 칸을 다 봐준다..
[백준 / BOJ] 1918 후위 표기식 문제 출처 : www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 중위 표기법으로 입력된 수식을 후위표기법으로 바꾸는문제다. 후위표기법이란, 연산자가 피연산자 뒤에 위치하는 표기법이다. 후위 표기법의 예는 A+B = AB+ A+B*C = ABC*+ A*B+C = AB*C+ A*(B+C) = ABC+* 등이 있다. 풀이 구현문제다... 재귀로 풀었다. 처음에는 연산자를 피연산마 맨뒤에 쌓아놓기만 하면 되는거로 구현했다가 다 지우고 다시짰었다... 문제에서..

티스토리툴바