CS 지식/Algorithm-이론 및 PS스킬 정리

Big - O Notation, 흔히 말하는 O표기법이란 최악, 최선의 성능중 최악의 성능에 해당한다. 최악의 성능을 평가하는 이유는 적어도 일정정도의 성능은 보장한다는 의미이다. O 표기법은 알고리즘의 성능을 평가하기 위해 처리해야할 데이터의 양에 대한 실행시간을 수학적 으로 계산한 방법이다시간 복잡도 함수에서 알고리즘 분석을 원활하게 하기 위해 시간 복잡도를 표기하는것을 Big -ONotation이라고 한다. 다음과 같은 for문이 있다고 가정하자. 이 루프 제어문은 n개의 대입연산과, n+1번의 비교연산, n번의 덧셈 연산을 포함하여, 총 3n + 1개의 연산이 생긴다. 추가적으로 루프문 내에서는 n번의 덧셈연산과, n번의 대입연산, 총 2n이 발생하여 해당 루프문은 최종적으로5n+1 이라는 연산을..

(Codes : https://github.com/J-Hoplin/Algorithm-with-Python/tree/master/4%20.%20Double%20Linked%20List)1 . Doubly Linked List 앞에서 보았던 연결리스트는 단일 연결 리스트(Singly Linked List)였다. 연결리스트는 배열과 같이 물리적 메모리적 메모리가 아닌 링크라는 형식의 개념을 사용하기에 관리하기가 매우 쉬웠다. 하지만 단일 연결리스트의 한계가 있다. 바로 일방성이라는것이다. 한방향으로만 나아갈 수 있을뿐 그와 반대방향으로 링크를 시킬 수 없다는 단점이 존재한다. 앞으로 볼 이중 연결리스트는 단일 연결리스트와 달리 양방향성을 지니고 있다.다음 사진을 보자. 임의의 링크는 자신의 다음 링크도 가리키..

프로그래밍 단계는 다음과 같이 이루어 진다. 문제의 이해 -> 논리의 설계 -> 코딩 -> 번역 -> 테스트 -> 활용 다음과 같은 단계들이 있는데 이중 순서도는 프로그램 논리 설계 과정에서 쓰인다. 순서도란 문제 해결에 쓰인 논리를 단계적으로 그림으로 표현한 것을 말한다. 또한 순서도를 이용하면 명령문들의 관계를 시각적으로 보여줄 수 있다. 순서도 작성하는데 있어 방법은 다음과 같다. 1) 명령문의 기능에 해당하는 의미를 지닌 도형을 그림.2) 명령문의 정확한 순서를 파악하기 위해 화살표를 이용해서 흐름을 그림 대부분의 프로그램은 입력, 처리, 출력 기본적인 이 세가지 단계를 모두 지니고 있다.이제 순서도의 기호들에는 어떤것들이 있는지 살펴보자. 1) 단말(terminator) 이 기호는 단말(term..

1 . Linked List Linked List는 대부분의 알고리즘에서 사용하는 자료구조이다. 알고리즘에서 사용하는 데이터와 다음 노드(Node)를 가리키는 링크(Link)를 묶어 노드로 정의해 사용한다. C 혹은 C++의 개념에서는 포인터 개념을 링크로 사용하지만 파이썬은 해당 개념이 존재하지 않는다. 우선 용어부터 알아보자. 연결리스트에는 기본적으로 링크와 노드 라는 용어를 사용한다. 파이썬에서 연결리스트를 사용하기 위해서는 노드를 클래스로 정의하여 사용한다. 1234class Node: def __init__(self,data,link = None): self.data = data self.link = linkcs 이 클래스의 경우 호출 시 __init__메서드를 호출하고 Node라는 클래스는 d..

1 . O표기법 최악, 최선의 성능중 최악의 성능에 해당한다. 최악의 성능을 평가하는 이유는 적어도 일정 정도의 성능은 보장한다는 의미이다. O 표기법은 알고리즘의 성능을 평가하기 위해 처리해야할 데이터의 양에 대한 실행시간을 수학적으로 계산한 방법이다 O 표기법에는 다음과 같은 7가지의 방법이 존재한다. 1) O(1) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양과는 상관없이 항상 일정한 실행시간을 갖는 알고리즘을 의미한다. 2) O(log2N) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양이 증가할수록 실행 시간도 약간씩 증가하는 알고리즘을 의미한다. 실행 시간의 증가폭 자체가 logN의 그래프를 가지므로 급격하게 증가하지는 않는다. 일반적으로 효율이 좋은 검색 알고리..