분류 전체보기

https://yunzae.tistory.com/86 힙 정의및장단점 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 yunzae.tistory.com 힙큐는 힙자료구조를 이용한다. 힙 자료구조는 부모 가 자식보다 항상 크다. 하지만 형제노드사이에는 크기순위가 없다. 전체적인 순위를 따지기보다는 최대값, 최솟값이 필요 할 때 힙큐를 자주 쓴다. 파이썬 힙 자료구조 파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다. 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 ..

최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립되어 있다. 예를 들면 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등의 다양한 사례가 존재한다. 상황에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. 대표적으로 사용하는 최단 거리 알고리즘은 3가지인데 다익스트라(데이크스트라), 플로이드 워셜, 벨만 포드 알고리즘 이다. 이중 다익스트라와, 플로이드 워셜은 꼭 알아야 한다. 이 두가지에 대해서 설명을 하고 추후에 벨만 포드 알고리즘에 대해서 포스팅하겠다. 다익스..

이 문제는 이것이 코딩테스트다.226문제이다. 거스름돈 문제와 비슷하지만, 거스름돈은 최소단위의 돈이 있기에 그리디를 사용할 수 있다. 예를 들면 6원을 받았을때 거스름돈 문제는 1원단위의 돈이 있기때문에 어떤경우에도 거스름돈을 줄 수 있다. 하지만 이 문제에서는 1원단위의 돈이없을 수 있다. 그렇기에 다이나믹프로그래밍을 이용하여 풀어야 한다. 아래는 나의 코드이다. import sys moneyNum, moneyVal=map(int,sys.stdin.readline().split()) money=[] for i in range(moneyNum): money.append(int(sys.stdin.readline().rstrip())) money.sort() dp=[-1]*10001 # 초기값 설정 동전화..

이 문제는 이것이 코딩테스트다 223페이지 문제이다. 아래는 나의 코드이다. import sys N= int(sys.stdin.readline().rstrip()) dp=[0]*1001 dp[0]=0 dp[1]=1 dp[2]=3 for i in range(3,N+1): dp[i]=dp[i-1]+ 2*dp[i-2] print(dp[N]%796796) 아래는 예시코드이다. # 정수 N을 입력 받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업) d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i - 1] + 2 * d[..

템플릿 엔진이란? 템플릿 엔진은 템플릿 양식과 특정 데이터 모델에 따른 입력 자료를 합성하여 결과 문서를 출력하는 소프트웨어 또는 소프트웨어 컴포넌트를 말한다. 특히, 웹 템플릿 엔진은 웹 문서가 출력되는 템플릿 엔진을 말한다. 즉, 웹 템플릿 엔진은 지정된 템플릿 양식과 데이터가 합쳐져서 HTML 문서를 출력하는 소프트웨어를 말한다. 이후 웹 템플릿 엔진을 템플릿 엔진으로 부르겠다. 서버 사이드 템플릿 엔진은 서버에서 DB 혹은 API에서 가져온 데이터를 미리 정의된 템플릿(Template)에 넣어 HTML 문서를 만들어 클라이언트에 전달해주는 역할을 한다. 즉, HTML 코드에서 고정적으로 사용되는 부분은 템플릿으로 만들어두고 동적으로 생성되는 부분만 템플릿의 특정 부분에 끼워 넣는 방식으로 동작한다..

MVC패턴 MVC 패턴은 Model-View-Controller 의 약어로 주로 GUI 기반의 애플리케이션 개발에 사용된 디자인 패턴이다. 지금은 백엔드 기반의 웹 애플리케이션 개발의 기본 모델이 되었으며 모바일 앱 및 프론트엔드 기반 웹 애플리케이션 개발이 늘어나면서 MVP(Model-View-Presenter), MVVM(Model-View-ViewModel)과 같은 패턴들도 널리 사용되고 있다. 모델(Model) 데이터를 처리하는 영역 모델은 앱이 포함해야할 데이터가 무엇인지를 정의 데이터의 상태가 변경되면 모델을 일반적으로 뷰에게 알리며(따라서 필요한대로 화면을 변경할 수 있다) 가끔 컨트롤러에게 알리기도 한다.(업데이트된 뷰를 제거하기 위해 다른 로직이 필요한 경우). 실제 구현에는 데이터베이스..

다이나믹프로그래밍의 정의 및 장단점 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. '기억하며 풀기'라고 부르기도 한다. DP를 쓰는 이유 왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번..

정의및장단점 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 이진트리와 힙 공통점: 힙과 이진 탐색 트리는 모두 이진 트리임 차이점: 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우) 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오..