2022-09 알고리즘 정리

09-03 (토)

백준 골5

2293 동전 1

https://www.acmicpc.net/problem/2293

DP를 통해 풀어야 하는 문제. dp 배열로 2차월 배열을 이용하면 메모리 4mb를 초과해서 (dp배열 & coin배열) dp 배열을 1차원 배열로 구현해야 한다.

점화식 : dp[i][j]는 coin 0~i까지를 활용해 j를 만들 수 있는 경우의 수를 나타낸다.

dp[i][j] = dp[i-1][j] + dp[i]j-coin[i]]

이 점화식은 2차원 배열을 기준으로 작성된 점화식이고
이것을 1차원 배열을 통해 구현한다면

dp[j] = dp[j]+dp[j-coin[i]]
이다.

09-05 (월)

프로그래머스 lv2

이진 변환

https://school.programmers.co.kr/learn/courses/30/lessons/70129

python string method 중에서 replace, bin, slicing을 이용하면 쉽게 풀 수 있는 문제.
문자열도 리스트처럼 슬라이싱이 가능하다는 것을 알게됐다.

09-16 (금)

프로그래머스 lv2

방금그곡

https://school.programmers.co.kr/learn/courses/30/lessons/17683/solution_groups?language=python3

# 처리를 어떻게 하는지가 중요했던 문제.
처음에는 모든 음을 분리해서 리스트로 만들어 문제를 풀었다. 이때 조건문을 이용해 음들을 분리했다 ( #이 아니면 문자 추가, #이면 마지막 문자에 #추가). 비효율적인 방식으로 시작해서 오래 걸렸다

정답 코드에서는 # 음들을 애초에 소문자로 치환해줘서 문자열 find()로 쉽게 풀었었다.