알고리즘
-
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 =..
-
BOJ) 나이트의 이동알고리즘/백준 2020. 7. 18. 22:06
나이트의 이동 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 www.acmicpc.net 풀이 테스트 케이스의 수가 주어지고, 각 테스트 케이스마다 체스판의 크기, 시작점, 목표 지점이 차례대로 주어진다. 나이트가 시작점을 출발해서 목표 지점에 도달하는 경우의 수를 출력하는 문제다. 나이트가 이동할 수 있는 경우의 수는 8가지다.위의 8가지 경우의 x와 y가 움직이는 위치를 각각 dx와 dy로 선언해줬다.그리고 BFS를 통해서 이미 도착했던 지점인지 visit체크와 함께 움직일 때마다 step을 저장해주면서, 도착지점에 도달하면 ste..
-
BOJ) 대회 or 인턴알고리즘/백준 2020. 7. 18. 22:01
대회 or 인턴 2875번: 대회 or 인턴 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 www.acmicpc.net 풀이 1. 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙 2. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 위의 두 조건에 따라, 여학생과 남학생, 인턴에 참여하는 학생의 수가 순서대로 주어질 때, 인턴쉽에 참가할 수 있는 최대 팀의 수를 구하는 문제다. 여학생 2명과 남학생 한명을 짝지어야 하기 때문에, 반복문을 통해 인턴십에 참여..
-
BOJ) 동전 1알고리즘/백준 2020. 7. 18. 21:56
동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 n 가지 종류의 동전을 각각 여러개 이용해서 k원이 되게 하는 수를 구하는 문제다. 처음에는 dfs로 접근했다가, 동전은 몇개라도 사용할 수 있다는 조건을 보고 DP로 선회했다. 각각 동전에 대해서 K원 이하일 때, 쓰일 수 있는 모든 돈에 경우의 수를 추가시켜주었다. for문을 돌면서 각 동전 coin에 대해coin의 가치부터 K원 까지 들어갈 수 있는 경우만 추가시켜주면 해결되는 문제였다. 코드 import java.io.BufferedReade..
-
BOJ) 암호 만들기알고리즘/백준 2020. 7. 18. 21:47
암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 C 개의 문자 중 L개를 선택해서 만들 수 있는 암호를 출력하는 문제다. 이 때, 암호는 모음(a,e,i,o,u)이 최소 하나 이상 자음이 두개 이상인 조합만 가능하다. 또한, 모든 암호의 경우를 사전순서대로 출력해야한다. 위의 두 조건을 충족하기 위해 C개 중 L개를 선택하는 것은 DFS를, 사전 순서대로 하기 위해 정렬을 선택했다. DFS이후에 정렬을 하기에는 너무 많은 시간과 메모리를 낭비할 것 같아서 입력 받자마자 정렬을 해주었다. DFS에서..