devkty 님의 블로그

트리[참고 사이트]https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.htmlhttps://blog.encrypted.gg/1019https://velog.io/@orcasuit/%ED%8A%B8%EB%9D%BC%EC%9D%B4-Triehttps://wikidocs.net/193702데이터 사이의 계층 관계를 표현하는 트리 구조를 알아봅니다. 무방향이면서 사이클이 없는 연결 그래프입니다.각 노드는 하나의 알파벳 문자를 가지고, 루트에서 임의의 노드까지 경로를 따라가면 해당 경로에 해당하는 문자열을 찾을 수 있습니다.위와 같은 그림을 트리 구조라고 합니다.용어루트(root): 트리의 가장 위쪽에 있는 노드. 트리 하나당 1개 존재리프(단말/외부 노드)..

그래프(vertex, edge, node, arc)자세한 내용은 https://blog.encrypted.gg/1016 를 참고하면 좋습니다.그외 참고 사이트https://velog.io/@orcasuit/그래프vertex-edge-node-archttps://velog.io/@ffwang/인접-행렬과-인접-리스트https://suyeon96.tistory.com/32위와 같은 것을 우리는 알고리즘에서 그래프라고 합니다. 그림에서도 알 수 있듯이 그래프는 Vertex라는 노드와 Edge라고 불리는 간선의 집합으로 구성됩니다.관련 용어Vertex(정점, 노드): 데이터가 저장되는 그래프의 기본 원소Adjacent Vertex(인접 정점): 정점에서 간선으로 직접 연결되어 있는 정점(1번 기준으로 3,2,8..

오늘은 컨디션이 좋지 않았네요...몇일 전 목감기가 이제는 코감기로 왔는지 재채기가 심합니다. 정글에 있으면서 여러분께서 걸리네요. 아무래도 밀폐되서 그런가 봅니다. 몸관리 잘하고 컨디션 조절을 잘해야되겠습니다.오늘은 3주차의 핵심 키워드인 그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬에 대해서 학습 했습니다. 위상정렬은 추후 업데이트할 예정이고 나머지 키워드에 대해서 다음 포스팅부터 올리겠습니다.사진은 레전드 식사 크래프톤 정글 특제 햄버거입니다.

Week02 퀴즈 오답노트해시 충돌이란 무엇이며 그것이 발생하는 원인과 해결하기 위한 다양한 방법들 중, 체이닝을 설명하세요.해시 충돌: 두 개 이상의 아이템이 동일한 저장공간에 지정되는 현상입니다.이는 해시 함수의 특정상 제한된 크기의 해시 테이블에 무한한 수의 가능한 키들을 매핑해야 하기 때문에 발생합니다. 즉, 다양한 키들이 동일한 해시 값을 가질 수 있기 때문에 충돌이 발생합니다.체이닝: 각 버킷에 연결 리스트(linked list)를 사용하여 여러 키-값 쌍을 저장하는 방법입니다.체이닝 장점: 해시 테이블의 크기에 영향을 받지 않고, 일정한 성능을 유지할 수 있다.체이닝 단점: 연결 리스트를 위한 추가 메모리가 필요하다. 연결 리스트가 길어지면, 해시테이블의 값을 찾는데 시간이 많이 소요될 수 ..

글에 들어가기 앞서 설현아님 벨로그를 참조해서 작성하였습니다. 디테일한 내용(코드)은 해당 벨로그를 참조해주세요!(내용 공유해주심에 감사드립니다) https://velog.io/@sha0209/%ED%95%B4%EC%8B%9C%EB%B2%95hashing%EA%B3%BC-%EC%B6%A9%EB%8F%8C-%EB%8C%80%EC%B2%98-%EB%B0%A9%EB%B2%95해시법해시법을 사용하면 문지열, 리스트, 클래스형 등 정수가 아닌 값을 저장할 때에도 결국에는 정수 형태로 변환(해시값)되어 저장된다. 키(key)와 값(value)의 쌍으로 데이터를 저장하며, 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구할 수 있다.→ 기대할 수 있는 효과추가와 삭제를 효율적으로 수행 가능충돌이 없다면 O(1) 시..

링크드 리스트링크드 리스트는 동적할당이 유용하고, 삽입/삭제가 유용합니다.(일반적인 리스트에서의 밀리는 시간을 고려하지 않음) 그러나 탐색시간이 오래 걸린다는 단점이 있습니다.구조노드: 데이터와 하나 이상의 링크로 이루어 진다. 링크를 위한 추가 공간이 필요.헤드포인터: 헤드 노드만 알면, 링크로 연결된 모든 노드에 순차적으로 접근 가능.(헤드노드 전)헤드 노드: 연결 리스트의 시작 노드헤드 포인터: 머리 노드의 주소를 저장하는 가장 중요한 변수꼬리 노드: 마지막 노드, 꼬리 노드의 링크를 처리하는 방식에 따라 단순 연결과 원형 연결로 구분종류단순 연결 리스트: 하나의 방향으로만 연결된 리스트. 노드는 하나의 링크만 가지며 꼬리 노드에는 마지막 노드라는 None을 가진다.원형 연결 리스트: 꼬리 노드의 ..

오늘은 Week 2의 시험과 새로운 발제가 나오는 날입니다. 그렇기 때문에 9시 와서 코드들을 복습하고, 10시에 시험을 치뤘습니다. 이후 서로의 코드를 보고 리뷰를 하며 식사하고 돌아와 코치님의 발제를 들었습니다.오늘의 일정13:00 ~새로운 3주차 발제가 있다.코치님이 하실 말씀은…좀더 깊게 이해해야합니다. 문제 푸는 것보다 개념을 깊게 파야만 할 것 같습니다…특히나 다음주차 그래프는 개념이 굉장히 중요합니다.오늘 이번주와 저번주 키워드들을 공부하는 것이 다음주 공부에 도움이 될 것이므로 저번주차 내용을 복습하고 이번주차에 들어가시면 좋겠습니다.14:00 ~ 15:00운영진 티타임. 다양한 이야기를 했고, 저는 문제를 더 푸는가 일찍 퇴근해서 컨디션을 유지해야하는가? 에 대해 의문점이 있어 질문 했습..

시험 전날이다보니 여러 문제들을 풀었고, Week 02에서 못풀었던 문제 3개가 있는데, 코드까진 올려두겠다.이해는 다음에 해보겠다.9:40 ~아침에 일어났는데, 목이 너무 아팟다. 요즘 감기가 유행이라 걸린것 같다. 목조심하고 따듯한 물 많이 마셔야겠다.이번주 백준문제는 한바퀴를 돌았다. 어려웠던 문제 8문제를 박차를 가하여 풀고, 못봤던 개념을 재정리하겠다. 복습까지!!9번 (6549) 히스토그램에서 가장 큰 직사각형해당문제는 히스토그램에서 높이가 같은 도표를 묶어서 제일 큰 넓이를 찾는 것이 목표이다. 스택을 쌓아서 같은 층인 값의 연속을 찾아서 높이와 너비를 곱해 찾으면 좀더 수월하다고 한다.import sys# 여러 줄 입력을 처리하기 위해 while 루프 사용def largest_rectang..

1.5 캐시가 중요하다오버헤드: 프로그램을 돌리기 위해 필요한 여러 복사과정이 프로그램의 “실제 작업”을 느리게 하는 것이다.이러한 복사과정을 가능한 빠르게 동작하도록하기 위해 고안된 것이 캐시이다.일반적인 레지스터 파일은 수백 바이트의 정보를 저장하는 반면, 메인 메모리의 경우는 십 억개의 바이트를 저장한다. 그러나 프로세서는 레지스터 파일의 데이터를 읽는 데 메모리의 경우보다 거의 100배 더 빨리 읽을 수 있다.메인 메모리를 더 빠르게 동작하도록 만드는 것보다 프로세서를 더 빨리 동작하도록 만드는 것이 더 쉽고 비용이 적게 든다고 한다.이러한 극간을 줄이기 위해 시스템 설계자가 작고 빠른 캐시 메모리라고 부르는 저장장치를 고안하여 프로세서가 단기간에 필요로 할 가능성 높은 정보를 임시로 저장할 목적..

힙 정렬힙은 부모의 값이 자식의 값보다 항상 크다라는 조건을 만족하는 완전 이진 트리입니다. 대소 관계가 일정하다고 볼 수 있습니다. (부모의 값 ≥ 자식의 값)파이썬에서 힙 정렬은 heap모듈 함수를 통해 쉽게 구현가능합니다. 파이썬의 힙 정렬 함수는 다음과 같습니다.heappush(heap, data): 힙에 새로운 데이터를 삽입한다.heappop(heap): 힙에서 루트 노드(최소값)를 꺼낸 후 삭제한다.heapify(x): 주어진 배열을 힙 구조로 변환한다.→ 원래 힙정렬이 기본은 최솟값 정렬이다. 그러므로 최댓값을 구할때에는 -을 사용하여 최댓값 정렬로 바꾸어서 풀고 나중에 -를 다시 붙여 원래값으로 되돌려야한다.힙의 루트는 최댓값일때, 힙 정렬을 완료하는 과정을 보여드리겠습니다.https://..