파이썬/알고리즘 정리 (5) 썸네일형 리스트형 알고리즘 정리 <최단 경로> 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 일반적으로 컴퓨터공학과 학부 수준에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지이다. 오늘은 이 중에서 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형을 다룰 것이다. 1. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. - 기본 원리 - 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. 3) 방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드를 선택한다. 4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하.. 알고리즘 정리 <다이나믹 프로그래밍> 다이나믹 프로그래밍 다이나믹 프로그래밍이란 다양한 알고리즘 문제를 푸는 상황에서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이다. 쉽게 말로 표현하자면 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 1 1 2 3 5 8 13 21 34 55 89 이를 점화식으로 나타낼 수 있는데 an+2 = an+1 + an과 같이 표현할 수 있고 프로그래밍으로 표현하면 다음과 같다. [소스 코드] def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(.. 알고리즘 정리 <이진 탐색> 이진 탐색 알고리즘이란 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 먼저 이진 탐색을 배우기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 알아보겠다. 1. 순차 탐색 순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 데이터 예시) 순차 탐색으로 "dongbin"을 찾는 과정 list = ["haneul", "jonggu", "dongbin", "taeil", "sangwook"] 1) 가장 먼저 첫 번째 데이터를 확인한다. -> "haneul"은 찾는 데이터가 .. 알고리즘 정리 <정렬> 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램을 작성할 때 보통 오름차순, 내림차순 등 어떤 방식으로든 정렬해서 사용하는 경우가 많다. 일반적인 코딩 테스트 문제에서는 요구하는 조건에 따라서 적절한 정렬 알고리즘이 사용되어야 한다. 상황에 적절하지 못한 정렬 알고리즘을 이용하면 프로그램은 비효율적으로 동작하며 필요 이상으로 시간을 많이 소모한다. 정렬 알고리즘에는 대표적으로 [선택 정렬, 삽입 정렬, 퀵 정렬]이 있다. 1. 선택 정렬 쉽게말해 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것. 이 방법은 가장 원시적인 방법으로 매번 .. 백준 알고리즘 1일차. (파이썬 input함수, split함수) 오랜만에 코딩을 그것도 이번에 처음배우는 파이썬으로 하려니깐 생각보다 막혔다. 백준사이트보니깐 단계별로 보기쉽게 나눠져있어서 첫번째 단계인 '입출력과 사칙연산' 총 11문제를 풀었는데 생각보다 시간이 걸렸다. 생각보다 구글링도 많이하고 그 과정에서 얻은것들이 좀 있다. 앞으로는 블로그에 백준 알고리즘을 풀면서 새로 알았던 사실들을 정리하는 글을 올리면 좋을 것 같다. 1. 역슬러쉬를 출력하려면 역슬러쉬를 두번 입력해야한다. print("\\") // 출력 : \ 2. 파이썬에서 사용자의 입력을 받는 함수는 input이다. name = input("이름을 입력하세요. : ") 3. 사용자의 입력을 받고 각각 나눠주는 함수는 split()이다. a,b = input().split() // 입력을 3 1로했다.. 이전 1 다음