Algorithm

[알고리즘] 자료구조: 시간복잡도, 공간복잡도

알고리즘 복잡도 계산이 필요한 이우 하나의 문제를 푸는 알고리즘은 다양할 수 있음 정수의 절댓값 구하기 1, -1 --> 1 방법 1: 정수 값을 제곱한 값에 다시 루트를 씌우기 방법 2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산한다. 복잡도(Complexity) 시간 복잡도(Time Complexity): 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸렸는지를 의미 (알고리즘을 위해 필요한 연산의 횟수) 공간 복잡도(Space Complexity): 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 (알고리즘을 위해 필요한 메모리의 양) 가장 중요한 시간 복잡도를 꼭 ..

[알고리즘] 자료구조: 링크드 리스트(Linked List)

링크드 리스트 구조(Linked List) 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조 링크드 리스트 기본 구조와 용어 노트(Node): 각 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 링크드 리스트 장단점 장점 미리 데이터 공간을 할당하지 않아도 됨 배열은 미리 데이터 공간을 할당해아함 단점 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업..

[알고리즘] 자료구조 스택(Stack)

스택(Stack) 데이터를 제한적으로 접근할 수 있는 구조 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 큐: FIFO 정책 스택: LIFO 정책 용도 및 예제 대표적으로 많이 사용하는 곳이 브라우저이다. 인터넷 서칭 중 뒤로 가고 싶을 때 뒤로 가기 버튼을 누른다. '뒤로 가기' 버튼이 바로 스택으로 구현된 메소드 중 하나이다. 스택 구조 스택은 LIFO(Last In, First Out) 또는 FIFO(Frist In, Last Out) 데이터 관리 방식을 따름 대표적인 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push(): 데이터를 스택에 넣기 pop(): 데이터를 스택에서 꺼내기 peek(): 마지막 위치..

[알고리즘] 자료구조 : 큐 (Queue)

Queue 큐는 자료구조의 스택과 반대의 구조라고 생각하면 된다. 큐는 FIFO(First In First OUt)의 형태를 가지게 된다. 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다. 카페에 대입해서 설명해보면 카페에서 음료를 시키고 받은 주문번호가 있을 것이다. 이 번호표 기계도 프로그래밍된 프로그램인데 그 번호가 108번이라면 내 번호인 108번을 부를 때는 처음인 1번부터 확인해서 이 손님이 서비스를 받았는지 안 받았는지 확인하며 다음으로 호출할 번호를 정할까? 이러면 매우 비효율 적이다. 단순하게 생각하면 서비스를 받을 처음 위치와 마지막의 위치만 기억하면 모든게 쉽게 풀린다. 이 위치들을 큐에서는 front, rear이라고 한다. 위 그림을 보면 Enqueue는 맨 뒤에 어떤 요..