본문 바로가기

CS

 (43)
[정처기] 정처기 합격 후기 및 팁! 정처기는 필수는 아니지만 있으면 좋다라는 말을 들어서 딸 생각이 없다가 급하게 따고 싶은 마음이 생겨 준비했고 드디어 합격했습니다!만약 고민하시고 계신 분들이 있다면 따는 것을 추천드립니다.   정처기는 필기와 실기로 나뉘는데요, 필기는 모든 문제가 선택형이고 실기는 모든 문제가 서술형입니다. 그리고 필기를 합격해야만 실기를 응시할 수 있는 자격이 주어지며, 필기 합격 2년 이내에 실기를 합격해야 정처기 자격증을 최종적으로 얻을 수 있습니다.  저는 5월 10일에 필기를 응시했고 7월 29일에 실기를 응시했습니다. 각각 어떻게 준비했는지 꿀팁을 알려드리겠습니다! 1) 필기 준비 당시 저는 시험까지 일주일밖에 남지 않은 상황이었습니다. (취소 자리 잡을 때 서울에 자리가 없어 대전에서 시험을 보게되었어요ㅜ..
[백준] 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 이다.) ✔️힙 조건 : 각 노드의 우선 순위가 자식 노드의 우선순위보다 높거나 낮을 때 ✔️힙 종..

티스토리툴바