CS24 자료구조 리스트 (List) - Linked List, Array List, Vector 차이점 포함 리스트? (Linked List - 연결 리스트) 일반적으로 '리스트'는 연결 리스트(Linked List)를 뜻한다. 이후 Array List와 Vector를 추가로 설명하기 전까지 모든 설명은 연결 리스트(Linked List)에 대해 다룬다. 리스트는 배열처럼 데이터를 순서대로 표현하는 자료구조 중 하나인데, 구현 방법에 큰 차이가 있다. 배열은 메모리 상에 연속된 공간을 '미리 할당받고' 메모리상에 데이터를 순서대로 넣어 만든 자료구조이다. 리스트는 메모리 상에 데이터가 어디에 있던 신경쓰지 않는다. 'data = [12. 3. 11. -2]'를 배열과 리스트로 표현해보겠다. 위의 정갈하게 메모리상에 순서대로 들어가 있는 것이 배열, 아래쪽에 메모리상에 흩뿌려져 있는 것이 리스트이다. 이 때 배열.. 2021. 9. 30. BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS (2022-08-27 업데이트) 2022-07-21 업데이트 : 글 맨 아래에 '풀어보기'로 풀어볼만한 문제 링크 추가 2022-08-27 업데이트 : '풀어보기' 좀 더 추가, 목차 추가 목차 BFS (Breadth-first Search) 명확히 검증하면서 쓴게 아니라서 틀린 부분 있으면 알려주세요! - BFS와 DFS 대충 곰처럼 생긴 섬이 바다에 떠 있다. 편의상 이 섬을 20등분해서 격자 형태로 구역을 나누었다. 이제 우측상단의 귀(곰 입장에서 왼쪽귀)부터 출발해서 섬 전체를 둘러보려 한다. 둘러보는 방법은 여러가지가 있을 수 있다. 빨간 숫자는 둘러본 순서를 뜻한다. (0 부터 19까지) A처럼 자신과 가까운 곳부터 순서대로 살펴볼수도 있다. 격자형태로 나누었으므로 Manhattan Distance (Taxicab Geome.. 2021. 9. 24. 알고리즘 시간복잡도에 대해 목차 Complexity Up & Down 게임을 해봅시다! 1~100까지의 숫자 중 하나를 생각해보겠습니다. 전 96을 생각할껍니다. 이걸 누군가에게 맞춰보라고 하고, up & down으로 대답하겠습니다. "1" ⇒ up "2" ⇒ up "3" ⇒ up .. (92번을 더 한 후) "96" ⇒ 맞았..어.. 이렇게 물어볼사람은 없을껍니다! 다들 자연스럽게 아래와 같이 물어볼꺼에요. "50" ⇒ up "75" ⇒ up "87" ⇒ up "93" ⇒ up "96" ⇒ 맞았어! 이걸 다르게 표현해보겠습니다. 우선 1부터 차례대로 물어본 전자의 경우를 보겠습니다. 1~100까지의 100개를 N개라 표현하겠습니다. 이 경우 만약 생각한 숫자가 100이라면(= 생각한 숫자가 N이라면) 최악의 경우로, 100번 물.. 2021. 9. 22. 자료구조 배열 기본 Arrays 따로 증빙자료를 찾지 않고 생각의 흐름대로 작성한 것이라 사실과 다를 수 있음. 수정할 부분 혹은 추가할만한 내용이 있다면 댓글로 남겨주세요. — 0 배열은 물론 데이터를 표현하는 기타 자료구조들이 없다고 가정하자. 서로 연관된 데이터라 해도 이를 프로그램상에 표현하기 위해 취할 방법은 변수를 여러개 만드는 것이다. 오늘의 기온 데이터를 적당히 샘플링해서 시간 순서에 따라 676개로 나눈걸 표현해보자. int a = 10; int b = 13; int c = 11; ... int zz = 21; 676개의 데이터를 표현하긴 했지만, 이해하기 힘든 코드가 될 것이고 쓸데없이 코드길이도 길어질것이고, 변수명 창작의 고통(어제날짜 기온도 표현하려면?)도 따른다. — 1 그럼 생각을 좀 바꿔서 어차.. 2021. 9. 22. 이전 1 2 3 다음
