본문 바로가기

구현

 (60)
[백준 / BOJ] 1938 통나무 옮기기 문제 출처 : https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4
[백준 / BOJ] 1747 소수 & 팰린드롬 문제 출처 : https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 숫자 N이 주어졌을때, N보다 크거나 같은수중 소수이면서 팰린드롬인 수중 가장 작은 수를 찾는문제다. 풀이 에라토스테네스의 채를 이용해 풀은문제다. 우선, 에라토스테네스의 채의 최대 범위를 지정해주기위해, N = 1,000,000일때, 소수이면서 팰린드롬인 수중 가장 작은수를 찾아보면, 1003001 이라는것을 알수있다. 따라서, 소수를 걸러주기..
[백준 / BOJ] 5430 AC 문제 출처 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 선영이는 AC라는 언어를 만들었다. AC정수배열에 연산을 하기위해 만든 언어이다. AC에는 R, D가 주어진다. R은 주어진 정수배열을 뒤집는 연산이고 D는 현재 정수배열의 가장앞 정수를 없애는 연산이다. 정수배열과 연산이 주어졌을때, 결과를 출력하는 문제였다. (지울수없는경우 error를 출력한다.) 풀이 구현 문제였다. 문자열 구현이 약한거같아서 일부러 찾아 푸는중인데, 역시나 구현이 쉽지는 않았다. 모든 연산에 대해 시뮬레이션을 수행..
[백준 / BOJ] 17135 캐슬 디펜스 문제 출처 : https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net N*M배열에 적이있고 N-1번째 줄에 궁수가있다. 매 턴마다 궁수는 자기의 사정거리안에서 가장 가까운적(가까운적이 여러명이라면, 가장 왼쪽적)을 찾아 공격하고 궁수의 공격이 끝난후 적은 한칸 아래로 내려온다. 궁수는 일제히사격하므로, 한 적에게 여러궁수가 공격할수있다. 이때, 가장많은 적을 없애는 경우의 수를 구하는 문제다. 풀이 시뮬레이션 문제였다. 최악의경우 (N=15, M=15)일때 반복..
[백준 / BOJ] 14500 테트로미노 문제 출처 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net N*M크기의 종이에 숫자들이 쓰여있다. 이 종이에 테트로미노하나를 놓았을때, 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 찾는 문제다. 소스코드 완전탐색으로 푼 문제다. 종이의 세로,가로가 각각 최대 500이며, 한번 탐색마다 (모든 폴리오미노를 본다했을때,) 40번이라고 하면, 총 탐색횟수는 250000*40 = 10000000가 되어서 시간초과를 피할수있..
[백준 / BOJ] 16985 Maaaaaaaaaze 문제 출처 : https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 미로를 나타내는 5*5크기의 판이 5개 주어진다. 판의 각 칸에는 이동할수없는칸 0, 이동할수있는칸 1이 있다. 5개의 판은 자유롭게 쌓을수있고 각 판마다 자유롭게 90도 회전또한 가능하다. 이때, 판을 적절히 쌓고 적절히 회전해서 5*5*5크기의 미로를 탈출하는 최소 이동횟수를 구하는 문제다. 입구는 5*5*5크기의 그리드의 각 모서리이며 출구는 입구와 면을 ..
[백준 / BOJ] 8980 택배 문제 출처 : https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net C만큼의 용량을 실을 수 있는 트럭이 있다. N개의 마을이 있으며, A마을에서 B마을로 용량 D의 택배를 보낼려고한다. M개의 보낼 택배의 시작장소, 도착장소 용량이 주어질때 트럭 한 대로 보낼 수 있는 최대한 많은 택배의 양을 구하는 문제다. 풀이 모든 경우를 봐줄경우, 구현에 따라 최악의 경우 2^M번 반복하므로 완전탐색으로는 시간안에 풀기 힘들다. 그리디를 ..
[백준 / 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]의 각 원소들이 모두 주어졌을때 원래 수열이 무엇인지 찾는 문제였다. 풀이 완전탐색(백 트래킹)으로 풀리는 문제였다. 각 칸에 숫자를 넣어보고 숫자를 넣을수있다면, 재귀를 호출..

티스토리툴바