일반적인 이진 트리에서, 많은 노드들이 자식 노드를 하나만 가지거나 전혀 가지지 않는 경우가 많습니다. 이진 트리의 많은 부분에 빈 공간이 생기며, 트리를 순회 (recursion)할 때 이 빈 공간을 효율적으로 사용하지 못하는 문제가 있습니다. 스택 없이 이진트리의 연산을 구현하는데에 2가지 방법이 있습니다.1. node 객체에 부모를 가리키는 레퍼런스 필드를 추가로 선언하고 순회2. 노드의 null 레퍼런스 사용 = 스레드 이진 트리스레드 이진 트리(Threaded Binary Tree)는 이러한 문제를 해결하기 위해 고안된 자료구조입니다. 스레드 이진 트리는 트리의 노드들이 자식 노드가 없는 경우, 그 노드의 포인터를 다른 유용한 노드에 연결하여 메모리 공간을 효율적으로 사용합니다. 이 연..

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 ..

이진 탐색 = UpDown 게임 순차 탐색은 처음부터 끝까지 보면서 탐색하므로 O(N)의 시간이 걸림. 이진 탐색은 배열을 절반으로 계속해서 나누어 mid값이 목표값이 될 때까지 나누게 됨. O(logN)의 시간이 소요됨 다만, 이진 탐색은 이미 정렬되어있는 배열에서 탐색해야한다. 그렇지 않으면 정상적으로 동작하지 않음. 이진탐색 구현 - python으로 구현하였다. def BinarySearch (arr,target): left = 0 right = len(arr)-1 while(True): mid = (left+right)//2 if(arr[mid] == target): return mid elif(arr[mid] < target): left = mid+1 else: right = mid-1 targ..

1. 전체 값 중 가장 작은 값을 찾음 2. 해당 값을 맨 첫번째에 배치함 3. 첫번째 값을 제외하고 가장 작은 값을 찾아 두번째에 배치함 4. 두번째, 세번째, ... n-1번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치함. ✨선택정렬의 시간 복잡도 버블 정렬 : 중간에 정렬이 완료된 것이 확인되면 정지 선택 정렬 : 반드시 n-1,n-2,...,2,1 번의 비교 연산을 수행해야함. 약 n*(n-1)/2번의 연산을 필요로 함 = O(N^2) ✨선택정렬의 구현 python으로 구현해보겠다. def selection_sort(arr): length = len(arr) for i in range(length-1): minindex = i for j in range(i+1,length): if a..

for문이 1억번 도는데 1초정도의 시간이 소요됨 - 제한 시간이 1초인 문제를 풀 때 대략 1억 이하의 시간복잡도를 보이는 솔루션이면 통과 가능하다 N

프로세스 속성과 제어 (Process description, control) 프로세스에 대해 알아보겠다. 프로세스란? 프로그램이 실행상태에 있는 것 프로그램을 더블클릭 했을 때 실행되는 것 사람이 프로세스를 만들 수 있음 사람 말고도 프로세스가 프로세스를 만들 수 있음 ( 부모, 자식) 현재 상태 프로세스는 누가 만들까? 인간이 만든다 : 인간이 프로그램 실행시 (GUI, cmd) 프로세스가 만든다 : 시스테 프로세스를 작동할 때, user process Process의 3요소 Executable program Data used in program Execution context of th eprogram process의 상태 Process States Model running 상태 (프로세스 실행중) ..

OS Application program의 실행을 제어하는 소프트웨어 Program과 hardware사이의 인터페이스 효율성과 편의성이 목적 OS가 제공하는 서비스 프로그램의 실행 Serial Processing (Operation by human) 범용 컴퓨터 Scheduling 이 없음 Simple batch system : monitor - 운영체제의 초창기 모습 모니터가 여러개의 프로그램을 일괄적으로 제어 Uni-programming CPU가 run하다가 wait함 실행 - 입력 → 실행 → 출력 Time sharing 과 멀티 프로그래밍의 throughput이 똑같은거 아니냐? 아니다. Timesharing할 때 중간중간 비는 시간 생김

🤔 Segmentation이란? - Image segmentaion : 이미지를 비슷한 정보를 가진 단위로 나눈 것 더보기 💡 클래식한 접근이다. 1. Point clustering : 비슷한 종류끼리 묶음 2. Image segmentation 3. Semantic segmentation : 이미지 내의 의미있는 클래스들끼리 분할 4. Video object segmentation : 움직이는 사진, 영상(비디오)의 의미있는 객체,object만을 분할 - segmentation method의 방법 🤔Image thresholding 이란? Single threshold 픽셀의 grayLevel > T 이면 하얗다 픽셀의 grayLevel 많이 쓸수록 복잡해진다. T1과 T2사이에 픽셀이 존재할 경우 w..

각 프로세스는 하나의 프로세스 그룹에 속한다 기본적으로 자식은 부모와 같은 그룹에 속한다 쉘은 각 job마다 별도의 프로세스 그룹을 만든다 양수 프로세스 그룹 ID로 식별함 (process group ID) 시그널 처리할 때 프로세스 그룹 관리하는 이유 : job으로 먼저 등록 , 한줄에 여러개의 명령어 침 한 줄에 들어오는 모든 명령어 = 하나의 job → 자식을 만들면 groupID같다 foreground job은 키보드 작업 수행 가능 ctrl c background 는 키보드 불가 ctrl c안먹음 💡 getpgrp() : 프로세스의 프로세스 그룹을 리턴 💡 setpgid() : 프로세스의 그룹을 변경 (성공하면 0, 실패 시 -1) 🧐kill → 시그널 보내기 /bin/kill : 프로세스 또는..