본문 바로가기

Algorithm7

순열 순열(permutation) 주어진 문자열에 대한 가능한 모든 조합, 즉 순열을 출력하는 방법을 알아본다. 재귀함수를 이용해 순열을 출력하는 방법 data = list("abc") def permute(data, left, right): """ data: character list return the permutation of the given string """ if left == right: print("".join(data)) else: for i in range(left, right+1): data[left], data[i] = data[i], data[left] permute(data, left+1, right) data[left], data[i] = data[i], data[left] # ba.. 2020. 6. 2.
합병 정렬 합병 정렬(merge sort) 시간 복잡도는 $\theta{(n \times logn)}$ 파이썬 소스코드 def merge(arr, l, m, r): i = 0 j = 0 k = l left_sub = arr[l:m+1] right_sub = arr[m+1:r+1] while i 2020. 6. 1.
그래프 개념과 구현 그래프Graph는 정점vertex와 간선edge으로 구성된 데이터 구조입니다. 노드 사이에 간선으로 연결되며, 간선은 방향을 가질 수도 있고 방향을 가지지 않을 수도 있습니다. 즉, 그래프는 아래와 같은 두 가지 속성을 지니고 있습니다. 노드node라고도 부르는 정점의 유한 집합으로 구성됩니다. (u, v) 형태의 순성쌍으로 이루어진 간선의 유한 집합으로 구성됩니다. (u, v)는 정점 u에서 정점 v로 이어지는 간선을 나타냅니다. 방향이 있는 그래프directed graph에서 (u, v)와 (v, u)는 같지 않습니다. 간선은 시간이나 거리, 요금과 같은 가중치weight, 값, 비용을 나타낼 수도 있습니다. 위에서 본 그래프의 속성에서 살펴본 것처럼 그래프의 간선이 여러 종류의 값을 나타낼 수 있기.. 2019. 10. 22.
알고리즘 분석 | 최악의 경우, 평균, 최상의 경우 Worst cases, Average cases, and Best cases 알고리즘을 분석 할 때 세 가지 경우로 나눌 수 있다. 워스트 케이스, 에버리지 케이스, 베스트 케이스 세 가지가 있다. 선형 탐색(Linear search)을 예로 들어보자. 최악의 경우 최악의 경우는 알고리즘이 실행되는 시간의 상한을 결정한다. 프로그램을 실행 할 때 연산이 수행되는 횟수가 최대가 되는 경우이다. 선형 탐색의 경우 찾으려는 원소가 배열에 존재하지 않거나 배열의 끝에 존재하는 경우이다. 배열에 찾으려는 원소가 존재하지 않으면 배열의 전체 원소와 모두 비교를 한다. 따라서 선형 탐색의 최악의 경우 시간 복잡도는 $\large \theta (n)$ 이다. 평균적인 경우 평균적인 경우를 계산하는 방법은 다음과 같다... 2019. 5. 23.
알고리즘 분석 방법 | 점근적 분석 성능(Performance) 분석을 하는 이유 프로그램을 작성할 때 고려해야하는 사항이 많다. 사용자 편의성이 좋아야하며, 모듈성, 보안, 유지 관리 등이 중요하다. 이 뿐만 아니라 성능도 중요하다. 그렇다면 성능은 왜 중요한 것일까? 답은 간단하다. 성능이 좋아야 앞서 언급한 것들을 이룰 수 있다. 성능을 공부하는 이유 중 또 다른 하나는 재미있기 때문이다. 조금 더 실용적인 예를 들어보자. 만약 워드나 한글 같은 텍스트 에디터가 100페이지를 로드하는데 한시간이 걸린다면 어떨까? 동영상을 재생하기 위해 1시간이 걸린다면 어떨까? 이러한 경우 퍼포먼스, 즉 성능은 필수적이다. 성능 분석은 어떻게 할 수 있을까? 하나의 문제 혹은 태스크를 풀 수 있는 두 가지 알고리즘이 있다고 생각해 보자. 어느 것이 .. 2019. 5. 22.
자바 알고리즘 또는 프로그램 시간 성능 측정하는 방법 시간 측정하는 방법 currentTimeMillis현재 시간을 반환해주는 메소드인 currentTimeMillis()를 사용하면 시간을 측정할 수 있다. 시간을 측정하면 프로그램의 성능을 알아볼 수 있다.프로그램이 시작될 때의 시간을 구하고, 끝 났을 때의 시간을 구해서 빼주면 된다. 그러면 프로그램이 동작한 시간을 구할 수 있다. 실제 사용 예 // time public class Tistory { public static void main(String[] args) { int i = 100000; long startTime = System.currentTimeMillis(); program(100000); long estimatedTime = System.currentTimeMillis() - sta.. 2018. 10. 16.
자료구조 및 설계 실습1 소스코드 및 보고서:인접 리스트를 이용해 그래프를 저장 자료구조 및 설계 실습1 소스코드 및 보고서:인접 리스트를 이용해 그래프를 저장 문제1)인접 리스트를 이용해 그래프를 저장하는 프로그램인 리스팅 16.3에 한 개의 edge를 그래프에서 제거하는 함수를 작성하고 테스트하시오.- 교재 16.3의 그래프 객체에 간선을 제거하는 함수 추가- 그래프의 간선 제거 전 후를 확인 문제2)a. 인접행렬을 이용해 그래프를 저장하는 프로그램인 리스팅 16.1에 너비우선탐색을 수행하는 메소드를 작성하시오- 교재 16.1 그래프 객체에 너비우선탐색을 수행하는 함수 추가- 교재 큐(Queue) 객체를 너비우선탐색에 이용b. 16.1 그래프에 대해 너비우선탐색을 수행한 결과를 프린트하는 테스트 클래스를 작성하여 수행하시오.- 너비우선탐색을 수행하는 동안 방문하는 정점을 출력- .. 2018. 9. 2.

티스토리툴바