Door

https://school.programmers.co.kr/learn/courses/30/lessons/131129# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 풀다가 dp라는 건 파악했는데 dp를 어떻게 활용해야할지 몰라 힌트를 참고했습니다. 이 문제는 dp로 접근해야합니다. 처음에는 단순하게 "50을 넘어가면 무조건 불로 점수를 메긴다" 라고 생각을 했었습니다. 하지만 60처럼, 바로 다트하나로 점수를 얻을 수 있는 방법이 있어서 60의 결과값은 [1,0]이 되어야합니다. dp를 쓴다는 건 알았지만 그 다음 구체적은 구현이 까다로웠습니다. ..

알고리즘 공부 2023. 1. 2. 10:51

https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이 문제같은 경우에는 DFS를 활용해서 맨 오른쪽까지 가는 케이스를 구할 수도 있지만 저는 그렇게 구했더니 시간초과 이슈가 떠서 DP로 구현했습니다. (문제 알고리즘 분류가 DP이기도 하고....) dp테이블을 -1로 초기화하고 처음 돌맹이 위치는 1로 넣어줍니다. 그 다음, 1 다음(2부터 N번째 돌까지) 건너갈 수 있는지 여부를 확인..

알고리즘 공부 2022. 4. 13. 22:23

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제는 짧지만 공부할 것은 많은 문제. 이 문제는 DP로 풀어야하는데 처음 보는 입장에서는 많이 난감합니다. 직접 그려보면서 이야기를 하겠습니다. n, k = map(int, input().split()) c = [] dp = [0 for i in range(k + 1)] dp[0] = 1 for i in range(n): c.append(int(input())) for i in c: for j i..

알고리즘 공부 2022. 4. 12. 03:15

https://programmers.co.kr/learn/courses/30/lessons/42895# 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제에서는 DP라고 유형으로 나눴지만 DP라는 걸 모르면 적잖이 당황하기 쉽습니다. 사실 뭐 DP라는 걸 알아도 풀기가 어렵지만... 이 문제를 풀 때 점화식 아이디어가 떠오르질 않아서 인터넷 풀이를 참고해봤습니다. 이 문제의 핵심은 'N을 몇 번쓰는가'입니다. 저는 처음에 무턱대고 사칙연산을 구할려고 달려들었습니다. 예를들면 N=5일 때 2의 값은 뭐고 3의 값은 뭐고... 이렇게해보니 규칙이 보이는듯한데... 코드로 구현해보니 상당한 분노가 올라왔습니다. 무엇보다, 55 555 5555이런건 어떻게 구하지? 라는 것이 머릿속을 떠나지 ..

알고리즘 공부 2022. 3. 17. 11:27