본문 바로가기

CS/알고리즘

 (27)
[백준] 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..
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 ✔️버블 정렬이나 삽입 정렬이 수행되는 과정은 ”기껏해야” 이웃하는 원소의 자리바꾸는 ..
Chap 6-3. 삽입 정렬(insertion sort) 삽입 정렬이란? 배열을 정렬된 부분(앞부분)과 정렬 안 된 부분 (뒷부분)으로 나누고, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복 즉, 정렬 안 된 부분에서 하나씩 꺼내서 정렬된 부분에 있는 것들과 비교한다. 자신보다 작은 원소를 발견할 때까지 왼쪽 방향으로 이동한다. 자신보닥 작은 원소 바로 뒤에 삽입된다. → 정렬 안 된 부분의 원소가 정렬된 부분에 삽입되어 정렬된 부분의 그룹의 수가 1개 늘어나고, 정렬이 안 된 부분의 원소의 수는 1개 줄어든다. 결과= 이를 반복하여 수행하면, 마지막엔 정렬이 안 된 부분엔 아무 원소도 남지 않는다. + 모두가 정렬된 상태가 된다. 가정 = 정렬은 배열의 첫 번째 원소만이 정렬된 부분에 있는 상태에서 정..
Chap 6-2. 선택 정렬(selection sort) 선택 정렬이란? 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여, 배열의 1번 원소와 자리를 바꾼다. -이러한 방식으로 마지막에 2개의 원소 중 작은 것을 선택하여 자리를 바꾼다. [의사코드] 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A 1. for i = 0 to n-2 //n-1로 한다면 j = i+1 => j = n -1 +1 = n이 되므로 배열을 벗어난다. 2. min = i //최솟값의 인덱스 3. for j = i+1 to n-1 // A[i]~A[n-1]에서 최솟값을 찾는다. 4. if A[j] < A[min] 5. min = j //작은 부분으로 업데이트 하자 6. A[i] ↔ A[min] // ..

티스토리툴바