알고리즘/백준
-
BOJ) 기타줄알고리즘/백준 2020. 7. 22. 15:16
기타줄 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 첫째 줄에 갈아야하는 기타 줄의 수 n과 기타줄 브랜드 수 m이 공백을 두고 주어진다. 다음 m줄에 대해서 각 브랜드의 기타줄 패키지 가격과 1개의 가격이 차례대로 주어진다. 이 때, 기타줄을 갈 수 있는 최소 가격을 구하는 문제다. dfs로 dp로 할까 생각하다가 dfs로 먼저 짜봤다. 하지만, n이 최대 100이어서 빠르게 손절했다. (가지치기를 한다해도 비효율적) 다음은 dp를 생각했다. 줄 하나를 갈 때, 2개를 갈 때, ... n개를 갈..
-
BOJ) 문자열알고리즘/백준 2020. 7. 21. 15:29
문자열 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 풀이 문자열 두개가 주어질 때, 오른쪽 문자열의 길이는 항상 왼쪽보다 크다. 왼쪽 문자열의 맨 앞이나 맨 뒤에 a~z 문자 하나를 적절하게 배치했을 때, 왼쪽과 오른쪽의 문자열의 인덱스가 다른 수의 최소값을 찾는 문제다. 문제의 조건에 최대 길이가 50이라고 주어졌지만, 이를 먼저 확인하지 않고 brute force라 dfs로 그냥 모든 경우의 수를 조합했다. 하지만, 메모리 초과가 떠서 위의 조건을 추가적으로 ..
-
BOJ) 신기한 소수알고리즘/백준 2020. 7. 21. 15:15
신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수� www.acmicpc.net 풀이 처음에는 모든 숫자에 대해 DFS를 진행하면서 답을 구하려고 시도했다. 하지만 문제의 최대 조건인 n=8인 경우에 엄청난 시간이 소요되면서, 가지치기가 더 필요한 것을 느꼈다. 문제의 조건을 자세히 봤다. n=4 인 경우에 나오는 수를 살펴보면, 첫번째 자리에는 {2,3,5,7} 만 오고 나머지 자리에는 {1,3,7,9}만 나와있음을 확인했다. 이 말은, n=3인 경우, n=2인 경우에도 앞의 자리가 위의 네가지 숫자 말고는 올 수..
-
BOJ) 잃어버린 괄호알고리즘/백준 2020. 7. 21. 15:07
잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 양수와 +-로만 이루어졌고 최대 길이가 50인 수식이 있다. 이 수식에 적절하게 괄호를 씌워서 최소값을 구하는 문제다. 그렇다면, 가장 중요한 것은 -가 최대가 되게 해야한다. -로 먼저 split을 해주고, - 뒤에 있는 모든 +를 더해서 -를 씌워주면 최소값이 나올 것이다. 이 때, -를 기준으로 split을 해줬기 때문에, 배열의 첫번째 index는 -가 없다는 점을 유의해야한다. 그래서 idx ==0인 경우에는 -를 씌워주지 않고..
-
BOJ) 분해합알고리즘/백준 2020. 7. 21. 15:03
분해합 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 풀이 어떤 자연수 M과 N이 있을 때, M과 M의 각 자릿수 합이 N이되는 수의 최소값을 구하는 문제다. 범위를 어떻게 줄일지 생각이 나지 않아서, 일단은 DFS로 모든 경우의 수를 만들어서 검증했다. 자릿수 만큼 숫자를 만들고, 문제의 조건에 맞다면 최소값을 최신화해줬다. 메모리와 시간이 너무 보기 싫었다. 범위를 어떻게하면 줄일 수 있을지 생각하다가, 주어진 숫자의 각 자릿수가 9로만 이루어진 경우가 해당 자릿수에서 나올 수 ..
-
BOJ) 단어 수학알고리즘/백준 2020. 7. 18. 22:23
단어 수학 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 N개의 단어를 각각 숫자로 바꿔서 모두 더한 값 중 최대값이 되는 경우를 출력한다. 이 때, 단어에 포함되는 알파벳의 갯수는 10개 이하이며, 0~9 사이의 값을 적절하게 배치했을 때의 최대값을 구하는 문제다. 처음에는 각 알파벳이 가질 수 있는 값의 모든 경우의 수를 DFS를 통해 저장했다. 입력 받을 때, HashMap에 각 char의 index를 저장하는 식으로 문제를 풀었는데, 메모리와 시간이 매우 비효율적이었다. 생각 덜하고 빠르게..
-
BOJ) 체스판 다시 칠하기알고리즘/백준 2020. 7. 18. 22:13
체스판 다시 칠하기 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 흰색과 검은색이 랜덤하게 칠해진 n x m 크기의 보드가 주어지는데, 이 보드를 8x8로 잘라서 체스판으로 이용하는 경우 최소 책칠작업의 횟수를 구하는 문제다. 체스판은 흰색으로 시작하는 경우, 검은색으로 시작하는 경우 두 경우밖에 없기 때문에, 두 보드를 먼저 final로 선언했다. for문을 돌면서 8x8로 보드판을 자르면서 검사했다. 보드의 시작점은 0~n-8 , 0 ~m-8 이 된다. (n = 보드의 y축 최대 값, m =..