목록coding/알고리즘,자료구조 (98)

이모저모

동적 계획, knapsack 연습 - 제곱수의 합(백준)

문제: https://www.acmicpc.net/problem/1699 import sys n = int(sys.stdin.readline().rstrip()) # 초기화에 사용하는 큰 수 INF = int(1e6) # 동적으로 기입해갈 배열 준비 dy = [INF] * (n+1) dy[0] = 0 # 사용할 제곱수 종류들을 원소로 갖는 리스트 만들기 squares = [] root = 1 while root*root
coding/알고리즘,자료구조 2022. 2. 10. 13:01
BFS 연습 - 단어변환(프로그래머스)

문제: https://programmers.co.kr/learn/courses/30/lessons/43163 ✔︎ 더 알아봐야 할 점 - DFS에서의 백트래킹하듯이 BFS 에서도 적당히 가지치기 하면 좋겠다 싶다. - 그런데 이를 위해서는 모든 큐의 원소에서 기억하고 가지고 다녀야 할 정보? 메모리?에 부담이 늘어나는 것이 아닐까? - 더 좋은 방법으로 BFS에서 가지치는 방법은 어떤 것이 있을까? import collections def solution(begin, target, words): n = len(begin) que = collections.deque() que.append((begin, 0)) while que: word, cnt = que.popleft() # 타겟 발견하면 cnt 로 탐..
coding/알고리즘,자료구조 2022. 2. 10. 11:23
BFS 연습 - 1로 만들기(백준)

문제: https://www.acmicpc.net/problem/1463 import collections import sys n = int(sys.stdin.readline()) que = collections.deque([(n, 0)]) while True: num, cnt = que.popleft() # 만들고자 하는 수인 1이 되면 몇 번의 연산이 사용되었는지 출력하고 while 종료 if num == 1: print(cnt) break # 1 뺀 값, 연산 횟수 1추가해서 큐에 넣기 sub1 = (num-1, cnt+1) que.append(sub1) # 3으로 나눌 수 있다면 3으로 나눈 값, 연산 횟수 1 추가해서 큐에 넣기 if num%3 == 0: div3 = (num//3, cnt+1)..
coding/알고리즘,자료구조 2022. 2. 9. 18:44
동적 계획, knapsack 연습 - 설탕배달(백준)

문제: https://www.acmicpc.net/problem/2839 import sys n = int(sys.stdin.readline().rstrip()) # 초기화에 사용할 큰 수 INF = int(1e5) # 동적으로 기입할 배열 dy = [INF] * (n+1) dy[3] = 1 # 3kg 봉지만 고려하는 경우 for i in range(4, n+1): dy[i] = min(dy[i], dy[i-3] + 1) # 5kg 봉지도 고려하는 경우 if n >= 5: dy[5] = 1 for j in range(6, n+1): dy[j] = min(dy[j], dy[j-5] + 1) # 3과 5로 딱 떨어지게 담을 수 없는 경우 INF 로 남아있음 => -1 리턴 if dy[n] == INF: pr..
coding/알고리즘,자료구조 2022. 2. 9. 16:00
동적 계획법 연습 - 집도둑(leetcode)

문제: https://leetcode.com/problems/house-robber/ # 프로그래머스의 도둑질과 거의 똑같은 문제!(다만 프로그래머스는 원형으로 집이 배열되어 있다) 📝 배운 점 처음에 내가 풀었던 방법은 시간 효율이 안 좋았다. 그래서 discuss에 추천을 많이 받은 풀이를 찾아보았는데, 좋은 방법을 배우게 되었다. - 내 접근: 훔치기로 확정한 집이 1번인 경우와 2번인 경우 이렇게 두 경우로 나누어서 for 문을 두 번 돌렸다. - 다른 분의 접근: for문을 한 번만 돌려서 해결한다! 훔칠 수 있는 최대 액수를 기록해가는 배열 맨 앞쪽에 0으로 초기화하는 빈 인덱스를 3개 추가해주면 1번을 fixed하는 경우나 2번을 fixed하는 경우가 다 고려된 동적 배열을 기록해갈 수 있기..
coding/알고리즘,자료구조 2022. 2. 9. 13:51
동적 계획법 연습 - 계단오르기(leetcode)

문제: https://leetcode.com/problems/climbing-stairs/ 1칸 혹은 2칸씩 오를 수 있다면 n번째 칸에 이를 수 있는 방법은 몇 가지인지 구하기 bottom-up의 대표적인 예제! class Solution: def climbStairs(self, n: int) -> int: # bottom-up 으로 동적으로 기록해갈 배열 dy = [0] * (n+1) # 작고 확실한 출발점 dy[0] = 1 dy[1] = 1 # 전칸, 전전칸까지 올 수 있던 방법수를 합하여 해당 칸에 기록 for i in range(2, n+1): dy[i] = dy[i-1] + dy[i-2] return dy[n]
coding/알고리즘,자료구조 2022. 2. 9. 13:03
Prev 1 2 3 4 ··· 17 Next