본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 11660 구간 합 구하기 5 문제 출처 : www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net N과 M이 주어지고, N*N그리드에 숫자들이 주어진다. M개의 범위가 주어졌을때, 해당 범위에있는 숫자들의 합을 구하는문제다. 예를들어, 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 그리드에서, 1 1 1 4 는 10이다. 풀이 (구간합 구하기 3을 풀다 도망쳤다...) 일반적인 완전탐색으로는 풀지못한다. N의 범위가 1024이고, M이 10..
[백준 / 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] = 최소..

티스토리툴바