TIL

알고리즘 문제를 쭈~욱 풀어보며 공부했다. 백준 9020-골드바흐의 추 측 문제를 풀면서 시간 초과를 만났고, 내 코드에 적용하여 시간복잡도를 개선할 수 있었던 방법 두가지를 메모하려 한다. 추후 코딩 테스트에도 쓰일 수 있는 내용이라고 하니 기억해두면 좋을 듯 😄고

이틀간 재귀함수에 대한 문제들을 몇 가지 풀며 느꼈던 점들을 가볍게 메모해보자. 재귀 너무 어렵다 ... 😂재귀 개념의 가장 기본적인 문제라고 할 수 있지만, 막상 아무것도 보지 않고 팩토리얼을 재귀로 구현해라! 라고 하니 생각보다 오래 걸렸었다. 덕분에 관련 책을

각 정렬 알고리즘의 시간, 공간 복잡도 표내가 구현해 본 삽입 정렬배열의 각 요소마다, 리스트 처음까지 돌아오며 알맞은 자리를 찾아 삽입(insert)해주는 방식. 이미 어느정도 정렬된 데이터를 재정렬할 때 빠르며, 안정한 정렬 방법이다. 또한, 동작이 간단하다.하지만

파이썬의 리스트 객체 함수로, 리스트에만 사용할 수 있다.sort(\*, key=None, reverse=False)파이썬의 내장 함수로, 리스트를 포함한 iterable에 모두 사용 가능(dict, set, str...)sorted(iterable, /, \*, ke

배열에서 검색하는 방법 중 가장 기본적인 알고리즘순차 검색(Sequential Search)라고도 함원하는 값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 검색하는 방법검색할 값을 찾지 못하고 배열의 맨 끝을 지나면 검색 실패, 원소를 찾으면 성공매 반복시마다 선형

이진 검색 정렬된 배열에 한해서 사용 가능한 검색 알고리즘 매 반복시마다 배열의 가운데 원소와 key값과의 비교를 통해 범위를 절반씩 줄여나간다. 시간복잡도가 O(n)인 선형 검색보다 좋다. O(logn)

str.encode(encoding='utf-8', errors='strict')인코딩 방식과 에러 처리 방식을 전달해 줄 수 있음기본값은 가장 보편적인 인코딩 'UTF-8'유니코드 기반 인코딩 방식압도적인 호환성과 하위 방식이 따로 없는 단일 인코딩 방식이라는 장점

데이터를 임시 저장하기 위한 자료구조후입선출(LIFO: Last In First Out)데이터를 넣는 작업은 push, 빼는 작업은 pop푸시와 팝이 이루어지는 꼭대기는 top, 아랫부분은 bottom스택과 동일하게 데이터를 임시 저장하기 위한 자료구조선입선출(FIFO

힙 '부모의 값이 자식의 값보다 항상 크다 or 작다'를 만족하는 완전 이진 트리 자료구조 힙 정렬 '힙에서 최댓값 or 최소값은 루트(최상위 노드)에 위치한다' 라는 특징을 이용하여 정렬하는 알고리즘 아래의 과정을 반복하여 정렬 힙에서 최댓값인 루트를 꺼낸다. (

우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현을 제공하는 모듈. 파이썬 공식 문서를 참조해 자주 쓸 법한 부분을 추려봤다.heapq.heappush(heap, item)힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.heapq.hea

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘다음과 같은 조건일 때 사용해봄직 하다.큰 문제와 쪼개진 문제가 동일하거나 비슷한 형태를 띌 때쪼개진 문제들간의 상관관계가 없을 때(서로 영향 X)당연하게도 잘게 쪼개 해결함으로서 어려

그래프 탐색 알고리즘으로, 그래프의 노드들을 탐색하는 방법 중 하나다른 그래프 탐색 알고리즘으로는 대표적으로 BFS(Breadth-First Search, 너비 우선 탐색)가 있다.DFS는 시작 노드에서 한 방향으로 가능한 멀리까지 탐색한 후, 더 이상 진행할 수 없을

힙은 여타 자료구조와 다른 부분이 많은 특이한 녀석이다. 힙의 특징들은 때에 따라 강력하게 작용할 수 있는데, 그러한 부분을 정리해보았다.최상위 노드인 루트가 힙의 최대 or 최소 -> O(1)의 시간복잡도로 최대/최소값 찾아내기 가능추가적인 노드의 삽입, 삭제를 O(

그래프 객체들 간의 관계를 표현하는데 사용되는 추상적인 자료구조

특정한 특성을 가지는 그래프의 일종으로서, 그 자체로 독립된 자료구조로 쓰인다.트리의 대표적인 특성들은 다음과 같다.사이클이 없음 (Cycle-Free): 트리는 사이클이 존재하지 않는 그래프입니다. 즉, 두 노드를 잇는 경로가 유일하며, 자기 자신으로의 순환 경로가

대표적인 트리 순회 방법들인 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)에 대해 정리해보자.트리를 루트 방문 -> 왼쪽 자식 -> 오른쪽 자식 순서로 순회하는 방법.다음과

최소 신장 트리(MST: Minimal Spanning Tree) 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리 도로망 설계, 전기 회로 설계, 네트워크 연결, 센서 네트워크 설치 등에서 최소 비용으로 모든 노드를 연결하고

그래프에서 출발점부터 목적지까지의 최단 경로를 찾는 알고리즘 중 하나각 간선의 가중치가 음수가 아닌 경우에 사용(이 경우엔 벨만-포드와 같은 다른 알고리즘 사용)다익스트라 알고리즘은 다음 절차를 통해 구현출발점에서부터의 최단 경로를 저장할 배열 (혹은 우선순위 큐)를

포인터 기초 C언어에서 포인터는 다음과 같이 정의할 수 있다.(포인터에 주소값이 저장되는 데이터의 형) \*(포인터의 이름);예를 들어 p 라는 포인터가 int 데이터를 가리키고 싶다고 하면,라고 하면 올바르게 된다. 즉, 포인터 p 는 int 형 데이터의 주소값을

RB트리(Red-Black Tree)는 이진 탐색 트리(BST)의 일종으로서, BST의 worst case의 단점을 개선한 자료구조이다.복잡한 자료구조이지만, 실 사용에서 효과적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을 때 O

삽입 전 RB 트리의 속성을 만족한 상태여야 한다.삽입 방식은 일반적인 BST(이진탐색트리)와 동일하다.삽입할 노드의 색은 항상 RED다. (삽입 후에도 5번 속성을 만족하기 위해서!)알맞은 자리에 노드 삽입 이후, RB 트리 속성 여부를 확인한다.RB 트리 속성을 위

삽입 전 RB 트리의 속성을 만족한 상태여야 한다.삭제 방식은 일반적인 BST(이진탐색트리)와 동일하다.원하는 노드 삭제 이후, 삭제되는 색을 통해 RB 트리 속성 위반 여부를 확인한다.RB 트리 속성을 위반했다면 트리를 재조정(delete-fixup)한다. RB 트리

나같은 입문자에게 C의 포인터는 단순히 개념적으로도 충분히 높은 벽이었지만, 실제로 내 코드에서 포인터를 사용해보는 것은 그보다 한차원 너머의 어려움이었다. 산넘어 산이라고 해야할듯 😂처음에는 포인터의 간편함에 놀랐다. 각각의 포인터는 메모리 주소들을 가리킬 뿐이지만

Malloc Lab을 Implicit List로 구현한 후 받은 첫 점수는 53점! 더 높은 점수를 위해서는 만든 동적 메모리 할당기의 성능을 다양한 방법으로 끌어올려야 했다. Malloc Lab에서의 동적 메모리 할당기의 성능은 두 가지로 평가된다. Space Uti

개념은 쉽고, 구현은 어려워 🎵 나만의 동적 메모리 할당기의 성능을 더더욱 높이기 위해, Explicit Free List를 이용한 구현에 대해 공부했다. Implicit Free List를 사용한 할당기는 간단하게 구현할 수 있지만 블록의 할당에 소모되는 시간이 힙

에코 서버를 구현해보자!

귀여운 우리집 고양이 영상을 보여주는 페이지!! GET 요청을 보내서 두 수를 더해주는 기능도 있다.Tiny를 확장하여 동영상 파일을 처리할 수 있도록 한다. 실제 브라우저를 통해 결과를 체크하시오.서버의 디렉토리에 동영상 파일을 넣어주고, 간단한 video 태그를 추

네트워크란? 🕸️ network: 상호 연결되어 있는 것으로 이루어진 그룹이나 시스템. 상호 연결되어 있는 것을 점, 그들간의 관계를 선으로 표시한 것 Ex) 뉴런과 시냅스(neural network), 사람과 친분관계(social network) 등등.. 내가

기존의 코드에서는, 요청을 받은 후 일정 시간이 지나면 무한루프에 들어가며 동작을 멈추는 문제가 있었다.일반적으로 HTTP 에서는 클라이언트가 요청을 보내면 서버는 응답을 보내고 연결을 종료한다. 이 때 연결이 제대로 끊어지지 않았다면 서버는 계속하여 클라이언트에게서

처음 만난 Pintos 대망의 Pintos 대장정의 막이 올랐다. 처음 만난 Pintos는 그야말로 높디높은 벽 그 자체. 지금껏 정글에서 만난 적 없는 거대한 분량의 코드의 양에 압도되었다. 코드들이 어떤 식으로 구성되어 있나 알아볼 틈도 없이, Pintos의 첫 과

이것이 정글의 꽃이다 🌺 첫 과제인 Alarm Clock 을 성공적으로 처리하고, 본격적으로 PintOS의 스케줄링에 딥다이브할 시간이 왔다. 기존의 바보같던 스케줄러를 뚝딱뚝딱 고쳐 똑똑하게 만드는 과정은 너무나 어려웠고, 또 즐거웠다! PintOS 주차가 지옥주라

thread_block() : Running Thread -> Blocked Threadthread_unblock() : Blocked Thread -> Ready Threadthread_yield() : Running Thread -> Ready Threadsched

더, 더 아래로 👇 첫 번째 프로젝트 까지는 모든 작업을 커널 위에서 진행했지만, 이제부턴 유저 레벨에서의 동작을 처리한다. 본격적으로 'OS스러운 기능' 을 구현해보는 시간! 첫 과제는 파일 실행을 위한 작업을 직접 구현해보는 Argument Passing 이다.

PintOS의 두번째 지옥 탈출 🔱 매주 점점 더 힘들어지는 PintOS 의 두번째 프로젝트를 마무리했다. 모든 테스트를 통과한 유일한 팀이 되는 엄청난 경험을 하기도, 정글 입소 후 가장 큰 벽을 만나기도 했던 Project 2 였다. 눈 코 뜰 새 없이 바빠서

한창 PintOS 의 세 번째 프로젝트에 열을 올리고 있던 중, 우리반 단체 톡방에 어떤 형님이 올려주신 블로그 글의 제목이다. 제목에서 알 수 있듯 PintOS 에게 두드려 맞은 또다른 희생자님이 쓰신 글이었는데, 제목을 보면 알 수 있듯 PintOS 의 장점으로 시

PintOS 의 세 번째 프로젝트, 가상 메모리 주차가 공식적으로 종료되었다. 벌써 PintOS 와 함께한지 한 달이 채 넘어간다. 이젠 정말 미운 정 고운 정 다 들어버린듯?프로젝트 3에선 어떤 것을 배웠고, 어떤 문제점을 만났었는지 정리해보자.PintOS 는 우리가

기술 면접을 진행하다, 호이스팅에 대한 질문을 받았다.호이스팅이 어떠한 현상이며, 이로 인해 예상치 못한 에러가 발생할 수 있다는 점,또한 var 을 통한 변수 선언이 아닌 let, const 을 통해 선언 시 이를 피할 수 있다는 점에 대해 집중적으로 설명드렸다.대답