Algorithm/문제 풀이62 [알고리즘] 문자열 폭발 (백준 9935번) 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 www.acmicpc.net 폭발 문자열, 즉 특정 패턴을 찾아서 매칭되면 그 패턴에 해당하는 문자열을 삭제하고, 새로 만들어진 문자열에서 또 패턴을 찾아 삭제하라는 문제이다. 당연하겠지만 String.replaceAll로 반복문을 돌리는 것은 메모리 초과, 혹은 시간 초과로 불가능하다. O(N) 만큼의 시간복잡도로 패턴을 찾아 파괴하는 것이 포인트이다. 1. failureFunction 만들기 KMP를 응용하여 failureFunction을 만들어서 비교 문자가 같지 않은 경우 pattern 인.. 2020. 8. 26. [알고리즘] 팰린드롬? (백준 10942번) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 팰린드롬을 판별하는 동적 프로그래밍 + 문자열 처리 문제이다. 우선 팰린드롬이란 문자열 중앙을 기준으로 좌측, 우측이 마치 데칼코마니처럼 일치하는 경우를 말한다. EX) 121, 5, 2345432 문제에선 S 인덱스부터 E 인덱스까지의 문자열이 팰린드롬인지를 판별하라고 했는데 동적 프로그래밍을 사용하지 않고 일일이 계산한다면 O(N ^ 3) 혹은 O (N * M) 의 시간이 걸리는데 최악의 경우 무려 80억번의 계산이 필요하다. 하지만 동적 프로그래밍을 사용해서 구하게 된다면 O (N ^ 2) 의 시.. 2020. 8. 25. [알고리즘] 잃어버린 괄호 (백준 1541번) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net +, - 연산자로만 이루어진 수식에서 적절하게 괄호를 쳐서 최소값을 찾아내야하는 문제다. 만약 1+2+3-4+5+6-7 가 있다면 괄호 없이 계산할 시 합은 6이다. 하지만 만약 1+2+3-(4+5+6)-7 로 괄호를 쳐서 계산하게 되면 -16이 답이된다. 즉 -부호가 붙은 뒤의 수들을 괄호로 묶으면 최소값이 된다. (이중괄호는 고려하지 않는다) "-" 연산자를 기준으로 String을 split한다. split된 token들을 반복문을 돌려서 token마다.. 2020. 8. 24. [알고리즘] 체스판 하얀 칸 (백준 1100번) 1100번: 하얀 칸 체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램�� www.acmicpc.net 사실 이 문제는 굉장히 쉬운지라 어떻게 풀어도 상관은 없지만 다른 사람들 코드를 보니 의외로 이 사실을 모르는 것 같아서 한 번 올려본다. Solution 만약 이런 체스판이 있다고 쳤을 때 (가로 index + 세로 index), 즉 i + j 가 흰 칸은 짝수이고 검은 칸은 홀 수 이다. 그래서 굳이 i 가 짝수일 때, 홀수 일 때 경우, j가 짝수 혹은 홀수 일 때 경우를 분기할 필요 없이 (i+j)가 짝수, 홀수인 경우로만 분기하면 된다. impor.. 2020. 8. 24. 이전 1 ··· 12 13 14 15 16 다음
