본문 바로가기

전체 글

[Algorithm] min-cost-climbing-stairs 문제 https://leetcode.com/problems/min-cost-climbing-stairs/ Min Cost Climbing Stairs - 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 처음에 풀었을 때 - 매개변수로 주어지는 cost 배열을 이용 안 하고 dp 테이블을 따로 만듬 - 시간복잡도 올라감 class Solution(object): def minCostClimbingStairs(self, cost): cost.append(0) n = len.. 더보기
[Algorithm] 편집 거리 출처 - 이코테 p.382 문제 편집 거리 알고리즘.. 잘 이해 안 됐는데 거의 80% 정도까지 이해하도록 도와준 영상이 있다. 이분 영상 너무 좋다. 다른 영상도 계속 보면 도움될 것 같음 https://www.youtube.com/watch?v=XJ6e4BQYJ24&t=661s 여기서 감명깊었던게 "Adding a character to A is equivalent to deleting a character from B" 이다. def edit_dist(str1, str2): n = len(str1) m = len(str2) # 2차원 dp 테이블 초기화 (맨 첫번째 행열은 각각 빈 문자열) dp = [[0] * (m + 1) for _ in range(n + 1)] # dp 테이블 초기 설정 for.. 더보기
[Algorithm] 금광 문제 이코테 p.375 '금광' 문제 문제 2차원 테이블에서 채굴자가 얻을 수 있는 금의 최대 크기를 구하는 문제이다. 내 실수 2차원 테이블의 맨 왼쪽부터 채굴자가 얻을 금을 하나씩 선택해서 이어가는 느낌으로 풀었다. 이건 행마다 max 값을 고르는 선택의 느낌으로 풀면 안 된다. (이러면 결국 그리디가 되어버린다) 어떤 선택이 최적해가 될 지 모르기 때문에 결국에는 모든 맵에 대해서 최적해를 구해주어야 한다. 점화식은 나름 비슷하게 세웠는데, 애초에 내 풀이는 가정이 잘못 됐다. ('선택' 의 느낌으로 갔기 때문) 이 문제를 해결하는데 DP 를 선택해야하는 이유 최적 부분 구조인가 - YES 중복되는가 - YES for tc in range(int(input())): n, m = map(int, input.. 더보기
[Algorithm] 1로 만들기 이코테 p.217 피보나치 수열같은 느낌의 대표적인 dp 기본 문제다. 나는 bfs 가 먼저 떠올라서 bfs 로 풀었다. BFS 풀이 from collections import deque def bfs(n): q = deque() q.append((n, 0)) while q: x, cnt = q.popleft() if x == 1: print(cnt) exit() if x % 5 == 0 and x / 5 > 0 and not visit[x // 5]: newX = x / 5 visit[newX] = True q.append((newX, cnt + 1)) if x % 3 == 0 and x / 3 > 0 and not visit[x // 3]: newX = x / 3 visit[newX] = True q.. 더보기
[드림코딩 앨리 강좌] 노드로 배우는 백엔드 A-Z 본 글은 드림코딩 앨리님의 노드로 배우는 백엔드 A-Z 를 수강한 후, MDN Web Docs 를 바탕으로 재정리해본 글이다. 강의 기간: 2021.05~2021.05 회사를 이직하면서 기술스택이 Spring -> Node 로 바뀌었다. 드림코딩 앨리님의 유튜브를 평소에 즐겨봐서 이 분 강의를 믿고 선택하게 되었다. 결론적으로 매우 잘한 선택이었다. 전반적으로 노드를 입문하며 흐름을 파악하기에 좋은 강의였다. Chap 8. Web 기초 지식 HTTP HTTP v1,v2,v3 HTTP v1 HTTP,HTTPS 둘다 사용 가능 text-based 로 주고받음 uncompressed headers (size 도 큼) one file at a time inefficient HTTP v2 HTTPS 만 사용 가능.. 더보기
[Algorithm] 떡볶이 떡 만들기 이코테 p.201 문제 고칠점 list 안에서 최대값 찾을 때 max(array) 로 찾자. 자꾸 sorting 하고 원소로 끄집어내지 말고 import sys def cutDduck(cuttingHeight): sum = 0 for i in data: if i > cuttingHeight: i -= cuttingHeight sum += i return sum def binary_search(start, end, target): global answer if start >= end: return mid = (start + end) // 2 sumDduck = cutDduck(mid) if sumDduck == target: answer = mid return elif sumDduck > target: b.. 더보기
[Algorithm] 10026. 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 비교적 쉬운 문제였다. 처음에 bfs 를 적록색약인 사람용 / 적록색약 아닌 사람용 => 이렇게 두 개 만들어야 하나 싶었는데, 그냥 적록색약인 사람용 그림을 새로운 리스트에 새로 선언해줘서 그거만 기존 bfs 함수에 돌렸다. import sys from collections import deque input = sys.stdin.readline dx = [0, 0, 1, -1] dy = .. 더보기
[Algorithm] 2589. 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 내 오답 포인트 - 굳이 combination 을 썼다. 그래서 시간초과남. import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(a, b): global result q = deque() visit[a][b] = True q.append((a, b, 0)) while q: x, y, cnt = q... 더보기

티스토리툴바