본문 바로가기

알고리즘102

[LeetCode/Typescript] 779. K-th Symbol in Grammar https://leetcode.com/problems/k-th-symbol-in-grammar/ K-th Symbol in Grammar - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com n = 1일 경우 0부터 시작해, n이 1일 증가할 때 마다 0은 01로 1은 10으로 바뀝니다. n = 2일 경우 0이 01로 바뀌어 01, n = 3일 경우 0이 01로 바뀌고 1이 10으로 바뀌어 0110 이 됩니다. 패턴을 찾기 위해 5번째까지 써보면 n = 1, 0 n.. 2022. 11. 7.
[백준/C,C++] 7579번: 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 해당 문제에서 앱의 개수는 100개 이하이고, 확보해야하는 메모리는 10,000,000바이트 이하입니다. 100 x 10,000,000 는 10억으로 너무 크기 때문에, 비활성화 했을 경우의 최대 비용인 100을 사용해 DP 점화식을 짜야합니다. DP[i]를 i의 비용이 주어졌을때 확보할 수 있는 최대 메모리라고 가정해봅시다. 5 60 30 10 20 35 40 3 0 3 5 4 의 예제로 보겠습니.. 2021. 7. 5.
[백준/C,C++] 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 생각보다 어려운 문제였습니다. 1, 2, 5원을 1번 이상 사용해 만들 수 있는 1~10원의 경우의 수는 아래 표와 같습니다. 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 1 누적 1 1 1 1 1 1 1 1 1 1 1 2 0 0 1 1 2 2 3 3 4 4 5 누적 1 1 2 2 3 3 4 4 5 5 6 5 0 0 0 0 0 1 1 2 2 3 4 누적 1 .. 2021. 7. 5.
[백준/C,C++] 10942번: 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 1, 2, 1, 3, 1, 2, 1로 예를 들어보겠습니다. S = 1, E = 7일 경우 1과 1이 같고 그 중간 범위인 2, 1, 3, 1, 2가 팰린드롬이면 팰린드롬입니다. S = 2, E = 6일 경우 2와 2가 같고 그 중간 범위인 1, 3, 1이 팰린드롬이면 팰린드롬입니다. S = 3, E = 5일 경우 1과 1이 같고 그 중간 범위인 3이 팰린드롬이면 팰린드롬입니다. 수가 하나일 경우 무조건 팰린드롬이므로 S = 1, .. 2021. 7. 5.

티스토리툴바