본문 바로가기

CS

 (44)
[백준] 26009 험난한 등굣길 https://www.acmicpc.net/problem/26009 💡문제 분석 요약출발지점이 주어지고 도착지점까지 최단 시간에 가는 방법구하기이때, 장애 구간을 피해서 가야한다.장애지점(Ri, Ci)과 거리(Di)가 각각 주어진다.→ (Ri, Ci)로부터 거리가 Di 이하인 거리가 모두 장애 지점이 된다.이때, 두 칸 (R1, C1), (R2, C2)사이의 거리는 |R1 − R2| + |C1 − C2|와 같다.[입력 조건]첫째 줄에 격자의 크기 N, M이 주어진다. (2 ≤ N, M ≤ 3,000)다음 줄에 정체 구역의 수 K가 주어진다. (1 ≤ K ≤ 3,000)다음 K개 줄에 걸쳐 각 정체 구역의 정보 Ri, Ci, Di가 주어진다. (1 ≤ Ri ≤ N, 1 ≤ Ci ≤ M, 0 ≤ Di ≤ ..
[백준] 가희와 은행 22234 (라운드로빈) https://www.acmicpc.net/problem/22234💡문제 분석 요약상황은행원이 있고 은행 업무를 처리하기 위한 사람들이 여러 명있다.들어온 순서대로 처리하며 이때, 다 업무를 처리하지 못한다면 다시 줄을 서야한다.출력0~W-1초 동안에 각 초에 어떤 사람의 업무를 보고 있었는지 id를 출력한다.이 문제는 매우 좋은 문제인 것 같다. 왜냐하면 OS에 나오는 CPU 스케줄링 방식 중 라운드로빈 방식과 매우 유사하며 이를 구현하기 위한 로직을 생각해보는 문제이기 때문이다.모든 사람들에게 업무를 처리할 수 있는 일정한 시간이 똑같이 주어지고 그 시간 안에 해야하는 업무들을 다 끝내지 못한다면 다시 큐에 들어간다는 점이 “라운드로빈”과 유사하다. 참고) CPU 스케줄링이란?프로세스들은 CPU를 ..
[스택] Monotonic Stack 👉 Monotonic Stack 이란? : 스택의 원소들을 오름차순 혹은 내림차순 상태로 유지하도록 하는 알고리즘 단조(monotonic)는 수학 함수에 사용되는 용어이다.함수 y = f(x)가 다음 조건을 따를 때 단조 증가 또는 단조 감소하는 것으로 간주됩니다x가 증가함에 따라 y도 항상 증가 -> 단조 증가 함수 x가 증가함에 따라 y가 항상 감소 -> 단조 감소 함수  ☑️ 2가지 상황에 사용 가능 -> 1) 배열 특정 위치에서 정렬된 숫자들만 보고 싶을 때 -> 2) 배열 특정 위치에서 바로 다음 큰 값(or 작은 값)을 보고 싶을 때  만약 브루트포스로 한다면 O(N^2)이 될 것이다. 하지만 모노토닉 스택을 사용한다면 O(N)으로 시간복잡도를 줄일 수 있다!  👉..
[백준] 1158 요세푸스 💡문제 분석 요약 https://www.acmicpc.net/problem/1158 1부터 N번까지 원을 이루어 앉아있다. 모든 사람이 없어질 때까지 순서대로 K번째 사람을 삭제하기 [제약 사항] 전체 인원은 (1 ≤ K ≤ N ≤ 5,000) 💡알고리즘 설계 큐를 사용한 방법 전체 사람의 수만큼 반복하면서 계속 0~삭제할 인덱스반복하며 삭제할 인덱스가 아니라면 큐에 다시 넣고 삭제할 인덱스 순서가 되면 값을 넣지 않고 출력한다. 큐에 다시 순서대로 넣고 넣은 순서대로 다시 poll을 할 수 있으니 이 과정을 통해 사람이 원으로 앉았다는 것을 구현할 수 있다. 연결리스트를 사용한 방법 리스트 중간의 요소들을 삭제하는 것이 빈번하므로 연결리스트 선택 사람의 수만큼 반복문을 돌면서 삭제할 index를 모듈러..
[알고리즘] stack 문제 비교 (백준 - 2493, 17298, 6198) 아래의 백준 문제는 스택에 관련된 문제입니다. 비슷한듯 접근 방법이 달라 비교하여 정리했습니다! 스택은 언제 사용할까? 💡 2중 for문으로는 시간 초과가 날 것 같을 때 → O(n)에 가까이 갈 수 있도록 하는 스택! 탑 (레이저) 문제 = 뒤에서 봤을 때 나보다 큰 수 하나 방향 = ← 뒤에 애들이 나보다 작으면 어차피 가려지므로 의미없음 from collections import deque n = int(input()) top = list(map(int, input().split())) stack = [] answer =[0] * n cnt = 0 for i in range(n): while stack: if stack[-1][1] < top[i]: stack.pop() else: answer[i]..
[백준] 25418 정수 a를 k로 만들기 https://www.acmicpc.net/problem/25418 문제 분석 [ 문제 설명 ] 입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다. 연산 1: 정수 A에 1을 더한다. 연산 2: 정수 A에 2를 곱한다. 정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자. [ 입력 ] 첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다. [ 출력 ] 첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다. 제한 1 ≤ A 1을 더하기 #연산 2 => 2를 곱하기 A, K = map(int, input().split()) coun..
동기식 입출력과 비동기식 입출력 동기식 입출력과 비동기식 입출력 [ 동기식 입출력 ] 현재 CPU를 잡은 프로세스가 IO 요청을 하게 되면 IO가 끝날 때까지 그 프로세스의 후속 명령을 수행하지 않는 입출력 방식 서로 보조를 맞출 때까지 기다림 IO 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감 2가지 구현 방식 IO 가 끝날 때까지 계속 가지고 있고 완료될 때까지 기다림 CPU를 낭비시킴 → CPU를 계속 잡고 있음 매 시점 하나의 IO만 일어날 수 있음 결국, IO 장치와 CPU 이용률이 크게 저하된다. → 그래서 2번 방식으로 구현한다. 빼앗는 방법 IO가 완료될 때까지 해당 프로세스(오랜 시간이 걸리는 IO)에게서 CPU를 빼앗아 block 상태에 놓은 후 → 당장 명령을 수행할 수 있는 ready 상태의..
Chap 7_2. 프로세스 PCB(process Control Block) = 운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보 다음의 구성 요소를 가진다 (구조체로 유지) (1) OS가 관리상 사용하는 정보 • Process state(프로세스 상태 = ready, blocked) , Process ID • scheduling information, priority(CPU 우선순위 값을 두어서 운영한다) pointer를 통해 여러 PCB들을 연결할 수 있다. (줄 서있는 모습을 구현) (2) CPU 수행 관련 하드웨어 값 • Program counter, registers 프로세스의 문맥을 파악하기 위함 (어떤 값이 프로세스에 있었는지) program counter는 현재 메모리에 어떤 부분을 수행하고 있는지 가리..
Chap 6-5. 힙 정렬(Heap Sort) 먼저, 힙이라는 자료구조에 대해서 알아보고 이를 이용한 정렬 방법에 대해 알아보자! 힙(Heap)을 공부할 때 항상 가수 마마무의 노래 중 힙(HIP)이 생각난다 ㅎㅎ 배경음악으로 틀고 공부해보자...ㅎ 😎힙(heap)이란? 힙 ("이진 힙"이라고도 한다)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위하여 고안된 완전 이진 트리(Complete Binary Tree)를 기본으로 한 자료구조이다. 힙이라고 하는 것은 우선순위큐를 구현하기 위해 만들어진 데이터 타입이라고 할 수 있다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.(빠르다니.. 완전 HIP한 Heap 이다.) ✔️힙 조건 : 각 노드의 우선 순위가 자식 노드의 우선순위보다 높거나 낮을 때 ✔️힙 종..
Chap 6-4. 쉘 정렬(Shell Sort) 🌈Shell 정렬이란? 쉘은 ‘Donald L. Shell’이 제안한 방법으로 “쉘 정렬”이라고 한다. 다른 정렬 방법들은 정렬 방식이 이름이지만 이것은 만든 사람의 이름이라는 점에서 차이가 있다. 여러 가지 정렬 방법들을 배우는데 이름과 방법이 매치가 되지 않는다. 그래서 본인은 정렬 방식이 이름에 표면적으로 드러날 수 있도록 “Gap 삽입 정렬”이라고 자의적으로 생각해봤다.(일명 뇌피셜이라 할 수 있다.. ㅎ) ✔️방법 : 전체 리스트를 일정 간격(gap)의 부분 리스트로 나눈다. -> 나누어진 각각의 부분 리스트를 insertion sort 수행한다. (부분 리스트 별로 sort를 수행한다) 🌈motivation ✔️버블 정렬이나 삽입 정렬이 수행되는 과정은 ”기껏해야” 이웃하는 원소의 자리바꾸는 ..

티스토리툴바