코딩개발로 물장구치는 개발자

안녕하세요 Dibrary입니다. 파이썬으로 설명된 자료구조 책을 보면 여느 다른 책들과 같이 '리스트, 트리, 정렬, 탐색, 그래프' 등이 나와있습니다. 근데 파이썬을 자주 써 본 사람이라면 이런 의문이 들죠. 파이썬에서는 어차피 리스트 자료형이 있는데.... 물론, 저도 그런 생각을 한 적이 있습니다. (그리고 그 리스트 자료형은 여기서 말한 연결리스트도 아니죠;;) 그런 혼란을 가지고 있지만 불편함은 없어서 그냥 유야무야 넘어가다가, 자료형 리스트가 아닌 자료구조 '단순 연결리스트, 이중 연결리스트, 원형 연결리스트' 등을 배워야 하는 이유를 최근에 알고리즘을 풀다가 깨달았습니다. 1. 불필요한 공간 낭비를 위해서 사용할 수 있다. 애초에 리스트를 배열 대신에 쓰는 이유는 공간 사용의 효율을 높이기 ..

안녕하세요 Dibrary입니다. Trie 자료구조는 트리 형태의 자료구조인데, '문자열' 검색을 용이하게 하기 위한 자료구조 입니다. 먼저 구글에 Trie python를 검색해보면 여러 이미지들이 나옵니다. 그 중에 한 개를 살펴 보죠. 이게 뭘 의미하는거냐면, to와 tea와 ten이라는 단어는 똑같이 t로 시작하죠? 그래서 t라는 노드 밑에 위치합니다. to에서 o는 tea와 ten에 없으므로 t 노드 밑에 o가 있음으로써, 해당 경로로 검색을 하게 되면 to가 나오는 것이죠. tea와 ten은 t도 똑같고, e도 똑같습니다. 따라서 t노드 밑에 e노드가 있고, e노드 밑에 a와 n으로 나뉘는 것이죠. 이런식으로 문자열을 저장해두고, 찾을 때는 금방 찾게 만든 자료구조가 Trie 입니다. 파이썬으로 ..

안녕하세요 Dibrary입니다. 이번에 소개할 자료구조는 스택 입니다. 연결 리스트보다 어찌보면 간단한? 자료구조입니다. (이해하기는 굉장히 쉬운데 실제 쓰임새는 연습하지 않고는 떠오르지 않는 괴랄한... ) 스택의 특징은 딱 하나 입니다 LIFO (LAST에 IN 한 데이터가 FIRST로 OUT 한다) 이거 한 개만 아셔도 스택 개념의 절반은 먹고 들어간다~ 이거죠. 스택은 반드시 LIFO만 유지되면 됩니다. 그럼 여기서 LAST에 IN한 다는 의미와 FIRST로 OUT한다는 의미가 무엇인가 코드로 살펴보겠습니다. (물론 파이썬으로요) 임의로 stack이라는 이름의 list를 만들어 보았습니다. 1, 2, 3을 순서대로 넣고 확인해 보니 순서대로 들어갔네요. pop을 하니까 맨 마지막에 넣은 3이 제일..

안녕하세요 Dibrary입니다. 앞에서 단일연결 리스트를 보셨다면, '역순으로도 확인할 수 있으면 좋겠다~' 싶은 생각이 드셨을 수 있는데, 이 기능도 같이 구현한 것이 이중연결 리스트 입니다. 2022.05.17 - [자료구조] - 연결리스트 - 단순 연결 리스트 이렇게 양방향 화살표인 셈이죠. 근데, 사실 '개념'은 이래도, 양방향으로는 각 Node별로 앞, 뒤가 나뉘어져 있습니다. 따라서, 아래와 같이 표현하는 게 좀 더 정확합니다. 그래도 앞에서 뒤로, 뒤에서 앞으로 올 수 있다는 사실은 변함이 없습니다. 이번에도 파이썬으로 코드 구현을 해보겠습니다. 먼저 노드만을 만들어 보고 기본 개념 확인을 해보겠습니다. A와 B와 C라는 노드를 만들고, A B C 이렇게 연결 했습니다. A부터 C까지 값을 ..

안녕하세요 Dibrary입니다. 이번에 정리해볼 자료구조는 리스트 입니다. 일반적으로 리스트란 일련의 동일한 타입의 항목을 의미. 뭔 소리냐하믄, 비슷한 것을 줄줄이 소세지 마냥 엮어 놓은 것이라 보면 됩니다. 근데 우리는 이미 비슷한 자료구조를 알고 있죠? 배열. 배열과의 차이는 뭘까요? 배열은 데이터가 연속으로 위치해 있고, 리스트는 그럴수도 있고 아닐수도 있다는 것입니다. 리스트를 잘 보시면 군데군데 꼭 붙어있지 않더라도 연결을 해서 하나의 '배열 처럼' 만들었죠? 이렇게 떨어진 곳의 데이터를 하나의 '배열 처럼' 다루고자 하는 것이 리스트 자료구조 입니다. 보면 데이터 1개마다 1개의 화살표로 다음 데이터를 이어줬는데 한 방향입니다. 이렇게 만든 것이 단순연결리스트 이고,이 화살표가 양방향이라면 ..

안녕하세요 Dibrary 입니다. 이번에는 사전형을 써야만 풀리는 문제를 정리해보고자 합니다. 먼저 제가 몇 번을 틀린 방식은 아래와 같습니다. 문제에서 주어진 500000이라는 횟수의 비교를 너무 가벼이 생각했음. list가지고 해결이 안 되길래, set을 이용했음. 그럼에도 안 됨. 우선 500000이라는 횟수는 생각보다 간단하네~ 라고 착각했던게 큰 오판이었습니다. 차례대로 비교를 해 나가야 하는 것이므로, 500000*500000 의 경우의 수가 있죠... ... 그래서 리스트로 접근했던 아래 코드는 시작도 못해보고 시간초과에 걸렸습니다. sys.stdin.readline 을 이용해서 입력을 받았음에도 말이죠. 그래서 set으로 담으면 괜찮을까? 싶어서 set으로 시도를 해보았는데, 역시나 시간초..

개발자라면 뗄레야 뗄 수 없는게 '자료구조'와 '알고리즘'이다. 그 중에 이 책은 제목 중 '알고리즘'에 강점이 있는 책이다. 알고리즘은 말 그대로 '문제를 푸는 방법'이다. 초,중,고등학교를 기본교육으로 들은 사람이라면 '수학' 과목을 잊을 수 없을텐데 수학 문제를 푸는 것과 같은 이치인 셈이다. 반드시 생각을 해봐야 하고, 단순히 배운 개념만 가지고는 문제를 푸는데 써먹을 수 없었던 기억이 있을 것이다. 알고리즘도 몇몇 형식화된 그리고 유명한 것들이 존재한다. 문제는 그것들을 아주 완벽히 암기를 했다 하더라도? 실제 주어진 문제에 해당 알고리즘을 사용해야 하는지 아닌지를 판별할 수 없다. 그럼 이 책은 그 방법을 알려주는가? 그것도 아니다. 그러나, 이 책의 강점은 내 생각을 정리할 수 있는 하나의 ..