ETC/알고리즘 이론8

• 

  [알고리즘] 최단 경로 알고리즘 (Python, Java) 출처 : 2021 이코테 최단 경로 문제 - 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. - 다양한 문제 상황 - 한 지점에서 다른 한 지점까지의 최단 경로 - 한 지점에서 다른 모든 지점까지의 최단 경로 - 모든 지점에서 다른 모든 지점까지의 최단 경로 - 각 지점은 그래프에서 노드로 표현 - 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. - 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. - 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. - 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. - 매 상황에서 가장 비용이.. ETC/알고리즘 이론 2021. 11. 25.

• 

  [알고리즘] 그리디 알고리즘 ( 탐욕 알고리즘 ) (Python, Java) 출처 - 이코테 2021 그리디 알고리즘 - 그리디 알고리즘(탐욕 알고리즘) 은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. - 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. - 그리디 해법은 그 정당성 분석이 중요하다. - 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 그리디 알고리즘 - 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고싶다. - Q. 최적의 해는 무엇인가? - Q. 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까? - 그리디 알고리즘은 이처럼 매 상황에서 가장 큰값만 고르는 방식이라 최적알고리즘보다는 값이 작을 수 있다. - 일반적인 상황에서 그리디 알고.. ETC/알고리즘 이론 2021. 10. 19.

• [알고리즘] 리스트의 모든 조합 구할때 고려할점 (permutations, combinations VS product) (Python) 리스트 내의 값들의 모든 조합을 구하기 위해 itertools를 사용하는것은 다 알고 있을것이다. 2021.08.06 - [/[Algorithm]] - [파이썬] 경우의 수 (순열, 조합) 구하기 - itertools [파이썬] 경우의 수 (순열, 조합) 구하기 - itertools import itertools itertools 라이브러리를 사용하여 원소들의 순열과 조합을 사용할 수 있다. 1. 순열 순열은 서로 다른 n개 중, r개를 나열하는 경우의 수로 permutations 함수를 사용한다. def permutation(sel.. earthteacher.tistory.com 하지만, 문제를 풀다 자주 부딪히는 고민이 생겨 따로 포스팅을 하게 되었다. 바로 단일 리스트 내부 원소들의 조합을 구할때 .. ETC/알고리즘 이론 2021. 8. 20.

• 

  [알고리즘] 경우의 수 (순열, 조합) 구하기 - itertools (Python) import itertools itertools 라이브러리를 사용하여 원소들의 순열과 조합을 사용할 수 있다. 1. 순열 순열은 서로 다른 n개 중, r개를 나열하는 경우의 수로 permutations 함수를 사용한다. def permutation(self): # n=5, r=2 resultList = list(itertools.permutations(["1", "2", "3", "4", "5"], 2)) print("경우의 수 : {}개".format(len(resultList))) print(*resultList, sep="\n") #결과 경우의 수 : 20개 ('1', '2') ('1', '3') ('1', '4') ('1', '5') ('2', '1') ('2', '3') ('2', '4') ('.. ETC/알고리즘 이론 2021. 8. 6.

• [알고리즘] 재귀함수 (Recursive Function) 재귀함수 재귀함수란 함수 내에서 자기 자신을 호출하여 작업을 수행하는 방식의 함수이다. 재귀함수를 작성할 때는 함수 내에서 자기 자신을 다시 호출한 후, 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료조건이 꼭 포함되어야한다는 부분을 인지하고 작성하면 오버플로우를 피할 수 있다. 다시말해 재귀함수에서 중요한 부분은 실행을 마무리짓는 부분과, 계속 재귀를 실행하는 부분이 존재한다는것이다. 또한 그것이 일반적으로는 n이 0이나 1이 되면 종료하게 되게끔 구성이 되어있다. 1. 카운트다운 def countdown(n) : # 0 이 되는순간 end 출력 if n==0 : print("end") # 받은 인자 출력 및, n-1 한값을 다시 재귀 else : print(n) cou.. ETC/알고리즘 이론 2021. 8. 2.

• 

  [알고리즘] 피보나치 수열(Fibonacci Sequence) 알고리즘 (JAVA) 본 포스트는 여러 피보나치 수열 알고리즘 관련 게시글 중 해당 포스트를 참고하여 Python to Java로 작성해본 포스트입니다. 피보나치 수열이란? 피보나치 수열(Fibonacci Sequence)은 단순한 단조 증가(monotonically increasing) 수열로 0번째 항은 0, 1번째 항은 1, 그 외 항은 전번, 전전번 항의 합으로 표현된다. 바로 위 그림은 피보나치 수열의 첫 10항 정도를 보여주고있다. 흔히 나오는 문제는, 0 이상의 정수 n이 주어질 때 n번재 피보나치 수를 구하는것이다. n번째 피보나치 수를 구하는 fibo함수는 다음과 같이 정의할 수 있을 것이다. 기본 재귀적 풀이 앞서 만든 fibo함수를 그대로 구현하면 된다. public class FibonacciTest {.. ETC/알고리즘 이론 2020. 10. 16.

• 

  [알고리즘] Towers of Hanoi - 하노이의 탑 알고리즘 분할정복 알고리즘을 사용하여 하노이탑(Towers of Hanoi) 문제를 풀어보자. 하노이탑은 말뚝 3개와 크기가 모두 다른 구멍난 디스크 n개로 구성되어 있다. 문제는 한 말뚝에 쌓여있는 n개의 디스크를 모두 지정한 말뚝으로 옮기는 것이다. 규칙 문제를 풀 때 다음 규칙을 반드시 준수해야 한다. (1) 세 개의 말뚝 이외에는 디스크를 놓을 수 없다. (2) 한 번에 하나의 디스크만 옮길 수 있고, 말뚝의 맨 위에 있는 디스크만 옮길 수 있다. (3) 큰 디스크를 작은 디스크 위에 올려놓을 수 없다. 디스크의 수가 n개인 하노이 탑은 최소 $2^n - 1$단계로 풀 수 있다. 위 사진은 디스크의 수가 3개인 하노이 탑이 $2^3 - 1 = 7$단계를 거쳐 풀이됨을 보여준다. 알고리즘 일단, 세개의 기둥.. ETC/알고리즘 이론 2020. 10. 4.

• Edgher W. Dijkstra - Go To Statement Considered Harmful 을 읽고. https://web.archive.org/web/20070703050443/http://www.acm.org/classics/oct95/ Go To Statement Considered Harmful 380 captures 20 Dec 1996 - 05 May 2020 web.archive.org Go To Statement Considered Harmful Edsger W. Dijkstra Reprinted from Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148. Copyright © 1968, Association for Computing Machinery, Inc. This is a digitized copy derived .. ETC/알고리즘 이론 2020. 5. 26.