Weekly
-
[Pintos-KAIST] Project 2 :: System Calls - 2 (exec, wait, fork), Deny Write on Executables
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory 1. exec 1-1. exec 요구사항 현재 프로세스를 cmd_line에 주어진 실행 파일로 변경하고, 필요한 인수를 전달합니다. 이 함수는 성공한 경우 반환하지 않습니다. 프로그램이 로드되거나 실행될 수 없는 경우 종료 상태 -1로 프로세스가 종료됩니다. 이 함수는 exec를 호출한 스레드의 이름을 변경하지 않습니다. 파일 ..
-
[Pintos-KAIST] Project 2 :: Argument Passing (User 프로그램 인자 설정하기)
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory Argument passing user 프로그램이 실행되기 전에 프로그램에 대한 인자를 설정해야 한다. 👇🏻 인자를 어떻게 처리해야 하는지 예시를 통해 먼저 알아보자! 예시) "/bin/ls -l foo bar"의 인자 처리하기 명령어를 단어로 분할한다: /bin/ls, -l, foo, bar 각 문자열과 널 포인터를 스택에 오..
-
[Pintos-KAIST] Project 2 :: System Calls - 3 (File System), User Memory
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory User Memory Access system call의 일환으로, 커널은 종종 사용자 프로그램이 제공한 포인터를 통해 메모리에 접근해야 합니다. 그러나 사용자는 1) null 포인터, 2) 매핑되지 않은 가상 메모리를 가리키는 포인터 또는 3) 커널 가상 주소 공간(KERN_BASE 이상)을 전달할 수 있으므로, 커널은 이를 ..
-
[Pintos-KAIST] Project 2 :: System Calls - 1 (System Calls이 호출되는 과정)
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory Pintos 프로젝트 2 과제로 시스템콜을 구현했다. 1.5주동안 열씸히 구현한💦 유저 프로그램을 실행시키고 시스템콜을 호출하는 그 과정이 어떻게 이루어지는지 알아보자! system call을 호출하는 open-normal 테스트 파일이 실행되는 데까지 어떤 과정을 거치게 될까?? open-normal 👇🏻 System call..
-
[Pintos-KAIST] Project 1 :: Alarm Clock (Sleep-Awake 방식의 Alarm Clock 구현하기)
Alarm Clock 💡 스레드를 잠시 재웠다가 일정 시간이 지나면 깨우는 기능인 Alarm Clock을 Busy-waiting 방식에서 Sleep-Awake 방식으로 변경하자! 1) Busy-waiting과 Sleep-Awake의 차이 Busy waiting은 특정 조건이 매우 빠르게 충족될 것으로 예상될 때 사용되는 것이 적합하며, Alarm clock은 일정 시간 이후에 수행해야 하는 작업이 있을 때 사용된다. Busy waiting 프로그램이 다른 작업을 수행하며 기다리는 대신, 특정 조건이 충족될 때까지 반복적으로 체크를 하면서 기다리는 것을 말한다. 이러한 방식은 CPU 자원을 낭비하고, 다른 스레드가 실행되는 기회를 줄여 성능 저하를 야기할 수 있다. Alarm Clock 프로그램이 일정 시..
-
[c언어] Red-Black Tree 구현하기
🫶 Notion에서 보기 🫶 Red-Black Tree 🔎 Red-Black Tree란? www.notion.so 🔎 Red-Black Tree란? self-balancing binary search tree의 일종이다. 각 노드 당 한 비트의 추가 기억 공간을 가지는데, 이 비트는 노드의 색상 정보를 빨간색 또는 검은색으로 저장한다. 루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하게 되어 근사적으로 균형을 이룬 트리가 된다. 트리를 self-balancing 하게 만들어주어 검색, 삽입, 삭제 연산을 모두 O(log n)의 시간 복잡도를 보장하며, 이진 탐색 트리와 달리 최악의 경우에도 균형이 깨지지 않도록 보장한다. 🚨 ..
-
[React] useFormState, useFormStatus
form 액션의 결과에 기반하여 상태를 업데이트할 수 있게 해주는 Hook 마지막 양식 제출의 status 정보를 제공하는 Hook 📄 Docs 🔗 useFormState 🔗 useFormStatus useFormState 💡 현재는 Canary와 experimental channel에서만 사용할 수 있다. 💡 useFormState을 사용하는 이점을 얻으려면, React 서버 컴포넌트를 지원하는 프레임워크에서 사용해야 한다. form 액션의 결과에 기반하여 상태를 업데이트할 수 있게 해주는 Hook이다. const [state, formAction] = useFormState(fn, initialState, permalink?); 1. Reference useFormState(action, initia..
-
[Pintos-KAIST] Project 3 :: Memory Management
Pintos Project 3의 첫번째 과제인 Memory Management에서는 supplemental page table을 먼저 다루고, Physical Memory와의 매핑하는 함수를 구현한다. Implement Supplemental Page Table 현재 상태에서 Pintos는 가상 및 물리적 메모리 매핑을 관리하기 위한 페이지 테이블(pml4)을 가지고 있다. pml4 이외에 추가로, page fault 및 리소스 관리를 처리하기 위해 supplementary page table이 필요하다. 💡 Implement supplemental page table management functions in vm/vm.c. 0) supplemental page table hash table을 이용해서..
Best
-
[KAIST 정글] 나만무 프로젝트 회고 (2) :: 씽잉러너 만들기
초안 발표에서 탈탈 털린 우리 팀은 기획을 전반 수정해야 했다. 그렇게 나온 아이디어가 이름도 장황한 캐주얼 노래 배틀 게임 ㅋㅋ 캐주얼은 왜 붙인 건지 아직도 모르겠음 노래를 부르면 실시간으로 채점을 해주고 동시에 다른 친구와 대결을 할 수 있는 게임이다. 노래만 부르면 아쉬우니까 여기에 아이템으로 공격을 할 수 있고 방어 아이템을 쓰거나 특정 행동으로 공격을 회피할 수도 있다. 처음에는 내가 엄청 반대했다. 이유는 '난 이걸 만들 수 없어..' 웹만 만들어봤는데, 게임을 만드는 건 상상도 못 해봤고 어떻게 해야 하는 건지 도무지 감이 잡히지 않았다. 그래픽 관련 기술을 새로 배워서 하기엔 시간이 너무 촉박할 것 같고, 이 프로젝트에서 잘할 수 있는 걸 하고 싶었지 겨우겨우 해내는 걸 하고 싶지 않았다..
-
[KAIST 정글] 나만무 프로젝트 회고 (1) :: 팀 형성, 초안 발표
너무너무 늦었지만 이제라도 작성하는 나만의 무기를 갖기 회고 Start~! 지금은 나만무 최종 발표(7/8)가 끝난 지 3개월이나 지났다 ㅎㅎ 우선 나만무에 대한 나의 생각부터 기록해 보자면.. 부트캠프를 하고 남는 것은 프로젝트뿐이라고 생각하였고, 나에겐 무려 세 번째 부트캠프인 만큼 굉장한 프로젝트를 해내야 하고 해낼 수 있을 것이라는 자신감이 가득했다. 리더 지원 당연하게도 리더에 지원했다. 지원한 이유는 프로젝트 경험이 있다. 원래 나서는 거 좋아함. 답답할 바에 내가 뛸래 ! 앞으로 사회에 나가면 리더가 되기까지 몇 년은 더 기다려야 한다. 내가 스스로 리더가 될 수 있는 마지막 기회니까 애초에 크래프톤에서 발표하는 영상 보고 반해서 나도 하고싶어서 정글 지원했음 취업에도 당연히 도움이 될 것 ..
-
[c언어] Malloc Lab :: 동적 할당기 구현하기 (Implicit List, Explicit List, Segregated List, Buddy System)
🔎 Malloc Lab Carnegie Mellon University의 Malloc Lab 과제 C 프로그램을 위한 malloc, free 및 realloc 루틴의 버전을 직접 작성하는 과제이다. 주어진 파일을 초기 상태에서 테스트를 해보면 아래와 같이 out of memory 에러가 발생한다. implicit list 방식대로 malloc을 구현해서 이 out of memory 에러를 없애는 과제이다. 추가적으로 explicit list와 seglist 등을 활용해서 점수를 높일 수 있다. dynamic storage allocator는 네 가지 기능으로 구성된다. 이 함수들은 mm.h에 선언되어 있고, mm.c에서 정의한다. int mm_init(void); // 초기화 void *mm_malloc..
-
[c언어] Proxy Lab :: Proxy Server 구현하기 (Sequential proxy, Concurrent proxy, Caching)
🔎 Proxy Lab 🖥 Github에서 전체 코드 보기 Carnegie Mellon University의 Proxy Lab 과제 Web Proxy는 웹 브라우저와 end server 사이에서 중간자 역할을 하는 프로그램이다. 웹 페이지를 가져오기 위해서 브라우저가 end server에 직접 연결하는 대신에, proxy server에 연결하여 요청을 전달할 수 있다. end server가 proxy server에 응답을 하면, proxy server가 응답을 브라우저에 전달한다. 🤔 Proxy의 역할 Firewall: 프록시는 방화벽 외부에 있는 브라우저가 종단 서버에 접근할 때 프록시를 통해서만 접근이 가능하게 만들어주는 중개자 역할을 할 수 있다. 👉🏻 이를 통해 내부 네트워크는 외부로부터 보호될 수..
-
[KAIST 정글] 8주차 회고
벌써 정글에 입소한 지 두 달이 지났다. 정글의 커리큘럼을 보니 딱 중간 단계에 와있다. 지금까지 정글에 와서 정말 많은 공부를 했다. 배운 것들을 머릿속에만 남겨놓기 아까우니 여기에 남겨놔야지~! 1 ~ 4주차 :: 컴퓨팅 사고로의 전환 첫 4주동안은 난생처음 들어보는 자료구조와 알고리즘을 배우면서 정말 많은 알고리즘 문제를 풀었다. 이 세상엔 다양한 알고리즘이 very many 존재한다는 것을 알게 되었고, 이걸 모르고 살았던 인생이 아까울 정도였다. 복잡한 문제를 코드 몇 줄로 뚝딱 간단한 문제로 바꿔버리는 것이 아주 매력적이다. 요즘은 특히 다익스트라에게 아주 빠져버렸다 ㅎㅎ dijkstra
-
[Pintos-KAIST] Project 4 :: 디스크의 파일 데이터 할당 방법
Pintos Project4에서는 FAT 방식으로 파일 데이터를 할당한다. FAT 방식은 파일이 할당된 블록의 위치 정보를 chain 형태로 관리하는 Linked Allocation 방식에 해당한다. 이외에도 파일 데이터를 할당하는 방식은 여러가지가 있다. Contiguous Allocation Linked Allocation Indexed Allocation 1. Contiguous Allocation 연속 할당 방식은 각 파일을 디스크의 연속적으로 이어지는 공간에 할당한다. 이 상황에서 중간에 있는 길이가 5인 주황색 파일이 삭제되어 공간이 비었을 때, 길이가 6인 노랑색 파일을 저장하려고 한다면, 실제 디스크의 공간이 6 이상 비어있음에도 불구하고, 연속된 공간이 아니기 때문에 할당할 수 없어 4 ..
-
[Pintos-KAIST] Project 3 :: Stack Growth (Pintos의 스택 확장 메커니즘)
Stack Growth Project 2까지 사용하던 스택은 USER_STACK을 시작으로 하는 단일 페이지였으며, 프로그램의 실행은 이 크기로 제한되어 있었다. Stack Growth를 구현하면 스택이 현재 크기를 초과하면 추가 페이지를 할당한다. 즉, 접근한 가상 주소에 매핑된 frame이 없어서 page fault가 발생한 경우 중에서 접근한 가상 주소가 Stack 영역 내에 존재할 경우에는 추가 페이지를 할당해 page fault를 해결해보자! 우선 접근한 주소가 Stack 영역 내에 존재하는지 판별해야 한다. 접근한 주소가 Stack 영역 내에 존재하는지 판별하기 page fault가 발생했을 때 접근한 주소가 stack 안에 있는지 판별하고, stack에 접근한 경우에는 stack growth..
-
[python] 백준 1074 :: Z
[Z] # 문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. # 입력 첫째 줄에 정수 N, r, c가 주어진다. # 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 풀이 전체 코드 N, r, c = map(int, input().split()) def recursive(n, row, col): if n == 0: return 0 cur_count = 2 * (row % 2) + ..
-
메모리 누수: Garbage Collection, 전역 변수, 브라우저에서 메모리 확인하기
메모리 누수 Garbage Collection 변수를 만들면 변수를 브라우저 메모리에 저장하고, 만든 변수들 중 필요 없는 것들은 모아뒀다가 한번에 지운다. 👉🏻 GC(Garbage Collector)가 Garbage Collection을 하는 것이다. JS나 Java 같은 대부분의 언어는 메모리를 자동으로 할당해주는데, C언어 등의 일부 언어는 메모리를 직접 할당하고 데이터를 저장해야 한다. JavaScript는 GC가 해주니까 따로 메모리 관리를 할 필요는 없지만, 잘못 알게되면 문제가 생길 수 있다. 컴퓨터가 똑똑하긴 하지만 신은 아니니까! 컴퓨터가 오해를 하게 코딩을 하게되면, Garbage Collection을 해도 깔끔하게 지워지지 않을 수 있다. 아래는 잘 지워지고 있는 상태이다. Garba..
-
Optimistic UI: 빠르게 할 수 없다면, 속여보자! ㅋㅋ
Optimistic UI 유저가 네트워크 응답을 기다려야 할 때, 예상 응답을 미리 표시해주어 지연을 숨기는 방법이다. 전제 조건 실패할 가능성이 낮고, 실패해도 문제가 없는 상황에 적용해야한다. 배제해야 하는 경우 여러 테이블에 데이터를 함께 저장하는 경우. 👉하나라도 실패하면 전체 API가 실패로 처리되기 때문에 실패 확률이 높기 때문 활용 예시: 좋아요 프로세스 일반적인 방식 브라우저에서 좋아요를 누르면 백엔드에 `좋아요 API`를 요청하고 DB에 접근해서 기존의 좋아요 수에 +1을 한다. DB에서 돌려받은 값을 백엔드를 거쳐 브라우저에서 받아서 화면에 보여준다. 👇🏻 Optimistic UI를 적용하면 ~ state에 좋아요의 값을 +1 해놓고 state를 화면에 먼저 보여준다. 실제 요청의 결과..
-
Memoization으로 성능 최적화하기 (memo, useMemo, useCallback)
state가 바뀌면 바뀐 state로 컴포넌트가 다시 만들어지는데, 불필요한 재렌더링은 성능에 악영향을 미친다. 컴포넌트가 어떻게 재생성되고, 다시 만들지 않게 하는 방법은 무엇인지 알아보자! memoization 새로 만들 컴포넌트를 메모해놓고, 다음에 다시 만들어야 할 때 새로 만들지 않고 메모해 놓은 것을 가져다 쓴다고 생각하면 된다. 재렌더링 시 새로 만들어지는 것들 컴포넌트 안의 hook을 제외한 나머지는 전부 새롭게 다시 만들어진다. 부모가 새로 만들어지면 자식들도 새로 만들어진다. 렌더링이 일어나면 hook을 제외한 모든것이 새로 만들어진다. 1. let과 state let으로 선언한 변수는 값이 바뀌어도 화면에 반영되지 않는다. 반면, state가 변경되면 렌더링이 일어나고 화면에 반영된다..
-
[python] 백준 21606 :: 아침 산책 (DFS)
[아침 산책] # 문제 아침 산책을 즐기는 서현이는 서울과학고에 입학해서도 아침 산책을 즐기려고 합니다. 서현이는 산책을 위해 서울과학고의 지리를 분석했고, 그 결과 서울과학고를 $N$개의 장소를 $N-1$개의 길이 잇는 트리 형태로 단순화시킬 수 있었습니다. 트리 구조이므로, 모든 장소를 몇 개의 길을 통해 오고갈 수 있습니다. 아침 산책은 시작점과 도착점을 정하고, 시작점에서 도착점까지 트리 위의 단순 경로(같은 점을 여러 번 지나지 않는 경로)를 따라 걷게 됩니다. 트리 위의 두 점 사이의 경로는 유일하므로 시작점과 도착점이 정해지면 경로는 유일하게 결정됩니다. $N$개 장소 중에 일부 장소는 실내이며, 나머지 장소는 실외입니다. 서현이는 산책을 시작하기 전부터 운동을 하는 것을 원치 않기 때문에,..
-
[python] 백준 6549 :: 히스토그램에서 가장 큰 직사각형 (스택)
[히스토그램에서 가장 큰 직사각형] # 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. # 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼..
-
[python] 백준 10000 :: 원 영역 (스택)
[원 영역] # 문제 x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다. 원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오. 영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다. # 입력 첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다. 다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109) 입력으로 주어지는 원은 항상 유일하다. # 출력 첫째 줄에 원으로 인해서 만들어지는 영역의 개수를 출력한다. 0. 풀이 방법 주어진 데이터에서 각 원의 왼쪽 점과 오른쪽 점을 구한다. 왼쪽 점 =..
-
[SEO, SSR, OpenGraph] 서버사이드렌더링으로 검색 엔진 최적화, 다른 사이트의 정보 가져오기
페이지에 접속해서 html 코드를 가져오면 원하는 요소를 찾아낼 수 있다. (인기검색어 등) 쉽게 해주는 라이브러리를 이용할 수 있다. 브라우저는 백엔드에 HTTP 통신을 해서 데이터를 받아온다. HTTP는 Hyper Text transfer protocol로, 텍스트 데이터 또는 하이퍼 텍스트(HTML)를 전송하는 길이다. 즉, 백엔드에서 만들어둔 API를 통해서 데이터뿐만이 아니라 HTML도 주고받을 수 있다. (주소를 입력하면 된당) 터미널에서 curl을 이용해서 html 파일 받아오기 curl 주소: rest api의 get방식 (get 생략 가능) curl -XPOST 주소 : post방식 👇🏻 postman에서도 같은 결과가 나온다. (=> axios로도 가능하다는 뜻!) Scraping 한번..
-
[GraphQL] GraphQL Code Generator로 TypeScript 지정하기
GraphQL Code Generator [GraphQL-CodeGen 사이트] RestAPI를 사용하면 API에 대한 타입을 일일히 지정해줘야 하지만, GraphQL에서는 codegen을 이용해서 API의 타입들을 TS 파일로 한번에 다운받아 편리하게 사용할 수 있다. API 데이터에 타입을 지정하면 좋은 점 응답 데이터 안에 있는 값들에 자동 완성 기능을 사용할 수 있다. 잘못된 타입의 값을 입력했을 때 에러메시지를 통해 알 수 있다. 설치하기 1. codegen을 사용할 프로젝트에 아래 명령어를 한 줄씩 입력한다. yarn add @graphql-codegen/cli --dev yarn add -D @graphql-codegen/typescript yarn add ts-node 2. codegen ..
New
-
React 공식 문서 읽기 스터디 회고
정글 수료 후 동기들과 함께한 React 공식 문서 읽기 스터디가 드디어 끝났다! 🎉 다음 스터디 주제를 정하기 위해서 모여서 지난 스터디 회고와 앞으로 공부할 것을 정하는 시간을 가졌다. 이 스터디원들과 제일 먼저 공부했던 것은 면접 준비를 위한 모던 자바스크립트 Deep Dive 책 읽기였고, 책을 다 읽고 나서는 본격적으로 리액트를 공부해 보기 위해서 공식 문서를 읽었다. 리액트 공식 문서를 전부 읽는 데 걸린 기간은 무려 199일... (Sep 28, 2023 ~ Mar 25, 2024) 1. 이전 스터디 회고 1) 좋았던 점 성범) 모르는 것을 알게되어 좋았다 주희) 스터디 안 했으면 아예 공부 안 했을 것 같은데 조금이라도 하게 되어서 좋았다 성범) 개발이 재밌어보인다. 새로운 것을 배워서 적..
-
[React] createRoot, hydrateRoot
리액트를 쓸 수 있게 해주는 루트를 만드는 API들! Next.js 같은 프레임워크를 쓴다면 별로 쓸 일이 없을 것 같긴 한...🫠 📄 Docs 🔗 createRoot 🔗 hydrateRoot createRoot 브라우저의 DOM 노드 안에 React 컴포넌트를 표시하는 루트를 생성하는 API 1. Reference import { createRoot } from 'react-dom/client'; const domNode = document.getElementById('root'); const root = createRoot(domNode); 루트를 생성한 후, 그 안에 React 컴포넌트를 표시하기 위해 root.render(;)를 호출해야 한다. 온전히 React만으로 구축된 앱은 보통 루트 컴포넌..
-
[React] createPortal
모달 짱 쉽게 만들 수 있을 것만 같은 API..🩵 📄 Docs 🔗 createPortal createPortal cratePortal을 사용하면 컴포넌트의 일부를 DOM의 다른 부분에 렌더링할 수 있다. 포털을 생성하려면 createPortal을 호출하고 JSX와 렌더링할 DOM 노드를 전달한다. {createPortal(children, domNode, key?)} 포털은 DOM 노드의 물리적 배치만 변경한다. 포털에 렌더링하는 JSX도 이를 렌더링하는 React 컴포넌트의 자식 노드 역할을 한다. 예를 들어, 자식은 부모 트리에서 제공하는 컨텍스트에 접근할 수 있고, 이벤트는 React 트리에 따라 자식에서 부모로 버블링된다. Parameters children React로 렌더링할 수 있는 모든 ..
-
[React] useFormState, useFormStatus
form 액션의 결과에 기반하여 상태를 업데이트할 수 있게 해주는 Hook 마지막 양식 제출의 status 정보를 제공하는 Hook 📄 Docs 🔗 useFormState 🔗 useFormStatus useFormState 💡 현재는 Canary와 experimental channel에서만 사용할 수 있다. 💡 useFormState을 사용하는 이점을 얻으려면, React 서버 컴포넌트를 지원하는 프레임워크에서 사용해야 한다. form 액션의 결과에 기반하여 상태를 업데이트할 수 있게 해주는 Hook이다. const [state, formAction] = useFormState(fn, initialState, permalink?); 1. Reference useFormState(action, initia..
-
왜 Hooks는 컴포넌트의 최상위 레벨에서 호출해야 하나요?
hook을 작성할 때는 반드시 컴포넌트의 최상위 레벨 혹은 커스텀 훅 안에서만 작성할 수 있다. 즉, 조건문, 반복문, 함수 내부에서는 hook을 호출할 수 없다. 왜 이런 규칙이 생겼는지 알아보자!! 🔗 참고한 글 React hooks: not magic, just arrays Untangling the rules around the proposal using diagrams medium.com State: 컴포넌트의 메모리 – React The library for web and native user interfaces react-ko.dev useState를 호출하는 코드를 보면, 인자로 초기값만을 전달하고 있다. const [index, setIndex] = useState(0); 어떤 state..
-
[React] useRef, forwardRef, useImperativeHandle
리렌더링을 일으키지 않고 정보를 "기억하는" 방법을 알아보자. 컴포넌트가 특정 정보를 기억하도록 하고 싶지만 그 정보가 새로운 렌더링을 촉발하지 않게 하려면 ref를 사용하면 된다! 📄 Docs 🔗 useRef 🔗 Referencing Values with Refs 🔗 Manipulating the DOM with Refs 0. useRef useRef(initialValue) 컴포넌트의 최상위 레벨에서 useRef를 호출해서 ref를 선언한다. import { useRef } from 'react'; const ref = useRef(0); useRef가 반환하는 객체 { current: 0 // The value you passed to useRef } ref.current 속성을 통해 ref의 현재..
-
[KAIST 정글] 나만무 프로젝트 회고 (2) :: 씽잉러너 만들기
초안 발표에서 탈탈 털린 우리 팀은 기획을 전반 수정해야 했다. 그렇게 나온 아이디어가 이름도 장황한 캐주얼 노래 배틀 게임 ㅋㅋ 캐주얼은 왜 붙인 건지 아직도 모르겠음 노래를 부르면 실시간으로 채점을 해주고 동시에 다른 친구와 대결을 할 수 있는 게임이다. 노래만 부르면 아쉬우니까 여기에 아이템으로 공격을 할 수 있고 방어 아이템을 쓰거나 특정 행동으로 공격을 회피할 수도 있다. 처음에는 내가 엄청 반대했다. 이유는 '난 이걸 만들 수 없어..' 웹만 만들어봤는데, 게임을 만드는 건 상상도 못 해봤고 어떻게 해야 하는 건지 도무지 감이 잡히지 않았다. 그래픽 관련 기술을 새로 배워서 하기엔 시간이 너무 촉박할 것 같고, 이 프로젝트에서 잘할 수 있는 걸 하고 싶었지 겨우겨우 해내는 걸 하고 싶지 않았다..
-
[KAIST 정글] 나만무 프로젝트 회고 (1) :: 팀 형성, 초안 발표
너무너무 늦었지만 이제라도 작성하는 나만의 무기를 갖기 회고 Start~! 지금은 나만무 최종 발표(7/8)가 끝난 지 3개월이나 지났다 ㅎㅎ 우선 나만무에 대한 나의 생각부터 기록해 보자면.. 부트캠프를 하고 남는 것은 프로젝트뿐이라고 생각하였고, 나에겐 무려 세 번째 부트캠프인 만큼 굉장한 프로젝트를 해내야 하고 해낼 수 있을 것이라는 자신감이 가득했다. 리더 지원 당연하게도 리더에 지원했다. 지원한 이유는 프로젝트 경험이 있다. 원래 나서는 거 좋아함. 답답할 바에 내가 뛸래 ! 앞으로 사회에 나가면 리더가 되기까지 몇 년은 더 기다려야 한다. 내가 스스로 리더가 될 수 있는 마지막 기회니까 애초에 크래프톤에서 발표하는 영상 보고 반해서 나도 하고싶어서 정글 지원했음 취업에도 당연히 도움이 될 것 ..
-
[Redux] Redux, React Redux, Redux DevTools
1. Redux 📄 Redux 📄 React Redux 1-1. Installation npm install redux npm install react-redux1-2. Setting 1) Redux Store를 이용 가능하게 해주는 컴포넌트인 로 index.js의 을 감싼다. 는 react-redux에서 가져온다. store는 별도의 파일에서 만들어서 가져온다. import { BrowserRouter } from "react-router-dom"; import { Provider } from "react-redux"; ~~~ 생략 ~~~ root.render( ); ~~~ 생략 ~~~2) reducer 생성 store를 만들기 위해서는 reducer가 필요하므로, reducer를 먼저 만들어주자! s..
-
[React] Router (version 6)
1. Installation npm install react-router-dom@6 2. Setting 1) src/index.js 로 App을 감싼다. import { BrowserRouter } from "react-router-dom"; const root = ReactDOM.createRoot(document.getElementById("root")); root.render( ); 2) src/App.js 안에서 필요한 페이지들을 태그를 이용해 정의해둔다. path 속성에 담은 값이 각 페이지의 경로가 된다. import "./App.css"; import { Routes, Route } from "react-router-dom"; import Homepage from "./page/Homepag..
-
[React] Class Component
1. 기본 형태 클래스 컴포넌트의 기본 형태를 먼저 보자! ES7 React/Redux/React-Native/JS snippets Extension을 사용하고 있다면 rcc를 입력하면 기본 형태를 자동으로 입력할 수 있다. import React, { Component } from 'react' export default class AppClass extends Component { render() { return ( ) } } 2. State 1) state 만들기 클래스 컴포넌트는 hook이 없다! 따라서 function 컴포넌트처럼 useState를 사용할 수 없다. constructor 메서드 안에서 state 객체를 만들어주고 안에 필요한 state들을 요소로 넣어준다. (이 c..
-
[React] Describing the UI
📄 Docs 2023년에 리뉴얼된 리액트 공식 문서의 "Describing the UI" 내용이다. 📚 You will learn React Component import / export JSX props 조건부 렌더링 목록 렌더링 컴포넌트 순수성 유지 1. React Component 1-1. 컴포넌트: UI 구성 요소 리액트는 markup, CSS, JS를 사용자 정의 컴포넌트로 결합할 수 있게 해주며, 이는 앱의 재사용 가능한 UI 요소가 된다. 1-2. 컴포넌트 중첩 컴포넌트는 일반 JS 함수이므로 한 파일에 여러 컴포넌트를 포함할 수 있다. 컴포넌트가 다른 컴포넌트를 렌더링할 수는 있지만, 아래처럼 정의를 중첩해서는 안 된다!! export default function Gallery() { /..
-
[React] Quick Start :: 80% of React concepts
📄 Docs 2023년 3월에 리뉴얼된 리액트 공식 문서의 첫번째 장, "Quick Start"의 내용이다. 📚 You will learn 컴포넌트 생성 및 중첩 마크업과 스타일 추가 데이터 표시 조건부 렌더링과 목록 렌더링 이벤트 응답 및 화면 업데이트 컴포넌트 간 데이터 공유 1. Creating and nesting components 리액트는 컴포넌트로 구성된다. 컴포넌트는 자체 로직과 외관을 가진 UI의 일부이다. 컴포넌트는 버튼만큼 작을 수도 있고, 한 페이지 전체만큼 클 수도 있다. 리액트 컴포넌트는 마크업을 리턴하는 JS 함수이다. 컴포넌트의 이름은 대문자로 시작한다. 1-1) 컴포넌트 생성 function MyButton() { return ( I'm a button ); } 1-..
-
Optimistic UI: 빠르게 할 수 없다면, 속여보자! ㅋㅋ
Optimistic UI 유저가 네트워크 응답을 기다려야 할 때, 예상 응답을 미리 표시해주어 지연을 숨기는 방법이다. 전제 조건 실패할 가능성이 낮고, 실패해도 문제가 없는 상황에 적용해야한다. 배제해야 하는 경우 여러 테이블에 데이터를 함께 저장하는 경우. 👉하나라도 실패하면 전체 API가 실패로 처리되기 때문에 실패 확률이 높기 때문 활용 예시: 좋아요 프로세스 일반적인 방식 브라우저에서 좋아요를 누르면 백엔드에 `좋아요 API`를 요청하고 DB에 접근해서 기존의 좋아요 수에 +1을 한다. DB에서 돌려받은 값을 백엔드를 거쳐 브라우저에서 받아서 화면에 보여준다. 👇🏻 Optimistic UI를 적용하면 ~ state에 좋아요의 값을 +1 해놓고 state를 화면에 먼저 보여준다. 실제 요청의 결과..
-
Memoization으로 성능 최적화하기 (memo, useMemo, useCallback)
state가 바뀌면 바뀐 state로 컴포넌트가 다시 만들어지는데, 불필요한 재렌더링은 성능에 악영향을 미친다. 컴포넌트가 어떻게 재생성되고, 다시 만들지 않게 하는 방법은 무엇인지 알아보자! memoization 새로 만들 컴포넌트를 메모해놓고, 다음에 다시 만들어야 할 때 새로 만들지 않고 메모해 놓은 것을 가져다 쓴다고 생각하면 된다. 재렌더링 시 새로 만들어지는 것들 컴포넌트 안의 hook을 제외한 나머지는 전부 새롭게 다시 만들어진다. 부모가 새로 만들어지면 자식들도 새로 만들어진다. 렌더링이 일어나면 hook을 제외한 모든것이 새로 만들어진다. 1. let과 state let으로 선언한 변수는 값이 바뀌어도 화면에 반영되지 않는다. 반면, state가 변경되면 렌더링이 일어나고 화면에 반영된다..
-
HOC: 먼저 실행하는 컴포넌트 만들기
HOC가 가능해지는 원리부터 알아보자! 컴포넌트를 가져올 때 사용하는 일반적인 방법이다. (Aaa 컴포넌트에서 Bbb 컴포넌트를 불러오고 있다.) 이때, Bbb 컴포넌트를 불러오는 방식을 함수를 호출하는 형태로 변경할 수 있다. 여기에 컴포넌트를 하나 더 추가해보자. 추가하는 컴포넌트는 Aaa가 Bbb를 불러올 때 그 사이에 실행시킬 것이다. `먼저 실행 컴포넌트`를 보면, 함수 안에서 함수(Component)를 리턴하면서 리턴하는 함수의 props를 리턴되는 컴포넌트에 전달해주고 있다. 이를 활용하면 Aaa를 실행시키면 Bbb 컴포넌트에 props는 그대로 전달하고, 먼저 실행 컴포넌트에서 필요한 로직들을 먼저 실행시킬 수 있게 된다. 이렇게 중간에 추가한 `먼저 실행 컴포넌트`를 Higher Orde..
-
Closure: 외부 변수를 기억하는 함수
Closure 클로저는 함수가 선언된 렉시컬 환경을 '기억'하여, 해당 함수가 선언된 범위 바깥에서 호출되더라도 그 환경에 있는 변수를 접근하고 조작할 수 있게 하는 프로그래밍 패턴이다. 함수는 보통 호출되고 나면 실행이 끝나고, 그 안에서 선언한 모든 변수는 메모리에서 해제된다. 이렇게 되면 일반적으로 해당 함수의 변수에는 접근할 수 없게 된다. 그런데, 클로저가 있는 경우에는 얘기가 달라진다. 클로저가 있으면 외부 함수가 종료되어도, 내부 함수가 외부 함수의 지역 변수에 계속해서 접근할 수 있다. (외부 함수의 변수를 기억하고 계속 사용할 수 있게 된다.) 우선 함수 내부에 함수가 있는 유형을 먼저 만들어보자. 외부함수 aaa의 지역변수에 내부함수인 bbb가 접근할 수 있다. apple이 외부함수에 ..
-
Next.js와 브라우저 저장소
브라우저의 저장공간 브라우저에 데이터를 저장할 수 있는 공간을 먼저 알아보자! 개발자 도구 > Application에서 볼 수 있다. 1. Local Storage 브라우저를 껐다가 켜도 남아있는다. ex) 비회원으로 장바구니 담기한 경우 저장 보안상 중요한 데이터를 저장하는 것은 옳지 않다. console에 찍으면 다~ 나오기 때문,, 2. Session Storage 브라우저를 끄면 사라진다. 3. Cookies 브라우저와 백엔드 간 연결 시 데이터 전달 통로가 될 수 있다. 지정한 시간이 지나면 사라진다. 백엔드 API와 통신할 때 같이 보낼 수 있다. 만료 시간을 지정할 수 있다. 이렇게 객체 형태로 저장해서 사용할 수 있다. 그런데, Next.js 환경에서 이러한 브라우저 저장소에 접근하려고 하..
-
[Pintos-KAIST] Project 4 :: 디스크의 파일 데이터 할당 방법
Pintos Project4에서는 FAT 방식으로 파일 데이터를 할당한다. FAT 방식은 파일이 할당된 블록의 위치 정보를 chain 형태로 관리하는 Linked Allocation 방식에 해당한다. 이외에도 파일 데이터를 할당하는 방식은 여러가지가 있다. Contiguous Allocation Linked Allocation Indexed Allocation 1. Contiguous Allocation 연속 할당 방식은 각 파일을 디스크의 연속적으로 이어지는 공간에 할당한다. 이 상황에서 중간에 있는 길이가 5인 주황색 파일이 삭제되어 공간이 비었을 때, 길이가 6인 노랑색 파일을 저장하려고 한다면, 실제 디스크의 공간이 6 이상 비어있음에도 불구하고, 연속된 공간이 아니기 때문에 할당할 수 없어 4 ..
-
[Pintos-KAIST] Project 3 :: Memory Mapped Files
Memory-mapped page Memory-mapped page는 Anonymous page와 달리 파일을 기반으로 매핑하는 페이지이다. 즉, 이 페이지에 담기는 내용은 실제 디스크에 존재하는 파일의 데이터가 담긴다. 🤔 왜 매핑을 해야 하지? 파일과 메모리를 매핑하면, 파일을 메모리처럼 접근할 수 있게 되어서 파일 입출력의 효율성을 향상할 수 있다. 이렇게 파일과 매핑된 메모리 영역은 가상 주소 공간에서 접근 가능하며, 해당 영역에 대한 읽기/쓰기 작업이 가능해진다. 쓰기 작업으로 인해 파일의 내용이 변경되면 매핑이 해제(unmap)될 때 디스크의 실제 파일에 해당 변경 사항이 반영된다. Mapping 파일과 메모리 매핑은 System call인 mmap()을 통해 이루어진다. Pintos에서는 v..
-
[Pintos-KAIST] Project 3 :: Anonymous Page (Lazy Loading으로 메모리 효율성 높이기)
💡 이번 파트에서는 Anonymous page라고 불리는 non-disk based image를 구현한다. Anonymous Page란? 파일을 기반으로 하는 file-backed page와 달리, 이름이 지정된 파일 소스가 없기 때문에 anonymous라고 불리며, 스택과 힙 영역에서 사용된다. Lazy Loading을 이용한 페이지 초기화 Lazy loading은 메모리 로딩을 필요한 시점까지 미루는 디자인 패턴이다. Lazy Loading을 구현하기 위해서는 페이지를 할당할 때 해당 페이지에 대응하는 page 구조체만 만들고, 물리 frame 할당 ❌ 실제 내용도 ❌ (아직은 로딩하지 않는다!) 그럼 내용은 언제 로드하지 ?! 👉🏻 실제로 내용이 로드되는 시점은 page fault가 발생하는 시점이..
-
[Pintos-KAIST] Project 3 :: Memory Management
Pintos Project 3의 첫번째 과제인 Memory Management에서는 supplemental page table을 먼저 다루고, Physical Memory와의 매핑하는 함수를 구현한다. Implement Supplemental Page Table 현재 상태에서 Pintos는 가상 및 물리적 메모리 매핑을 관리하기 위한 페이지 테이블(pml4)을 가지고 있다. pml4 이외에 추가로, page fault 및 리소스 관리를 처리하기 위해 supplementary page table이 필요하다. 💡 Implement supplemental page table management functions in vm/vm.c. 0) supplemental page table hash table을 이용해서..
-
[Pintos-KAIST] Project 2 :: System Calls - 3 (File System), User Memory
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory User Memory Access system call의 일환으로, 커널은 종종 사용자 프로그램이 제공한 포인터를 통해 메모리에 접근해야 합니다. 그러나 사용자는 1) null 포인터, 2) 매핑되지 않은 가상 메모리를 가리키는 포인터 또는 3) 커널 가상 주소 공간(KERN_BASE 이상)을 전달할 수 있으므로, 커널은 이를 ..
-
[Pintos-KAIST] Project 2 :: Argument Passing (User 프로그램 인자 설정하기)
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory Argument passing user 프로그램이 실행되기 전에 프로그램에 대한 인자를 설정해야 한다. 👇🏻 인자를 어떻게 처리해야 하는지 예시를 통해 먼저 알아보자! 예시) "/bin/ls -l foo bar"의 인자 처리하기 명령어를 단어로 분할한다: /bin/ls, -l, foo, bar 각 문자열과 널 포인터를 스택에 오..
-
[Pintos-KAIST] Project 3 :: Stack Growth (Pintos의 스택 확장 메커니즘)
Stack Growth Project 2까지 사용하던 스택은 USER_STACK을 시작으로 하는 단일 페이지였으며, 프로그램의 실행은 이 크기로 제한되어 있었다. Stack Growth를 구현하면 스택이 현재 크기를 초과하면 추가 페이지를 할당한다. 즉, 접근한 가상 주소에 매핑된 frame이 없어서 page fault가 발생한 경우 중에서 접근한 가상 주소가 Stack 영역 내에 존재할 경우에는 추가 페이지를 할당해 page fault를 해결해보자! 우선 접근한 주소가 Stack 영역 내에 존재하는지 판별해야 한다. 접근한 주소가 Stack 영역 내에 존재하는지 판별하기 page fault가 발생했을 때 접근한 주소가 stack 안에 있는지 판별하고, stack에 접근한 경우에는 stack growth..
-
[Pintos-KAIST] Project 2 :: System Calls - 1 (System Calls이 호출되는 과정)
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory Pintos 프로젝트 2 과제로 시스템콜을 구현했다. 1.5주동안 열씸히 구현한💦 유저 프로그램을 실행시키고 시스템콜을 호출하는 그 과정이 어떻게 이루어지는지 알아보자! system call을 호출하는 open-normal 테스트 파일이 실행되는 데까지 어떤 과정을 거치게 될까?? open-normal 👇🏻 System call..
-
[python] 백준 17835 :: 면접보는 승범이네 (dijkstra)
면접보는 승범이네 # 문제 마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다. 면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다. 모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장..
-
[Pintos-KAIST] Project 2 :: System Calls - 2 (exec, wait, fork), Deny Write on Executables
Pintos Project 2 관련 포스팅 목록 Argument Passing (User 프로그램 인자 설정하기) System Calls - 1 (System Calls이 호출되는 과정) System Calls - 2 (exec, wait, fork) & Deny Write on Executables System Calls - 3 (File System) & User Memory 1. exec 1-1. exec 요구사항 현재 프로세스를 cmd_line에 주어진 실행 파일로 변경하고, 필요한 인수를 전달합니다. 이 함수는 성공한 경우 반환하지 않습니다. 프로그램이 로드되거나 실행될 수 없는 경우 종료 상태 -1로 프로세스가 종료됩니다. 이 함수는 exec를 호출한 스레드의 이름을 변경하지 않습니다. 파일 ..
-
[KAIST 정글] 8주차 회고
벌써 정글에 입소한 지 두 달이 지났다. 정글의 커리큘럼을 보니 딱 중간 단계에 와있다. 지금까지 정글에 와서 정말 많은 공부를 했다. 배운 것들을 머릿속에만 남겨놓기 아까우니 여기에 남겨놔야지~! 1 ~ 4주차 :: 컴퓨팅 사고로의 전환 첫 4주동안은 난생처음 들어보는 자료구조와 알고리즘을 배우면서 정말 많은 알고리즘 문제를 풀었다. 이 세상엔 다양한 알고리즘이 very many 존재한다는 것을 알게 되었고, 이걸 모르고 살았던 인생이 아까울 정도였다. 복잡한 문제를 코드 몇 줄로 뚝딱 간단한 문제로 바꿔버리는 것이 아주 매력적이다. 요즘은 특히 다익스트라에게 아주 빠져버렸다 ㅎㅎ dijkstra
-
[Pintos-KAIST] Project 1 :: Priority Donation
Donation Donation 구현사항 lock을 보유하고 있는 스레드가 낮은 우선순위를 가진 스레드일 경우, 대기하고 있는 스레드의 우선순위를 보유한 스레드에게 기부한다. 이 때, 재귀적으로 기부가 이루어질 수 있다. 🤔 Donation을 하는 이유 :: Priority Inversion 높은 우선순위 스레드가 낮은 우선순위 스레드가 가진 공유 자원(lock)을 사용하기 위해 대기할 때 Priority Inversion이 발생한다. 높은 우선순위 스레드는 블록되어 CPU 시간을 할당받지 못하고, 대기 상태에서 머물러 있게 된다. 이럴 경우 중간 우선순위의 스레드가 ready_list에 존재한다면, 높은 우선순위 스레드는 우선순위가 더 높음에도 불구하고 CPU 시간을 할당받지 못하고 대기 상태에 머물러..
-
[Pintos-KAIST] Project 1 :: Priority Scheduling
Priority Scheduling 💡 우선순위가 높은 스레드가 먼저 CPU를 점유할 수 있도록 Priority Scheduling을 구현한다. Priority Scheduling 구현사항 스레드들은 각 우선순위에 따라 ready list에 추가된다. 현재 실행 중인 스레드의 우선순위보다 높은 우선순위의 스레드가 ready list에 추가되면, 현재 실행 중인 스레드는 바로 CPU를 양도한다. 스레드는 언제든지 자신의 우선순위를 변경할 수 있다. 우선순위를 낮추어 더이상 가장 높은 우선순위가 아니게 된다면, 즉시 CPU를 양도한다. lock, semaphore, condition variable을 사용하여 대기하고 있는 스레드가 여러 개인 경우, 우선순위가 가장 높은 스레드가 먼저 깨어나야 한다. 구현하..
-
[Pintos-KAIST] Project 1 :: Alarm Clock (Sleep-Awake 방식의 Alarm Clock 구현하기)
Alarm Clock 💡 스레드를 잠시 재웠다가 일정 시간이 지나면 깨우는 기능인 Alarm Clock을 Busy-waiting 방식에서 Sleep-Awake 방식으로 변경하자! 1) Busy-waiting과 Sleep-Awake의 차이 Busy waiting은 특정 조건이 매우 빠르게 충족될 것으로 예상될 때 사용되는 것이 적합하며, Alarm clock은 일정 시간 이후에 수행해야 하는 작업이 있을 때 사용된다. Busy waiting 프로그램이 다른 작업을 수행하며 기다리는 대신, 특정 조건이 충족될 때까지 반복적으로 체크를 하면서 기다리는 것을 말한다. 이러한 방식은 CPU 자원을 낭비하고, 다른 스레드가 실행되는 기회를 줄여 성능 저하를 야기할 수 있다. Alarm Clock 프로그램이 일정 시..
-
[c언어] Proxy Lab :: Proxy Server 구현하기 (Sequential proxy, Concurrent proxy, Caching)
🔎 Proxy Lab 🖥 Github에서 전체 코드 보기 Carnegie Mellon University의 Proxy Lab 과제 Web Proxy는 웹 브라우저와 end server 사이에서 중간자 역할을 하는 프로그램이다. 웹 페이지를 가져오기 위해서 브라우저가 end server에 직접 연결하는 대신에, proxy server에 연결하여 요청을 전달할 수 있다. end server가 proxy server에 응답을 하면, proxy server가 응답을 브라우저에 전달한다. 🤔 Proxy의 역할 Firewall: 프록시는 방화벽 외부에 있는 브라우저가 종단 서버에 접근할 때 프록시를 통해서만 접근이 가능하게 만들어주는 중개자 역할을 할 수 있다. 👉🏻 이를 통해 내부 네트워크는 외부로부터 보호될 수..
-
[c언어] Malloc Lab :: 동적 할당기 구현하기 (Implicit List, Explicit List, Segregated List, Buddy System)
🔎 Malloc Lab Carnegie Mellon University의 Malloc Lab 과제 C 프로그램을 위한 malloc, free 및 realloc 루틴의 버전을 직접 작성하는 과제이다. 주어진 파일을 초기 상태에서 테스트를 해보면 아래와 같이 out of memory 에러가 발생한다. implicit list 방식대로 malloc을 구현해서 이 out of memory 에러를 없애는 과제이다. 추가적으로 explicit list와 seglist 등을 활용해서 점수를 높일 수 있다. dynamic storage allocator는 네 가지 기능으로 구성된다. 이 함수들은 mm.h에 선언되어 있고, mm.c에서 정의한다. int mm_init(void); // 초기화 void *mm_malloc..
-
[c언어] Red-Black Tree 구현하기
🫶 Notion에서 보기 🫶 Red-Black Tree 🔎 Red-Black Tree란? www.notion.so 🔎 Red-Black Tree란? self-balancing binary search tree의 일종이다. 각 노드 당 한 비트의 추가 기억 공간을 가지는데, 이 비트는 노드의 색상 정보를 빨간색 또는 검은색으로 저장한다. 루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하게 되어 근사적으로 균형을 이룬 트리가 된다. 트리를 self-balancing 하게 만들어주어 검색, 삽입, 삭제 연산을 모두 O(log n)의 시간 복잡도를 보장하며, 이진 탐색 트리와 달리 최악의 경우에도 균형이 깨지지 않도록 보장한다. 🚨 ..
-
Why Is Code Review Necessary?
1. Google이 일하는 방식 1) Test Driven Development 테스트가 기본이다. 구현해야 할 요구사항과 구현체를 분리해서 구현하기 전에 테스트를 먼저 작성한다. 엣지 케이스, 코너 케이스 등을 생각해서 테스트를 작성한다. 테스트를 먼저 작성하는 이유: 코딩을 먼저 하면 내 코드에 맞는 테스트만 떠올리게 되기 때문에, 테스트를 먼저 작성하고 코딩을 한다. 테스트는 실행 가능한 문서라고 하는데, comment는 테스트해볼 수도 없고 내 코드와 맞는지 확인할 수 없는 반면, 테스트는 코드와 동기화가 될 수 밖에 없기 때문이다. 구글은 테스트가 없으면 커밋조차 할 수 없다. 2) Short iterations 자잘하게 빨리 빨리 많이 커밋을 해놔야 문제가 생겼을 때 파악하기 쉽다. 3) Pa..
-
MacOS에서 Ubuntu 개발 환경 설치하기 (AWS, VSC)
인스턴스 생성하기 우선 AWS에 접속해서 Ubuntu 인스턴스를 생성한다. AWS EC2 접속 인스턴스 시작 클릭 인스턴스 이름 작성 우분투 선택 새 키 페어 생성 키 페어 이름 작성 후 키 페어 생성 클릭 스토리지 사이즈 27GiB로 변경 인스턴스 시작 클릭 인스턴스 생성 완료! 이제 이 인스턴스에 접속해보자 접속하기 1. SSH 설정파일 만들기 Finder에서 사용자 폴더에 들어온다. .ssh라는 이름으로 폴더 생성 (자동으로 숨겨진 폴더로 생성된다.) 터미널에서 cd 명령어를 사용해서 .ssh로 들어온다. vi config (config라는 이름의 파일 생성) 생성한 파일에 아래처럼 작성 2. 키페어 권한 변경 키페어가 저장된 경로에서 파일들의 권한을 함께 보는 명령어를 입력해보면(ls -l ) 키..
-
[python] 백준 2098 :: 외판원 순회 (DP, 비트마스킹)
[외판원 순회] # 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 ..
-
[python] 백준 11049 :: 행렬 곱셈 순서 (DP)
[행렬 곱셈 순서] # 문제 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. 예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자. AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다. BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다. 같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다. 행렬 N개의 크기가 ..
-
[python] 백준 3055 :: 탈출 (BFS)
[탈출] # 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. ..
-
[python] 백준 2617 :: 구슬찾기 (DFS)
[구슬찾기] # 문제 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다. 우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다. 예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다. 구슬 2번이 구슬 1번보다 무겁다. 구슬..
-
[python] 백준 2573 :: 빙산 (DFS)
[빙산] # 문제 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다. 그림 3은 그림 1의 빙산이 ..
-
[python] 백준 21606 :: 아침 산책 (DFS)
[아침 산책] # 문제 아침 산책을 즐기는 서현이는 서울과학고에 입학해서도 아침 산책을 즐기려고 합니다. 서현이는 산책을 위해 서울과학고의 지리를 분석했고, 그 결과 서울과학고를 $N$개의 장소를 $N-1$개의 길이 잇는 트리 형태로 단순화시킬 수 있었습니다. 트리 구조이므로, 모든 장소를 몇 개의 길을 통해 오고갈 수 있습니다. 아침 산책은 시작점과 도착점을 정하고, 시작점에서 도착점까지 트리 위의 단순 경로(같은 점을 여러 번 지나지 않는 경로)를 따라 걷게 됩니다. 트리 위의 두 점 사이의 경로는 유일하므로 시작점과 도착점이 정해지면 경로는 유일하게 결정됩니다. $N$개 장소 중에 일부 장소는 실내이며, 나머지 장소는 실외입니다. 서현이는 산책을 시작하기 전부터 운동을 하는 것을 원치 않기 때문에,..
-
[python] 백준 1707 :: 이분 그래프
[이분 그래프] # 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. # 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ..
-
[C언어] C언어 기초 :: main 함수, 메모리 크기, 자료형, 상수, 조건문, 반복문, 입출력, 사용자 정의 함수
hello, C..! 😀 C언어는 메모리 주소에 직접 접근할 수 있다는 점에서 강력한 언어가 되며 다양한 운영체제 및 언어들의 기본이 되고 있다. 고급 언어에 속하면서도 거의 어셈블리어 취급을 받고 있다 ㅋㅎ ㅜ,, C언어의 기초가 되는 부분들을 훑어보자 📖 1. main 함수 작성하기 #include int main(void) { printf("hello world\n"); return 0; // main 함수의 반환값을 int로 정했으니, 함수를 종료할 때 정수를 반환해줘야 한다. } main 함수는 프로그램이 실행될 때 가장 첫번째로 실행되는 부분이다. int main(void)와 return 0을 약속처럼 동일하게 쓴다. 라이브러리 printf 같은 함수를 사용하려면 이 라이브러리를 추가해줘야 한..
-
[C언어] MacOS - VSC에 C언어 개발 환경 구축하기
C언어 개발 환경 설정하기 1. 확장 프로그램 설치 VSC에서 확장 프로그램 C/C++이랑 Code Runner 이 두개를 설치해준다. 2. 설정 변경 Code > 기본 설정 > 설정 으로 들어간다. run in terminal 검색 왼쪽에서 Run Code configuration 클릭 Code-runner: Run in Terminal에 체크한다. 3. 파일 실행 hello.c 파일을 만들어줬다. #include int main(void) { printf("hello world\n"); return 0; } 오른쪽 위에 있는 ▶️ (Run Code) 버튼 누르면 실행 완료~! 터미널에 hello world가 출력되었다.
-
[python] 백준 11724 :: 연결 요소의 개수
[연결 요소의 개수] # 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. # 출력 첫째 줄에 연결 요소의 개수를 출력한다. 풀이 연결된 뭉텅이가 몇개인지 묻는 문제이다. DFS 탐색을 수행하면, 연결된 요소를 모두 방문하게 된다. 따라서, 한 요소에 대한 탐색이 종료되고 새로운 탐색이 시작된다는 것은, 연결이 끊긴 것을 의미한다. 탐색이 끊기고 새롭게 시작되는 횟수를..
-
[python] 백준 1260 :: DFS와 BFS
[DFS와 BFS] # 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. # 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. # 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 ..
-
[python] 백준 1197 :: 최소 스패닝 트리
[최소 스패닝 트리] # 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. # 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 ..
-
[python] 백준 5639 :: 이진 검색 트리
[이진 검색 트리] # 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다. 이진 검색 트리..
-
[python] 백준 5904 :: Moo 게임 (분할정복)
[Moo 게임] # 문제 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다. S(0) = "m o o" S(1) = "m o o m o o o m o o" S(2) = "m o o m o o o m o..
-
[python] 백준 1933 :: 스카이라인 (우선순위 큐)
[스카이라인] # 문제 N개의 직사각형 모양의 건물들이 주어졌을 때, 스카이라인을 구해내는 프로그램을 작성하시오. 스카이라인은 건물 전체의 윤곽을 의미한다. 즉, 각각의 건물을 직사각형으로 표현했을 때, 그러한 직사각형들의 합집합을 구하는 문제이다. 예를 들어 직사각형 모양의 건물들이 위와 같이 주어졌다고 하자. 각각의 건물은 왼쪽 x좌표와 오른쪽 x좌표, 그리고 높이로 나타난다. 모든 건물들은 편의상 같은 높이의 지면(땅) 위에 있다고 가정하자. 위의 예에서 스카이라인을 구하면 아래와 같다. # 입력 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x..
-
[python] 백준 2014 :: 소수의 곱 (우선순위 큐)
[소수의 곱] # 문제 K개의 소수가 있다. 이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자. 예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다. K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 231보다 작은 자연수이다. # 입력 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 ..
-
[python] 백준 2261 :: 가장 가까운 두 점 (분할 정복)
[가장 가까운 두 점] # 문제 2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다. # 출력 첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다. 💡 참고한 블로그 👉🏻 codable 1. 입력 받아서 x좌표를 기준으로 정렬한다. 점이 뒤죽박죽으로 주어지니까, 일단 정렬부터 하고 보자.. # n개의 점을 입력 받아 2차원 리스트로 저장 arr = [list(map(int, sys.stdin.readline().spl..
-
[python] 백준 6549 :: 히스토그램에서 가장 큰 직사각형 (스택)
[히스토그램에서 가장 큰 직사각형] # 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. # 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼..
-
[python] 백준 10000 :: 원 영역 (스택)
[원 영역] # 문제 x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다. 원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오. 영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다. # 입력 첫째 줄에 원의 개수 N(1 ≤ N ≤ 300,000)이 주어진다. 다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109) 입력으로 주어지는 원은 항상 유일하다. # 출력 첫째 줄에 원으로 인해서 만들어지는 영역의 개수를 출력한다. 0. 풀이 방법 주어진 데이터에서 각 원의 왼쪽 점과 오른쪽 점을 구한다. 왼쪽 점 =..
-
[python] 백준 13334 :: 철로 (우선순위 큐)
[철로] # 문제 집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다. 양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사..
-
[python] 백준 1715 :: 카드 정렬하기 (우선순위 큐)
[카드 정렬하기] # 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40)..
-
[python] 백준 1655 :: 가운데를 말해요 (최대힙, 최소힙, 우선순위 큐)
[가운데를 말해요] # 문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준..
-
[python] 백준 2812 :: 크게 만들기 (스택)
[크게 만들기] 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.풀이 뒤에서 아무리 큰 숫자가 나와봤자, 앞에 있는 숫자들의 개수가 지울수 있는 총 개수보다 많으면 소용이 없다. 앞에서부터 하나씩 비교해가면서 지울 수 있는 개수만큼 지워나가야 한다. 👇🏻 요로케 숫자를 앞에서부터 하나씩 떼어서 그 앞에 나왔던 숫자보다 큰 숫자인지 확인한다. 지금 숫자가 앞에 나온 숫자들보다 큰 숫자이고, 제거할 수 있는 ..
-
[python] 백준 10830 :: 행렬 제곱 (분할 정복)
[행렬 제곱] # 문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. # 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. # 출력 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 풀이 전체 코드 import sys N, B = map(int, input().split()) A = [list(map(int, sys.stdin.readline().split())) for _ ..
-
[python] 백준 1629 :: 곱셈 (분할 정복, 모듈러 연산, 메모이제이션)
[곱셉] # 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. # 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 풀이 a, b, c = map(int, input().split()) def power(n): if n == 0: return 1 # n이 0이면 1을 반환한다. if n % 2 == 0: return (power(n//2) ** 2) % c # n이 짝수면 power(n//2)의 제곱을 반환한다. # n이 홀수면 power(n//2)의 제..
-
[CS:APP] 1-7) 운영체제의 역할
이전의 hello 프로그램을 쉘 프로그램이 로드하고 실행했을 때나 hello 프로그램이 메시지를 출력할 때, 이 프로그램이 키보드나 디스플레이, 디스크나 메인 메모리를 직접 액세스하지 않는다. 💡 운영체제가 제공하는 서비스를 활용한다. 0. 운영체제 운영체제는 하드웨어와 소프트웨어 사이에 위치한 소프트웨어 계층이다. 응용프로그램이 하드웨어를 제어하려면 언제나 운영체제를 통해서 해야 한다. 운영체제의 두 가지 주요 목적 1) 제멋대로 동작하는 응용프로그램들이 하드웨어를 잘못 사용하는 것을 막는다. 2) 응용프로그램들이 단순하고 균일한 메커니즘을 사용하여 복잡하고 매우 다른 저수준 하드웨어 장치들을 조작할 수 있도록 한다. (응용프로그램이 하드웨어를 직접 조작하려면 복잡하다. 운영체제가 중간다리 역할을 해서..
-
[CS:APP] 1-5~1-6) 캐시 메모리, 저장장치의 계층구조
캐시가 중요하다! 1-4) 프로세서의 작동 원리에서 봤듯이, 시스템이 정보를 한 곳에서 다른 곳으로 이동시키는 일에 많은 시간을 보낸다. 기계어 인스트럭션들과 데이터 스트링들의 복사 과정을 간략하게 다시 정리해보면, 데이터의 복사 과정 1) 기계어 인스트럭션들 처음에는 하드디스크에 저장되어 있다. 프로그램이 로딩될 때 메인 메모리로 복사된다. 프로세서가 프로그램을 실행할 때 프로세서로 복사된다. 2) "hello, world\n" 데이터 스트링 처음에는 디스크에 저장되어 있다. 메인 메모리로 복사된다. 디스플레이 장치로 복사된다. 더 큰 저장장치들은 보다 작은 저장장치들보다 느리다. 그리고, 더 빠른 장치들은 더 느린 장치들보다 만드는 데 비용이 많이 든다. 1) 디스크 드라이브 vs 메인 메모리 구분 ..
-
[python] 백준 2630 :: 색종이 만들기 (분할 정복)
[색종이 만들기] # 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 ..
-
[python] 백준 8983 :: 사냥꾼 (이분 탐색)
[사냥꾼] # 문제 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다. 사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다..
-
[python] 백준 16564 :: 히오스 프로게이머 (이분 탐색)
[히오스 프로게이머] # 문제 성권이는 Heroes of the Storm 프로게이머 지망생이다. 이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다. 팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가? 예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다. # 입력 첫째 줄에는 캐릭터의 개수 N, 올릴 수 ..
-
[python] 백준 2470 :: 두 용액 (두 포인터)
[두 용액] # 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수..
-
[python] 백준 2110 :: 공유기 설치 (이분 탐색)
[공유기 설치] # 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. # 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에..
-
[python] 백준 2805 :: 나무 자르기 (이분 탐색, 시간 초과 해결 방안)
[나무 자르기] # 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의..
-
[python] 백준 1920 :: 수 찾기 (이분 탐색)
[수 찾기] # 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. # 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. # 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 풀이 n_list = set(map(int, input().split())) m = input() m_list = l..
-
[python] 백준 6603 :: 로또 (백트래킹 풀이, itertools 풀이)
[로또] # 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오. # 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루..
-
[python] 백준 2503 :: 숫자 야구 (백트래킹 풀이, itertools 풀이)
[숫자 야구] # 문제 정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다. 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다. 예) 영수가 324를 갖고 있으면 429는 1 스트라이크 1 볼이다. 241은 0 스트라이크 2 볼이다. 924는 2 스트라이크 0 볼이다. 영수는 ..
-
[python] 백준 1110 :: 더하기 사이클
[더하기 사이클] # 문제 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자. 26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다. 위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다. N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작..
-
[python] 백준 14888 :: 연산자 끼워넣기 (eval 함수 성능 비교)
[연산자 끼워넣기] # 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 ..
-
[python] 백준 10971 :: 외판원 순회 2
[외판원 순회 2] # 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이..
-
[python] 백준 10819 :: 차이를 최대로
[차이를 최대로] # 문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| # 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. # 출력 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.풀이 전체 코드 - 1) itertools 활용 from itertools import permutations _ = input() m = 0 for a i..
-
[python] 백준 2798 :: 블랙잭 (itertools vs for문 비교)
[블랙잭] # 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 ..
-
[python] 백준 2309 :: 일곱 난쟁이
[일곱 난쟁이] # 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. # 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. # 출력 일곱 난쟁이의 키를 오름차순으로 출..
-
[python] 백준 1181 :: 단어 정렬
[단어 정렬] # 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. # 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. # 출력 조건에 따라 정렬하여 단어들을 출력한다.풀이 전체 코드 import sys words = [sys.stdin.readline().strip() for _ in range(int(input()))] def func(w): return len(w), w [print(..
-
[python] 백준 10989 :: 수 정렬하기 3 (도수 정렬, 계수 정렬)
[수 정렬하기 3] 🚨 메모리 제한이 8M이다. 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 전체 코드 import sys N = int(input()) # 인덱스에 해당하는 숫자의 개수를 값으로 담을 배열 count = [0] * 10001 # count의 배열에서 정렬할 숫자의 인덱스에 해당하는 값을 1씩 증가한다. for _ in range(N): count[int(sys.stdin.readline())]..
-
[python] 백준 1074 :: Z
[Z] # 문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. # 입력 첫째 줄에 정수 N, r, c가 주어진다. # 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 풀이 전체 코드 N, r, c = map(int, input().split()) def recursive(n, row, col): if n == 0: return 0 cur_count = 2 * (row % 2) + ..
-
[python] 백준 9663 :: N-Queen 👑
[N-Queen] # 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) # 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 풀이 전체 코드 N = int(input()) # row[행_idx] == True면 퀸이 있는 행 row = [False] * N # 열_idx + 행_idx == True면 퀸이 있음 right_cross = [False] * (2 * N - 1) # 열_idx - 행_idx + N-1 == True면 퀸이 있음 left_cross = [False] * (2 * N..
-
[python] 백준 5568 :: 카드 놓기 (재귀 함수 vs itertools 비교)
[카드 놓기] # 문제 상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까? 예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다. n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있..
-
[python] 백준 2628 :: 종이자르기
종이자르기 # 문제 아래 과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다. 점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, 의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다. 입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 ..
-
[python] 백준 9020 :: 골드바흐의 추측 (소수 찾기, 소수 배열 짱 빨리 만들기)
소수 찾기: 배수 제거 방식 소수를 찾을 때 에라토스테네스의 체를 이용하는 방법보다 더 빠르게 찾을 수 있는 방법이 있다. 1부터 소수를 찾아나가면서, 배수를 지워버리는 방법이다. 숫자의 배수들은 소수가 아니므로, 소수인지 검증하기 위해 다른 숫자들로 나눠볼 필요가 없다!! 전체 코드 prime = [] # 소수를 담을 배열 check = [False]+[False] + [True] * 9999 # index에 해당하는 숫자가 소수일 때만 True를 담을 배열 # 2부터 10000까지 소수 찾기 시작~! for number in range(2, 10001): if check[number]: # True가 담겨있으면 소수임! 👉🏻 prime 배열에 추가한다. prime.append(number) # 찾은 ..
-
[python] 백준 1065 :: 한수 (숫자의 각 자릿수 구하기)
숫자가 주어졌을 때, 각 자리의 수를 구하려면 숫자를 문자열로 바꾸고 문자열 = str(숫자) 문자열[0]처럼 각 인덱스에 접근해도 되지만, 이렇게 분리한 각 자릿수로 사칙연산을 하려면 또 int로 변환해줘야 한다. 아주 귀찮음..🤮 숫자 상태에서 타입 변환 없이 계산을 통해서 각 자릿수를 더 빠르게 구할 수 있다!! 숫자의 각 자릿수 구하기 # 각 자릿수를 찾으려는 값 N = 369 # 100의 자리: 100으로 나눈 몫 N100 = N // 100 # 10의 자리: 100으로 나눈 나머지를 10으로 나눈 몫 N10 = N % 100 // 10 # 1의 자리: 10으로 나눈 나머지 N1 = N % 10 👇🏻 문제에 적용 ㄱㄱ [한수] 문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 ..
-
[CS:APP] 1-4) 프로세서의 작동 원리
프로세서는 메모리에 저장된 인스트럭션을 읽고 해석한다 [1-2) 컴파일 시스템]에 의해 실행가능한 목적파일로 번역되어 디스크에 저장된 hello 실행파일을 유닉스 시스템에서 실행하는 과정을 알아보자! 쉘 hello 실행파일을 유닉스 시스템에서 실행하기 위해서 쉘이라는 응용프로그램에 그 이름을 입력한다. linux> ./hello hello, world linux> 1) 쉘은 커맨드라인 인터프리터로, 프롬프트를 출력하고 명령어 라인을 입력 받아 그 명령을 실행한다. 2) 명령어 라인이 내장 쉘 명령어가 아니면, 쉘은 실행파일의 이름으로 판단하고 그 파일을 로딩해서 실행해준다. 👉🏻 위 경우, 쉘은 hello 프로그램을 로딩하고, 실행한 뒤에 종료를 기다린다. 3) hello 프로그램은 메시지를 화면에 출력..
-
[CS:APP] 1-2~1-3) 컴파일 시스템
프로그램은 다른 프로그램에 의해 다른 형태로 번역된다 아래의 hello.c 프로그램이 시스템에서 실행되는 과정을 알아보자! 그 중에서 소스 파일이 번역되는 과정을 알아보자! hello.c #include int main() { printf("hello, world\n"); return 0; } 뭘 번역한다는 거야? hello.c를 시스템에서 실행시키려면, 각 C 문장들은 다른 프로그램들에 의해 저급 기계어 인스트럭션들로 번역되어야 한다. 이 인스트럭션들은 실행 가능 목적 프로그램( = 실행가능 목적 파일) 이라는 형태로 합쳐져서 바이너리 디스크 파일로 저장된다. 컴파일러 드라이버는 유닉스 시스템에서 아래와 같이 소스파일에서 오브젝트 파일로 번역한다. 👇🏻 GCC 컴파일러 드라이버는 소스파일 hello.c..
-
[CS:APP] 1-1) 비트와 컨텍스트
정보는 비트와 컨텍스트로 이루어진다. 아래의 hello 프로그램이 실행되는 과정을 알아보자! hello.c #include int main() { printf("hello, world\n"); return 0; } 이 hello 프로그램은 프로그래머가 에디터로 작성한 소스 프로그램(= 소스파일)로 생명을 시작하며, hello.c라는 텍스트 파일로 저장된다. 소스 프로그램 ( = 소스파일 ) hello.c 프로그램은 연속된 바이트들로 파일에 저장된다! 소스 프로그램은 0 또는 1로 표시되는 비트들의 연속이며, 바이트라는 8비트 단위로 구성된다. 각 바이트는 프로그램의 텍스트 문자를 나타낸다. 대부분의 컴퓨터 시스템은 텍스트 문자를 아스키(ASCII) 표준을 사용하여 표시한다. 아스키(ASCII) 표준 아스..
-
[KAIST 정글] 0주차 프로젝트
Project : [ 오늘 뭐 먹지? ] 구분 기획 의도 함께 식사할 친구를 모집하는 웹서비스 팀원 이주희, 김경민, 김한중 기간 3일 기술 스택 python, flask, jinja2, JWT, MongoDB, pymongo, AWS 사용 기술 1. jinja2 템플릿 1) 데이터 활용 / 서버사이드 렌더링 {{변수명}}을 적으면 html 파일에 서버의 데이터를 포함시킬 수 있고, 서버에서 렌더링하여 완성된 화면이 로드된다. app.py @app.route('/', methods=['GET']) def home(): ... return render_template('list.html', room=newRoomList) list.html {{ i.menu }} 카테고리 {{ i.category }} 약속..
-
[KAIST 정글] 1주차 에세이
정글에 입소한 지 6일차 되는 날에 작성하는 나를 돌아보는 시간 지금까지의 나 작년에 부트캠프 수료 후 개발자로 취업해 그토록 원하던 개발 업무를 하게 되어서 1년이 정말 빠르게 지나갔다. 프로젝트가 완료되고 나서는 개발 업무가 아닌 멘토 업무를 하면서 공부도 더 할 수 있었고, 내가 부족한 부분을 파악하는 기회가 되었다. 하지만, 멘토 업무를 하는 중간중간에 추가 개발 건을 맡아 진행하면서 나는 멘토링보다 개발할 때 훨씬 큰 성취감과 보람을 느끼는 것을 깨달았다. 집중적으로 개발 업무를 할 수 있는 회사를 찾아보았지만 내가 원하는 규모의 회사에 취업하기에는 한정적인 나의 기술 스택과 부족한 CS 지식이 아쉬웠다. 코드캠프에서의 즐거웠던 기억과 개발 업무를 할 때 느낀 성취감, 그리고 멘토링을 하면서 다..
-
메모리 누수: Garbage Collection, 전역 변수, 브라우저에서 메모리 확인하기
메모리 누수 Garbage Collection 변수를 만들면 변수를 브라우저 메모리에 저장하고, 만든 변수들 중 필요 없는 것들은 모아뒀다가 한번에 지운다. 👉🏻 GC(Garbage Collector)가 Garbage Collection을 하는 것이다. JS나 Java 같은 대부분의 언어는 메모리를 자동으로 할당해주는데, C언어 등의 일부 언어는 메모리를 직접 할당하고 데이터를 저장해야 한다. JavaScript는 GC가 해주니까 따로 메모리 관리를 할 필요는 없지만, 잘못 알게되면 문제가 생길 수 있다. 컴퓨터가 똑똑하긴 하지만 신은 아니니까! 컴퓨터가 오해를 하게 코딩을 하게되면, Garbage Collection을 해도 깔끔하게 지워지지 않을 수 있다. 아래는 잘 지워지고 있는 상태이다. Garba..
-
OSI 7계층, TCP/IP 4계층
OSI 7계층 OSI 7계층을 이해하면 와이어 샤크를 통해서 어느 계층의 통신을 이용하고 있는지 확인할 수 있다. 확인해야 하는 이유는? 라이브러리 등을 쓸 때 내가 보내는 통신이 어떤 통신인지 확인하려고 (확인해서 불필요한 통신을 이용하고 있다면 계층을 낮춰서 더 빠르게 통신하는 방법을 생각해 볼 수 있겠지?!) 네트워크 pending 됐을 때! API 요청을 보냈는데 멈췄을 때 방화벽 문제인지 API가 오래 걸리는 건지 상태를 확인할 수 있다. 보안에서도 이용된다. (패킷 안에 이진 코드로 프로그램을 심어서 패킷 단위를 조작해서 보낼 수 있음) tcp/ip 4계층 옛날에는 7계층으로 나누었지만, 요즘에는 TCP/IP 4계층으로 나누기도 한다. 계층이 올라갈수록 SW에 가깝다. OSI 7계층을 기준으로..
-
비트와 바이트, ArrayBuffer로 성능 향상하기
CS 지식은 왜 배워도 배워도 까먹을까..? 보통 배우는 cs 지식은 시험을 보기 위해서 외우게 되고, 시험을 보고나면 쓰이는 용도를 잘 몰라 까먹는 일이 빈번하다. 👉🏻 CS를 굳이 알아야 하나? CS 지식 필요성에 대한 의문이 생김🙁 까먹는 이유는, CS 지식을 알아도 쓰이는 곳을 모르니까.. 잊혀지기 마련이다! 실무에서 사용하면서 알게되면 자동으로 몸에 체득 되어서 익혀질텐데..ㅠㅠ 그러므로! CS 실무와 이론이 연결되는 부분부터 공부해보자!!! 레쓰기릿 1. 비트와 바이트 비트와 바이트를 알아야 하는 이유가 무엇일까? 1) 나는 모르고 싶지만, 이걸 사용하는 사람들이 있다. 😞 이걸 쓰는 사람들이랑 같이 프로젝트를 하면 그 사람들이 사용한 코드가 들어있으므로 이에 대해 알아야 유지보수가 가능해서 ..
-
자동 검색 기능 구현하기: lodash debounce
검색 하기 버튼을 누르지 않아도 자동으로 검색이 되도록 하려면, 검색창의 onChange 함수가 실행될 때 refetch가 일어나면 된다. 하나하나 입력할 때마다 refetch가 일어나면 무수히 많은 요청이 가서 서버에 부하를 줄 수 있으므로, debouncing을 이용해서 일정 기간 텀을 두고 요청을 보내게 만든다. 자동 검색 구현하기 1. lodash 설치 yarn add lodash yarn add '@types/lodash' --dev 2. import import _ from 'lodash' 3. lodash의 debounce 사용 const getDebounce = _.debounce((data) => { // data: event.target.value // 0.2초 동안 재작업이 없으면 실..
-
Debouncing & Throttling
Throttling 특정 시간 이내, 추가 입력이 있어도, 처음 1회만 실행한다. 먼저 1회 실행시키고, 지정한 기간 동안에는 추가 입력이 있어도 실행하지 않는다. 마지막 호출이 발생한 후 일정 시간이 지날 때까지 추가 입력이 없으면 그때 실행된다. 무한스크롤에 주로 사용한다. 무한 스크롤은 스크롤을 내리면 추가 데이터를 refetch 해야한다. 스크롤은 한번 내리면 엄청나게 많이 내려가기 때문에, refetch가 엄청나게 많이 일어나게 된다. 그래서 한번 내리게 되면 해당 시간 동안은 더이상 refetch가 일어나지 않도록 Throttling을 사용해야 한다. Debouncing 특정 시간 이내, 추가 입력이 없으면, 마지막 1회만 실행한다. 어떤 작업이 있을 때, 특정 시간 내에 다시 그 작업이 반복..
-
검색 프로세스 : Inverted Index, Elastic Search, Redis
백엔드에서 검색 API를 구현하는 방법 1. 테이블 풀스캔 = 풀 테이블 스캔 Board.find({title: '%점심%'}) 등의 방법을 통해서 DB를 위에서부터 하나 하나 전체를 스캔해서 해당하는 값을 찾는다. 시간이 오래 걸린다. 2. 역색인 = 역인덱스 = invertedIndex 검색용 테이블을 하나 더 만들어서, 원래 들어있던 문장을 단어로 쪼개서 각 단어(token)에 해당하는 번호를 함께 저장해놓고, 검색할 경우 이 테이블에서 조회한다. 더 빠르게 조회할 수 있다. 토크나이징: 문장을 토큰으로 쪼개는 과정 Elastic Search 검색용 테이블을 직접 만들어도 되지만, 이런 기능을 목적으로 만든 DB인 Elastic Search를 이용하면 더 편리하게 이용할 수 있다. ES는 디스크 기..
-
[Apollo Server] GraphQL API 만들기, 서버 연결하기
GraphQL API를 만들어보자!!!! [Apollo-server] 0. TypeORM 설치 및 DB 연동 1. ApolloServer & graphQL 설치 yarn add apollo-server graphql 2. [Docs]에서 내용 가져오기 Database를 연결한 index.ts 파일에 아래의 코드를 추가한다. 🚨 database를 연결하는 코드를 지우지 말고, import문 아래 나머지 코드 위에 추가한다. index.ts ~~~ 데이터베이스 연결하는 코드 ~~~ import { ApolloServer } from '@apollo/server'; import { startStandaloneServer } from '@apollo/server/standalone'; // API Docs 만들..
-
[Firebase] 프론트엔드에서 DB 다루기
[Firebase Docs] 메인 DB로서 firebase ? 규모가 커지면 보안 등의 문제가 생긴다. 규칙에서 보안처리를 하는데, 이 부분을 설정하기가 조금 까다롭다. 간단하게 서비스를 만들거나 테스트 서비스 검증용으로는 좋은 선택이 될 수 있다. 대규모 트래픽이 있는 메인 서비스로는 좀.... But, 프론트엔드 개발자로서 반드시 사용할 줄 알아야 한다. 1. 프로젝트를 생성한다. [firebase 사이트] 1) firebase 사이트에서 새로운 프로젝트를 시작한다. 2) 프로젝트 이름 입력 > 계속 3) Google 애널리틱스 사용 해제 > 프로젝트 만들기 2. 프로젝트에 firebase를 연결한다. 1) 웹 아이콘을 클릭한다. 2) 앱 닉네임을 입력하고 등록한다. 3) npm 사용으로 체크가 되었..