1. 다익스트라 알고리즘이란? 다익스트라 알고리즘(Dijkstra Algorithm)은 최단거리 알고리즘 중 하나이다. 음의 가중치(이때 가중치는 거리라고 생각하면 편하다)가 없는 그래프에서 사용할 수 있다. 알고리즘의 작동방식에 따라 음의 가중치가 있는 경우엔 해당 구간을 무한으로 돌아버려 음수의 무한대의 거리가 나오기 때문에 불가능하다. 시간...

DP에 대한 설명은 이하 링크를 참고 DP <1> # 1904 01타일 1904번: 01타일 이번 문제는 “00” 타일과 “1” 타일을 가지고 전체 길이가 N인 2진수의 갯수를 세는 문제이다. 예를 들어 N = 1 인 경우 1 만 가능하다. f(1) = 1 N = 2 인 경우 11과 00이 가능하다. f(2) = 2 N = 3...

동적 프로그래밍 (Dynamic Programing) 동적 프로그래밍이란 이전에 계산한 값을 저장해 둔 후 재활용하는 방법이다. 문제의 주어진 조건에서 점화식을 유도할 수 있다면 동적계획법으로 푸는 것이 효과적이다. 동적 프로그래밍은 이전 값들을 이용하기 때문에 조건에 따라 몇몇 초기 값들은 수동으로 입력해주어야 한다. (초기 값들은 조건에 따라 이...

#9663 N-Queens 9663번: N-Queen 백트래킹 문제에서 널리 알려진 N Queens 문제이다. 간단하게 설명하자면, N x N 크기의 체스판에서 N개의 퀸들이 서로 공격할 수 없는 위치의 경우의 수를 세는 문제이다. 1. 백 트래킹이란? N Queens 문제를 들어가기 전에 백트래킹이 어떤 알고리즘인지 생각해보자. 해당 문제를...

0. 왜 갑자기 Redis? 원래 로그인 기능, 게시판 기능처럼 스탠다드한 기능을 구현하기 위해 MySQL, MongoBD를 먼저 공부해보려 했으나 긴급하게 BD의 검색어 자동완성 기능을 구현할 일이 있어서 먼저 Redis에 대해 알아보려고 한다. 1. 그래서 Redis를 고른 이유 검색어 자동완성 기능은 사용자와 직접 상호작용하는 부분이기 때문...

0. 발단 목표로 하는 로그인 기능과 게시판 기능을 추가하기 위해 그것들을 저장할 DB에 대해 알아보고자 한다. 이번 글에서… 데이터베이스를 사용하는 이유 데이터베이스의 종류 장단점 등을 알아볼 계획이다. 1. 데이터베이스를 사용하는 이유? 사용자가 입력한 정보나, 글들을 저장하기 위해 사용된다. 정보를 단순히 저장하는데 그치...

0. 읽기 전에… 이전 Cookie & Session 링크 이 글을 읽기 전에 위 링크를 통해 공부했던것을 보고 오면 왜 session을 이용하는지 알 수 있다. 1. 공식 문서 읽어보기 session에 대해 flask에서 제공하는 공식 문서가 있다길래 찾아보았다. Quickstart — Flask Documentation (1.1.x...

0. 도입 인터넷에 검색해보면 로그인 기능을 구현하기 위해 사용자가 입력한 정보를 세션이라는 것에 저장한다고 한다. 또한 같이 등장하는 개념인 쿠키 도 있다. 쿠키 역시 입력 정보를 저장하는데 사용되지만 세션이랑 무엇이 다른것일까? 아니, 애초에 사용자의 입력을 저장해야할 이유는 무엇일까? 1. HTTP 프로토콜 쿠키와 세션에 대해 알아보기 전...

#11729 하노이의 탑 하노이의 탑 문제는 대표적인 재귀 알고리즘의 예제이다. 11729번: 하노이 탑 이동 순서 너무나 유명한 문제라 룰을 간단히만 설명하자면 한쪽 탑에 정렬된 원판을 다른 탑으로 옮기는데 이때 거쳐갈 수 있는 탑이 하나 있고 (즉 원래 탑, 거쳐갈 수 있는 탑, 목적지 탑. 이렇게 3개의 탑이 있다.) 작은 원판 ...

#15649 순열 import sys def permutation(n, r, p = []): # n개중 r개 if (r == 0): print(*p) # 하나의 경우 출력 elif (r != 0): for i in range(1, 1+n): if (p.count(i) == 0...