자료구조

📍스택(Stack) > 스택(Stack)은 한 쪽 끝에서만 접근하여 데이터를 넣고 뺄 수 있는 후입선출(LIFO) 형태의 선형 자료구조이다. 비유하자면 빨래통과 같다 🧺 가장 처음 넣은 빨래는 가장 늦게 나오고, 가장 마지막에 넣은 빨래는 가장 빨리 나온다. 새로운 빨래를 넣는다면 먼저 들어간 빨래보다 위에 쌓이는 형태일 것이다. 스택(Stack)은 ...

큐(Queue)는 한쪽 끝에서만 자료의 삽입,삭제가 가능한 선입선출 FIFO 형태의 선형 자료구조이다 스택(Stack)과는 달리 가장 먼저 삽입한 자료가 가장 먼저 반환되는 구조로 이루어진다. 줄의 첫 번째에 서 있는 사람이 먼저 서비스를 받고, 그 다음으로 줄에 선 사람이 서비스를 받는 식으로 생각하면 된다. 하지만 이렇게 list를 큐(Queue) 자...

문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한...

문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X : 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다...

🔎 해시테이블이란? key에 data를 저장하는 데이터 구조이다. 이는 파이썬의 딕셔너리 구조와 동일하다. key를 hash 함수에 넣고 일정한 길이의 해시 코드를 얻게 된다. 이후, 3으로 나눈 나머지인 0,1,1 이 index가 되며 이를 통해 data 를 되찾을 수 있다. 🔎 장점/단점 저장/읽기의 속도가 빠르다. 검색,조회가 빈번한 작업인 경...

🔎 힙이란? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)입니다. 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다. 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다. 그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 갈...

heapq 모듈을 사용하여 최소 힙 구하기

🔎 DFS란? Depth First Search의 약자로, 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다. 🪄 그래프 자료에서 데이터를 탐색하는 알고리즘이라고도 부릅니다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 또, 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 위 과정을 반...

🔦 BFS와 DFS의 차이점 DFS는 탐색하는 원소를 최대한 깊게 따라가야 합니다. 이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, "가장 마지막에 넣은 노드"를 꺼내서 탐색하면 됩니다 - > 그래서 스택(Stack)을 사용 BFS는 현재 인접한 노드를 먼저 방문해야 합니다. 인접한 노드 중 방문하지 않은 모든 노드들을 저장...

너무 어려운 이진 탐색 트리