본문 바로가기

분류 전체보기

 (341)
[백준 / BOJ] 9935 문자열 폭발 문제 출처 : www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열이 주어지고, 폭발 문자열이 주어진다. 문자열에서 폭발문자열이 있는경우 해당 폭발문자열은 사라지게된다. 예를들어, CaaaabbbbC ab 인경우 가운데 부터 순서대로 사라져서 마지막에 CC만 남게된다. 풀이 문자열의 최대길이가 백만이므로 일반적인 완전탐색으로는 시간초과가 난다. 스택의 특징을 사용해서 구현했다. 구현은 간단한데 1. 문자열을 하나하나 deq에 넣으면서 탐색한다..
[백준 / BOJ] 2158 산악자전거 문제 출처 : www.acmicpc.net/problem/2158 2158번: 산악자전거 첫째 줄에 세 정수 V, R, C가 주어진다. 다음 R개의 줄에는 C개의 정수로 행렬이 주어진다. 행렬의 각 수는 -25이상 25이하의 정수이다. www.acmicpc.net R*C 행렬이 주어지고, 각 칸마다 높이가 주어진다. 현재 높이A에서 높이 B로 이동할때, 속력이 (2^(A-B))배로 변한다. (R,C) 위치에 도달하는 최소시간을 구하는 문제다. 풀이 다익스트라로 풀리는문제다. 목적지에 도달할때, 다른 경로로 뺑돌아서 (속력을 높인후) 도착하는 경우가 더 빠를수 있기때문에, 다익스트라로 풀어야한다. 구현은 일반적인 다익스트라에 속력을 계산해주는걸 추가하면된다. 주의할점이 현재 (y,x)에 도착한 도달시간이 ..
[백준 / BOJ] 2941 크로아티아 알파벳 문제 출처 : www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 문자열을 입력받았을때, 해당 문자열에서 크로아티아 알파벳이 몇개있는지 찾는 문제이다. 풀이 완전탐색으로 풀리는 문제다. 문자열의 최대 길이가 100이므로 모든경우를 다 보면서 크로아티아 알파벳을 찾아줘도 되지만, 해당 방법은 비효율적이다. 문제에서 주어진 크로아티아 알파벳들을 보면 규칙을 찾을수있는데, 바로 크로아티아 알파벳은 'j', '=' , '-' 셋중 ..
[백준 / BOJ] 6503 망가진 키보드 문제 출처 : www.acmicpc.net/problem/6503 6503번: 망가진 키보드 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 두 줄로 이루어져 있다. 테스트 케이스의 첫째 줄에는 m이 주어진다. (1 ≤ m ≤ 128) 둘째 줄에는 상근이가 입력하려고 하는 www.acmicpc.net 상근이의 키보드가 망가져서, 키보드에서 작동가능한 키가 m개 밖에없다. 상근이가 입력하려는 문자가 주어졌을때, m개의 키를 눌러서 입력할수있는 최대 부분 문자열의 길이를 구하는 문제다. 풀이 예제 출력을보면 This can't be solved by brute force 라고 친절히 적혀있으므로 완전탐색으로는 풀리지않고, (문자열의 갯수가 완탐으로는 못풀만큼 입력되는듯) 다른 방법으로 ..
[백준 / BOJ] 9202 Boggle 문제 출처 : www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 각칸에 알파벳 대문자가 적혀있는 보드가 주어졌을때 단어를 찾는 게임을 하려고한다. w개의 찾을 단어가 주어지고, 각 칸마다 알파벳 대문자가 적혀있는 b개의 4*4 보드가 주어졌을때, 가장 많이 얻는 점수 , 가장 긴 문자열, 가장 많이 찾을수있는 단어의 수 를 구하는 문제다. (이동은 현재위치에서 8방향(가로, 세로, 대각선)으로 갈수있다.) 풀이 일반적인 완탐만 사용할경우, 최..
[백준 / BOJ] 14725 개미굴 문제 출처 : www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 로봇 개미가 개미굴 입구에서 각 층을따라 내려오며 먹이를 탐색한다. 이때 로봇 개미 발견한 먹이를 순서대로 알고있을때, 개미굴의 구조를 출력하는 문제다. 풀이 처음에는 기본적인 그래프 탐색으로 풀수있겠다 생각했는데, 시간초과가 난다. Trie를 사용안하면, 자신과 연결된 개미굴이 자신이 찾고있는 개미굴인지 매 탐색마다 확인해야하므로 15번 반복하고, 문자의 갯수는 총 15000개가 ..
[백준 / BOJ] 12785 토쟁이의 등굣길 문제 출처 : www.acmicpc.net/problem/12785 12785번: 토쟁이의 등굣길 인하대학교에 다니는 토쟁이는 y축과 평행한 w개의 도로, x축과 평행한 h개의 도로가 있는 도시에 살고 있다. 토쟁이의 집은 이 도시의 맨 왼쪽 아래에 위치하며 좌표로는 (1, 1)로 표시할 수 있다. www.acmicpc.net w*h그리드가 주어지고, 토스트집의 위치 y,x가 주어진다. 인하대학교에 다니는 토쟁이가 토스트집(x,y)을 지나서 (w,h)에 위치한 학교에 갈려할때, 최소 이동횟수를 구하는 문제다. 풀이 모든 경우를 다 탐색할경우 한 골목에서 선택할수있는 선택지가 2개, 골목길의 수가 40000개 이므로, 2^40000번 반복해서 시간초과가 난다. dp를 써서 풀었다. dp[y][x] = 최소..
[백준 / BOJ] 1941 소문난 칠공주 문제 출처 : www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 5*5그리드에 학생들의 파가 주어진다. (이다솜파 : S, 임도연파 : Y) 이다솜은 자신의 파를 늘리기위해 소문난 칠공주를 결성하기로했다. 칠공주가 되기위해선 3가지 조건이 필요한데, 1. 칠공주에 속하는 학생들은 서로 인접해있어야한다. 2. 7명의 학생으로 구성되어야한다. 3. 이다솜파보다 임도연파가 더 많아야한다. 이때, 소문난 칠공주를 결성하는 모든 경우의수를 구하는 문제다. 풀이 푸는데 2일..

티스토리툴바