본문 바로가기

구현

 (60)
[백준 / 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] 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] 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+* 등이 있다. 풀이 구현문제다... 재귀로 풀었다. 처음에는 연산자를 피연산마 맨뒤에 쌓아놓기만 하면 되는거로 구현했다가 다 지우고 다시짰었다... 문제에서..
[백준 / BOJ] 9935 문자열 폭발 문제 출처 : www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열이 주어지고, 폭발 문자열이 주어진다. 문자열에서 폭발문자열이 있는경우 해당 폭발문자열은 사라지게된다. 예를들어, CaaaabbbbC ab 인경우 가운데 부터 순서대로 사라져서 마지막에 CC만 남게된다. 풀이 문자열의 최대길이가 백만이므로 일반적인 완전탐색으로는 시간초과가 난다. 스택의 특징을 사용해서 구현했다. 구현은 간단한데 1. 문자열을 하나하나 deq에 넣으면서 탐색한다..
[백준 / BOJ] 1941 소문난 칠공주 문제 출처 : www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 5*5그리드에 학생들의 파가 주어진다. (이다솜파 : S, 임도연파 : Y) 이다솜은 자신의 파를 늘리기위해 소문난 칠공주를 결성하기로했다. 칠공주가 되기위해선 3가지 조건이 필요한데, 1. 칠공주에 속하는 학생들은 서로 인접해있어야한다. 2. 7명의 학생으로 구성되어야한다. 3. 이다솜파보다 임도연파가 더 많아야한다. 이때, 소문난 칠공주를 결성하는 모든 경우의수를 구하는 문제다. 풀이 푸는데 2일..
[백준 / BOJ] 1644 소수의 연속합 문제 출처 : www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 자연수 N이 주어진다. 연속된 소수들을 더해서 자연수 N을 더하는 경우의수를 구하는 문제다. 풀이 '연속된 소수들을 이용해서 N을 만들어야 한다'는 조건이 있기때문에, 투포인터를 이용해 풀수있다. 소수만을 가지고 N을 만들어야 한다. 매번 해당 숫자가 소수인지 판단하면 너무 오래걸리기 때문에, 에라스토테네스의 체를 이용해 미리 소수들을 구해서 벡터에 넣어줬다. 연속된 소수들의 시작idx와 끝idx를 나타내는 left, right를 선언해줬다. 연속된 소수들의 합 S = (vec[left] + vec[left + 1]..

티스토리툴바