본문 바로가기

전체 글227

[알고리즘] ep3++) AVL 트리 구현 AVL 트리 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료  주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식 중 하나.. 2024. 7. 17.
[알고리즘] ep3+) 이진탐색트리(BST) 구현 BST(이진탐색트리) 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료  주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식.. 2024. 7. 17.
(주)포트래이 데이터 라벨링 프리랜서 후기 포트래이(portrai)라는 AI 의료 기반 스타트업에서 데이터 라벨링 관련 프리랜서 계약을 맺게 되었다계약기간은 총 1년이며 출근과 업무 방식은 매우 자유로웠다포트래이는 종로구에 위치한 바이오 스타트업이며  서울대 의대 출신의 대표와 그 동문인 교수들이 공동 창업한 회사이다 사실 포트래이와의 연은 이전부터 있었다, 이전에 포트래이 로고 효과음을 외주 받은 적이 있었고 이후에 좋은 기회로 또 프리랜서 계약을 맺게 되었다회사는 나에 대한 배려를 많이 해주었다, 학생 신분인 나였기에 학기 중에는 많은 여유가 없을 것을 참작해 주고 그것을 반영해 주었다내 자리는 연구소 안 대표님 바로 뒷자리에 위치하였으며 윈도우 컴퓨터라 맥북을 사용하는 난 되게 오랜만인 반가운 느낌이 들었다 데이터 라벨링과 관련한 업무는 비.. 2024. 7. 13.
[알고리즘] ep3) 탐색트리 ㅇ이진탐색트리(BST, Binary Search Tree): 노드의 왼쪽 가지에는 노드보다 작은 값들만 있고, 노드의 오른쪽 가지에는 노드보다 큰 값들만 있도록 구성 내부노드에 (key, value)쌍을 저장하며 그림으로는 간단히 노드에 key만 표시한다(왼쪽 및 오른쪽 부트리 또한 각각 이진탐색트리이다) // 재귀버전int binarySearch(int* arr, int lowIdx, int highIdx, int key) { if (lowIdx > highIdx) { if (highIdx key) { // 중간값이 키값보다 큰 경우, 왼쪽 절반을 탐색 return binarySearch(arr, lowIdx, midIdx - 1, key); } else if (a.. 2024. 7. 11.
[알고리즘] ep2) 사전(dictionary) ㅇ사전(dictionary) ADT: 탐색 가능한 형태의 (key, value)쌍 항목들의 모음을 모델링주로 해시 테이블(hash table)과 이진 검색 트리(BST)로 구현하며, 이때 각 키는 유일해야 한다 -> 유일키 - 직접응용: 연락처, 카드 사용승인, 인터넷주소 맵핑 e.g. www.sejong.ac.kr을 128.148.34.101로 맵핑 - 간접응용: 알고리즘 구현, 자료구조 구현  유일키(unique key): 한 개의 키에 대해 하나의 데이터만 존재e.g. 학번, 계좌, ID중복키(duplicate key): 한 개의 키에 대해 여러 개의 데이터가 존재e.g. 이름, 나이, 계좌개설일자  [두 종류의 사전]- 무순사전 ADT- 순서사전 ADT [사전 구현에 따른 탐색 기법]    "컴퓨.. 2024. 7. 11.
[알고리즘] ep1-6+) 퀵정렬의 다양한 버전 (출력형식)Limit         결정적1           결정적3              무작위1           무작위31        X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 100    X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 500   X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 1000  X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX(참고: X.XXXXXXXX는 측정된 cputime in milliseconds).   [주요 함수들의 설계 가이드라인]global integer n = 100000global array Limits = {1, 100, .. 2024. 7. 10.
[알고리즘] ep1-4+) O(n + klog(n))의 힙정렬 문제: 중복이 있을 수 있는 n개의 정수들로 이루어진 무순리스트 L을 구축 후, k번째 작은 원소를 O(n + klog(n)) 시간에 찾아 인쇄하라  프로그램 요구사항:findKthSmallest(L, n, k)중복이 있을 수 있는 n개 정수 원소들로 이루어진 리스트 L의 원소 가운데 k-번째로 작은 원소를 찾아내 반환한다.buildList(n, min, max)난수함수를 이용하여 min ~ max 사이의 중복이 있을 수 있는 정수 n개의 무작위, 무순리스트를 만들어 반환한다.리스트는 1D 배열 또는 단일연결리스트 가운데 하나를 자유롭게 선택하여 구현한다.main()buildList(10, 1, 100)을 호출하여 1과 100 사이의 정수 10개로 이루어진 리스트를 만들어 L에 저장한다.정수들 사이를 공.. 2024. 7. 10.
[알고리즘] 정렬 알고리즘 선택 매뉴얼 ㅇ버블정렬 - 실무에서는 아예 사용하면 안된다"제자리 + stable" O(n^2)   ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)"제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합   ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)"제자리 + stable" O(n^2): 느리다 - 소규모 입력에 적합  ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ  ㅇ힙정렬: 우선순위 큐 (힙으로 구현)"제자리 + unstable" O(nlog(n)): 빠르다 - 대규모 입력에 적합   ㅇ병합정렬: 분할통치"제자리 X + stable" O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합   ㅇ퀵정렬: 분할통치"제자리 + unstable".. 2024. 7. 7.
[운영체제] 후기 운영체제에 대한 정리를 끝마치게 되었다처음 운영체제에 대한 큰 틀을 잡을 때는 혼공컴운(강민철) 책을 사용해서 기반을 다졌고, 이후 나머지 심화적인 내용은 박태순교수님의 Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham) 책으로 공부했다. 컴퓨터공학과 박태순교수님의 운영체제 강의는 세종대 대표 명강의로 유명하다 수강신청이 굉장히 치열해 과연 잡을 수 있을까 했지만 1순위 우선순위를 갖고 재빠르게 신청하니 다행히 운 좋게도 쟁취할 수 있었다 학습 분위기는 학생들 수준도 굉장히 높고 치열했다 컴퓨터공학과와 컴퓨터공학과를 복수전공하는 학생들 중 열의 .. 2024. 7. 7.

티스토리툴바