📍문제 링크 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 📍알고리즘 분류 - 수학 - 브루트포스 - 조합론 - 백트래킹 📍문제 풀이 - 알파벳 N개가 주어질 때, 모음 최소 1개, 자음 최소 2개를 사용하여 만들 수 있는 암호를 모두 출력하라 - 백트래킹을 이용하여 사전순이 아니면 가지치기 📍의사 코드 - 백트래킹으로 가능한 경우의 수를 배열에 저장하다가, 사전 순이 어긋나면 가지치기 실행 - 사용한 알파벳을 체크할 때 isUsed 배열에 자음인..

📍문제 링크 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 📍알고리즘 분류 - 자료 구조 - 스택 📍문제 풀이 - 중위 표기식을 후위 표기식으로 바꿔 출력하라 - 곱셈, 나눗셈은 덧셈, 뺄셈보다 우선순위가 높은 연산자이다 📍의사 코드 - 일반 배열과 스택 배열을 만든다 - 주어진 중위 표기식 문자열을 순회하며, 알파벳이면 : 일반 배열에 push ( 이면 : 스택에 push ) 이면 : 스택 배열의 마지막 원소가 (가 나올 때까지 일반 배..

📍문제 링크 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 📍알고리즘 분류 - 자료 구조 - 스택 📍문제 풀이 - 후위 표기식을 순회하며, 알파벳인 경우 와 연산자인 경우로 나눠서 생각한다. - 알파벳인 경우 stack에 저장한다. - 연산자인 경우, stack에서 2개의 수를 꺼내어 연산한뒤 다시 stack에 넣어 준다. 📍의사 코드 - 각 알파벳에 숫자를 바인딩하여 객체로 저장한다. 이를 통해 쉽게 숫자를 꺼내 쓸 수 있다. -..

📍문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 수의 길이가 주어질 때, 계단 수의 총 가짓수를 구하라 - 계단 수 : 12345, 10101 처럼 각 자릿수가 1씩 증감하는 수 - 이차원 배열 memo가 있고 - row : N - column : 맨 마지막 숫자 일때, N=2 까지 아래와 같은 2차원 배열을 만들 수 있다 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 N = 2 일때, - 마지막 숫자가 1인 경우는 memo..

📍문제 링크 https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 📍알고리즘 분류 - 자료 구조 - 정렬 - 해시를 사용한 집합과 맵 - 트리를 사용한 집합과 맵 📍문제 풀이 - 수열이 주어지는데, 출현 빈도 순으로 정렬한다 - 빈도가 같을 수록, 먼저 등장했을 수록, 앞에 위치한다. 📍의사 코드 - 빈 객체를 만들고, 숫자를 키로, 출현 빈도를 밸류로 하여 저장한다. - 동시에 첫 등장한 숫자는 unique한 배열에 push하여 순서를 저장한다. - 원본 수열을 정렬하는데, indexOf ..

📍문제 링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 가장 긴 증가하는 부분수열 : LIS (Longest Increasing Subsequence) 알고리즘으로 알려져 있다 - DP를 사용하여 해결한다 - 비슷한 문제가 많은 시리즈 문제 - LIS의 길이만 다루면 됨 - memo 배열을 data[n] 까..

📍문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - DP를 문제에 적용한다는 것은 메모이제이션이 활용된다는 것을 의미한다. - 이 문제에 메모이제이션을 적용하려면, n=1, 2 ... 커질 때, n=1 일 때의 값이 n=2 일 때 활용되도록 하면 된다. 5 3 최댓값 5 5 1 3 5 최댓값 10 (5+5) 5 1 10 3 5 4 최댓값 20 (5+5+10) 그런데, 이..

📍문제 링크 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📍알고리즘 분류 - 백트래킹 📍문제 풀이 - N개의 중복을 허용하는 수가 주어질 때, 중복을 허용하여 M개를 고르는 경우의 수를 모두 출력한다 (중복조합) - 비내림차순으로 출력한다 (오름차순 + 중복 허용) 📍코드 (JavaScript) const [in1, in2] = require("fs") .readFileSync("/dev/stdin") .toString() .trim()..