this-is-kim

*다이나믹 프로그래밍 -동적 계획법 -메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시키는 방법 -조건 큰 문제를 작은 문제로 나눌 수 있음 작은 문제의 답이 큰 문제의 답 -풀이 방법 탑다운(하향식, 메모제이션) : 재귀 함수 보텀업(상향식) : 반복문 -다이나믹 프로그래밍의 전형적인 형태는 보텀업 -결과 저장용 리스트를 DP 테이블이라고 함 *피보나치 수열 with DP 1) 재귀 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) -시간복잡도 : O(2^n) -n이 커질수록 비효율적임 2) 탑다운 : 재귀 + 메모제이션 def fibo(x): if x == 1 or x == 2: ret..

*순차 탐색 (Sequential Search) -데이터를 차례대로 확인하는 방법 -시간복잡도 : O(N) # 반복문 def sequential_search(data, target): for i in range(len(data)): if target == data[i]: return i + 1 data = list(input().split()) target = input() print(sequential_search(data, target)) *이진 탐색 (Binary Search) -데이터가 정렬되어있는 경우에 사용 -시작점, 중간점, 끝점 -찾으려는 데이터와 중간점 위치의 데이터를 비교 -한 번 확인할 때마다 확인할 원소의 갯수가 절반으로 줌 -시간 복잡도 : O(logN) # 반복문 def bina..

*정렬(Sorting) -연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘 -선택 정렬 / 삽입 정렬 / 퀵 정렬 / 계수 정렬

DFS(Depth-First Search) BFS(Breadth First Search) 탐색 방법 깊이 우선 탐색 너비 우선 탐색 동작 원리 스택 - FILO 큐 - FIFO 구현 방법 재귀 함수 큐 자료구조 def dfs(v): visited[v] = true for i in graph[v]: if not visited[i]: dfs(i) graph = [[0]*m for _ in range(n)] visited = [False] * n dfs(v) from collections import deque def bfs(v): queue = deque([v]) visited[v] = True while queue: n = queue.popleft() for i in graph[n]: if not visi..

-풀이를 떠올리는 것은 쉽지만 소스코드를 작성하기는 어려운 문제 -대표 유형 : 완전 탐색(모든 경우의 수를 다 계산), 시뮬레이션(한 단계씩 차례로 수행) -시간, 메모리를 고려해 코딩을 해야함 (파이썬 기준, 1초에 2000만번 이하 연산 / 크기가 1000만 이하인 리스트) 상하좌우 N×N 크기의 정사각형 공간이 있다. 가장 왼쪽 위의 좌표는 (1, 1)이고, 가장 오른쪽 아래 좌표는 (N, N)이다. 시작 위치는 (1, 1)이고, 상하좌우로 움질 수 있다. 여행 계획의 문자가 다음을 의미할 때, 여행 계획에 따른 최종 도착 지점을 구하여라. 단, 정사각형 공간을 벗어나는 움직임은 무시된다. L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위로 한 칸 이동 D : 아래로 한 칸 이..

Greedy -Greedy : 탐욕스러운, 욕심 많은 -미래를 생각하지 않고 현재 상황에서 가장 최선의 선택을 하는 알고리즘 -'가장 큰 순서대로', '가장 작은 순서대로'와 같은 키워드 제시 -정렬 알고리즘과 함께 나오는 경우 많음 거스름돈 카운터에는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러줘야 하는 동전의 최소 갯수를 구하여라. 단, 거슬러 줘야 하는 돈 N은 항상 10의 배수이다. n = int(input()) count = 0 coins = [500, 100, 50, 10] for coin in coins: count += n // coin n = n % coin print(count) 문제풀이 -문제 해결 포인..