전체 글

[알고리즘] 자료구조: 링크드 리스트(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는 맨 뒤에 어떤 요..

[운영체제] 가상 메모리

메모리(memory) 메모리란 프로그램과 프로그램 수행에 필요한 데이터 및 코드를 저장하는 장치 메모리는 크게 내부 기억장치인 주기억장치와 외부 기억장치인 보조 기억장치로 분류됨 DRAM, CPU 안에 있는 레지스터(register)와 캐시(cache memory)등이 전자에 해당됨 SSD, HDD 등이 후자에 해당됨 가상 메모리 등장 배경 초창기 컴퓨터에서는 사용 가능한 RAM의 용량이, 가장 큰 실행 애플리케이션의 주소 공간보다 커야 했다. 그렇지 않을 경우 "메모리 부족" 오류에 의해 해당 애플리케이션을 실행할 수 없었다. 이후 컴퓨터에서는 프로그래머가 애플리케이션의 일부분만 기억장치에 올려 실행하도록 지정할 수 있게 하는 어버레이 기법을 사용하여 메모리 부족 문제를 해결하고자 했다. 하지만 이 역..