🏃🏻&zwj;♀️스텝바이스텝

LCS (최장 공통 부분 수열)

2024.03.11

코테 보다가 나온 것이기에 정리한다... LCS (Longest Common Subsequence)는 주어진 여러 개의 수열 중에서 모두의 부분수열이 되는 수열들 중 가장 긴 것을 찾는 것이다. 예시를 보자면, ACAYKP의 부분수열은 {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, {A, A}, {A, Y}, ... {A, C, A, Y, K, P} 이고, CAPCAK의 부분수열은 {C}, {A}, {P}, {C}, {A}, {K}, {C, A}, {C, P}, {C, C}, ... {C, A, P, C, A, K}이 있는데 각각의 부분수열 중에서 서로 같은 부분수열이 있을 것이다. 그중 가장 긴 것을 찾으면 되는데 위의 예시의 답은 길이가 4인 {A, C, A, K} 이다. 대표적..

CS/⚙️ 운영체제

[⚙️ OS] 프로세스 간 통신 (IPC: Inter-Process Communication)

2024.03.09

커널의 지원 필요 ✨ IPC의 목적 = 프로세스 동기화 data transfer sharing data event notification resource sharing and synchronization process control Message Passing 커널을 통해 주고 받음 user 계층에 있는 프로세스들끼리 직접 통신 X 👉 OS에서 제공하는 message passing에 관한 system call을 이용해 커널을 거쳐감 Messsage queue Pipes Mailboxes Sockets communication link를 만들어서 메시지를 주고 받음 🔹 Direct Communication 프로세스를 직접 지명 send(P, message) receive(Q, message) 상대방의 I..

CS/⚙️ 운영체제

[⚙️ OS] 프로세스 동기화

2024.03.09

프로세스 동기화 여러 프로세스가 공유자원에 접근한다면 race condition(경합조건)이 발생한다. 이러한 상황을 막기 위해서 필요한 mechanism이 있다. 🔹 Locking Mechanism 어떤 작업이 수행되는 것을 막는다 👉 before entering critical section 👉 before accessing shared data critical section(임계영역)은 최대한 짧게 설정해야한다 multi-processors에서 interrupt-based locks을 구현하기 어려움 👉 read-write instructions 으로 해결 🔹 Semaphore Synchronization tool Counting semaphore Binary semaphore ➔ 0 또는 1 값만..

알고리즘/프로그래머스

[프로그래머스] 단어 변환

2024.03.06

✨ BFS/DFS https://school.programmers.co.kr/learn/courses/30/lessons/43163# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📍 고려해야할 점 한 번에 한 개의 알파벳만 변경 가능 begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기 굳이 배열의 순서대로 찾을 필요 없음 🕹️ 풀이과정 👉 이 문제 같은 경우 DFS와 BFS 모두 풀이 가능하다. 하지만 DFS로 구현할 시에는 시간복잡도가 크다. 🔹 DFS words 배열에서 현재 단어와 한 글자만 다른 단어를 탐색한다. 👉 중복 탐색을 방..

CS/⚙️ 운영체제

[⚙️ OS] CPU 스케줄링

2024.03.03

CPU 스케줄링 👉 어느 프로세스가 사용될 것인지 결정 🔹 CPU 스케줄러 Ready 상태의 프로세스 중에서 이번에 CPU에 줄 프로세스 선정 🔹 Dispatcher CPU 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘김 = context switching 🔹 고려사항 누구한테 CPU를 줄 것인지 중간에 CPU를 뺏어올 수 있게 할 것인지 또는 계속 쓰게 할 것인지 🔹 scheduling criteria CPU utilization ➔ 최대한 사용 Throughput Turnaround Time (총 소요시간) Waiting Time Response time (CPU를 최초 얻을 때까지 걸린 시간) 스케줄링 알고리즘 🔹 nonpreemptive (비선점형) 🔹 preemptive (선점형) 🔸 ..

알고리즘/BOJ

[BOJ] 20058 마법사 상어와 파이어스톰 - Java

2024.03.01

✨ BFS + 구현 ➔ 부분 격자를 시계방향으로 90도 회전 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 📍 고려해야할 점 2^L * 2^L 크기의 부분 격자로 나누고 모든 부분 격자를 시계방향으로 90도 회전 L=1일 때, 2x2의 부분격자가 시계방향으로 90도 회전 L=2일 때, 4x4의 부분격자가 시계방향으로 90도 회전 (x, y)칸에서 인접한 칸(상하좌우) 중 얼음이 있는 칸이 3개 미만이면 (x, y)칸 얼음의..

CS/⚙️ 운영체제

[⚙️ OS] Thread

2024.02.29

스레드 스레드 프로세스 내부에 있음. 한 개의 프로세스가 여러 스레드를 가질 수 있음 ➡️ concurrency 병렬처리 스레드끼리 address space, resource 공유 멀티 스레드 modern OS embedded systems multi-core processors network servers 🔹 Multiple Threads 각 thread는 별개로 실행 Memory와 I/O state은 공유 thread 1에서 thread 2로 context switching이 일어나면 thread1이 가지고 있던 register set을 CPU state에 저장 thread2의 CPU state을 register set에 load Hyper-Threading : Context switching ove..

CS/⚙️ 운영체제

[⚙️ OS] Process

2024.02.27

프로세스 🔹 프로세스 코드의 일부. 실행 중인 프로그램 자기 독립적인 resource 가짐. single address space ➡️ protection 다른 프로세스와 공유 X 🔹 특징 프로세스 각각 고유의 스택 메모리 보유 고유의 메모리 페이지 보유 고유의 file descriptor table 보유 PID (Process ID) 🔹 프로세스의 Context CPU 수행 상태를 나타내는 하드웨어 문맥 Program Counter register 프로세스 주소 공간 code data stack 프로세스 관련 커널 자료구조 PCB Kernel Stack 🔹 프로세스 생성 자식은 부모의 공간을 복사해 그 공간에 새로운 프로그램을 올림 트리(계층 구조) 형성 fork() 시스템콜을 통해 자신과 동일한 프로..

전체 글

LCS (최장 공통 부분 수열)

[⚙️ OS] 프로세스 간 통신 (IPC: Inter-Process Communication)

[⚙️ OS] 프로세스 동기화

[프로그래머스] 단어 변환

[⚙️ OS] CPU 스케줄링

[BOJ] 20058 마법사 상어와 파이어스톰 - Java

[⚙️ OS] Thread

[⚙️ OS] Process

티스토리툴바