🍒 Chae-ri Dev 🍒

[Algorithm/Python] 다이나믹 프로그래밍 알고리즘 정리

DP(Dynamic Programming)는 연산 속도와 메모리 공간을 최대한 효율적으로 활용할 수 있게 해주는 알고리즘이다. 대표적인 예시 : 피보나치 수열 피보나치 수열을 점화식으로 표현하면 다음과 같다.프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현(+ dict 자료형)# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현def fibo(x): if x == 1 or ×= = 2: return 1 return fibo(x - 1) + fibo(x - 2)print(fibo(4)) 하지만 위 코드는 n이 커지면 수행 시간이 기하급수적으로 늘어나는 문제가 발생한다.메모이제이션 기법을 사용해서 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메..

https://www.acmicpc.net/problem/7576  # 코드import sysfrom collections import dequeM, N = map(int, sys.stdin.readline().split())graph = []for _ in range(N): graph.append(list(map(int, input().split())))q = deque()num = 0for i in range(N): for j in range(M): if graph[i][j] == 1: q.append([i, j])def bfs(): while q: dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] x, y = q.popleft() ..

# 질문Cafes and coffee houses today are often more than just places that serve coffee.요즘 카페는 단지 커피만 마시는 곳이 아닙니다.They serve as mobile offices or even as meeting places.이동 사무실이나 미팅 장소로서의 역할을 하고 있는데요.How has the role of cafes changed over the years?수년간 이 카페의 역할이 어떻게 바뀌고 있나요? grab some coffee : 커피를 마시다the reason why : ~하는 이유change quite a bit : 많이 바뀌다 I also do the same. : 나도 그렇게 한다.They go for the sa..

# 질문What new electronic gadgets or equipment are people, who like music, interested in these days?What are they talking about?요즘, 음악을 좋아하는 사람들은 어떤 전자기기에 관심이 있나요?What new products excite them and why?그들은 어떤 새로운 기기에 관심을 갖나요?그리고 그 이유는 무엇인가요? these days를 쓸 때 앞에 in을 붙이지 말기! actually를 사용할 때 맨 앞에 바로 사용하지 말고 Well actually 로 시작해보자.actually 뿐만 아니라 when it comes to(~관한)도 처음이 아닌 중간에 사용하는 것이 더 좋다.When it com..

starting to have : 시작되고 있다. disaster / tragedy / terribleCan you imagine?상상할 수 있나요? How can I live with this much fine dust?어떻게 이렇게 많은 미세먼지 속에서 살 수 있을까요?How am I supposed to live with this much fine dust?이렇게 많은 미세먼지 속에서 어떻게 살아야 하나?Basically, we didn't have to worry about air condition thing.=> We never really had to worry about air quality.=> 우리는 공기 질에 대해 걱정할 필요가 없었어요.=> We went outside pretty m..

BFS(Breadth First Search)BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 탐색하는 알고리즘이다. BFS를 구현할 때는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. # 동작 방식1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. deque 라이브러리 사용 => 시간 복잡도 O(N)일반적으로 bfs가 더 빠르다. from collections import deque# BFS 메서드 정의def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 dequ..

이번 포스틑는 롤플레이 12번 문제에 관한 것이다. # 상황I'm sorry but there is a problem I need you to solve.미안하지만 문제가 생겼어요. 당신은 이 문제를 해결해야 합니다.You have received the new phone but the features are not what you expected.새로 산 핸드폰에 당신이 기대한 기능이 없습니다.You would like to return it to get a new phone.당신은 새로운 핸드폰을 환불 받고 싶어요.Call the store, explain the situation, and make arrangements to get a new product.가게에 전화해서, 상황을 설명하고 새로운 ..

이번 포스트는 롤플레잉 문제인 11번, 12번, 13번 중 11번에 관한 것이다. RP(Role Playing) Set에는 두 가지 시나리오가 있다.1. 낯선 사람과 이야기 하는 상황2. 내가 알고 있는 누군가와 이야기 하는 상황 이 두 가지 시나리오를 이용해서 3가지 다른 방법으로 의사소통할 것이다.a. In person(개인적으로)b. Over the phone(전화상으로)c. Leaving a message on an answering machine(자동 응답기에 메세지 남기기) c 방법은 잘 안나온다. 대답이 1분을 넘으면 안된다. # 질문You would like to buy a new cellphone.당신은 새로운 핸드폰을 사고 싶어요.Call a store and ask 3 or 4 que..

이번 포스트는 콤보세트(CS)에서 어떻게 transition하는지에 관한 것이다. # 3 Questionstransitiontell you more / elabratenaturally expressexcuse # Condition"Teacher, my condition is so bad." 위 문장은 매우 어색한 표현이다. 다음과 같이 표현하는 것이 좋다.I'm not feeling well(good).I'm feeling ill.I think I caught a bit of a bug ~I came down with something ~I'm not feeling like myself today ~(오늘 나 왜이러는지 모르겠어 ~ 같은 표현)  Recycling / Fashion / Weather / ..

Past Experience 할 때 주의할 사항1. MP2. Fillers / Feelings(detail에 집중하지 말고 감정에 집중하자! )3. Freestyle4. Conclusion ++ Direct Quotation, 직접 화법을 통해 답변을 다이나믹하게 하자! 딴 사람이 나한테 ~~ 말을 했다라는 걸 표현할 때는, 직접 화법에 나의 이름도 넣어주면 좋다. 나 혼자 말하는 거를 답하고 싶다면, 다음 표현을 사용해보자.I thought to myself...I was like... 직접 화법은 문법이 중요하다. 짧게 이야기하면서 연습해가다가 나중에 길게 연습해보자.