Programming
-
백준 11003번 최솟값 찾기: C언어, Python 풀이Programming/PS 2023. 10. 15. 00:12
백준 11003 최솟값 찾기 문제의 해설입니다.슬라이딩 윈도우 크기로 관리되는 덱을 오름차순으로 유지하고, 같은 값을 그룹화하여 각 구간의 최솟값을 시간복잡도 O(1)에 찾는 최적화 방법을 설명합니다.최종 코드는 C와 파이썬으로 작성되었습니다.전략오름차순 덱?히스토그램 문제 와 거의 완벽히 똑같다. L = 6 인 상황을 생각해보자.$A_{i-5}$ 부터 $A_i$ 까지, 6개의 숫자 중 최솟값이 $D_i$가 된다.이제 가상의 6칸 저장소에 $A_{i-5}$ ~ $A_i$ 까지 숫자를 저장하고 관리한다고 생각해보자.$A_1$ 부터 $A_6$ 까지 각각 1, 2, 3, 5, 6, 7 이라고 해보자.우리의 6칸 저장소에도 역시 1, 2, 3, 5, 6, 7이 들어가 있다. $D_6 = 1$이 되겠다.$A_7..
-
백준 5430번 AC: C언어, Python 풀이Programming/PS 2023. 10. 14. 23:54
백준 5430 AC 문제의 C언어, 파이썬 풀이입니다.덱을 이용한 풀이로, 배열의 뒤집힘 상태와 입출력 방안에 대한 설명을 담고 있습니다.Python만 보기전략상태 변환 방법배열이 뒤집혀 있으면 뒤에서 빼고, 뒤집혀 있지 않으면 앞에서 빼면 된다.양쪽에서 삭제가 가능해야 하니 덱을 사용하면 된다.상태는 뒤집혀진 상태를 1 일반 상태를 0으로 둔다.XOR 연산을 통해 상태 전환, 토글이 가능하다.if (functions_buffer[i] == REVERSE){ // Switch state state = state ^ 1;}// Deleteelse { // Reversed: 1, Normal: 0 head += state ^ 1; tail -= state;} 입력 받기입출력이 생..
-
백준 1158번 요세푸스 문제: C언어 풀이Programming/PS 2023. 10. 14. 18:46
백준 1158번 요세푸스 문제 의 C언어 해설입니다.원형 큐를 이용한 구현 방식과 일반적인 일차원 배열을 이용한 구현 방식을 다루고, 두 방식의 성능 차이를 설명합니다.큐를 만들어 회전하는 구현원형 큐를 정의한다. k - 1번 우측으로 회전하고 인간을 POP, 제거 해준다.사람 수 만큼 회전하면 한 바퀴 돌아서 제자리로 돌아오게 된다.즉, 회전 수가 사람 수보다 많으면 불필요한 회전을 더 하는 셈이다.따라서 회전 수를 크기만큼 나눈 나머지를 사용한다.코드#include #define MAX_SIZE 8192#define REMAINDER_MASK 8191int main(void){ int num_people; int interval; scanf("%d %d", &num_people, &i..
-
백준 2346번 풍선 터뜨리기: C언어 풀이Programming/PS 2023. 10. 14. 17:02
백준 2346 풍선 터트리기 문제의 C언어 해설입니다.큐의 회전을 구현하는 방법과 이에 대한 수학적인 설명을 다룹니다.전략큐의 회전 구현하기1021번 회전하는 큐 문제와 마찬가지로 큐에서 풍선을 POP 하고, 안에 든 숫자만큼 큐를 회전 시켜주면 된다. 숫자가 음수라면 왼쪽으로 회전해야한다. 역시 앞선 문제에서 아이디어를 가져온다.전체 풍선 수가 10개라면 왼쪽으로 4번 회전 대신 오른쪽으로 6번 회전해주면 된다.풍선 수에서 좌측 회전 횟수를 빼주면 필요한 우측 회전 횟수가 나온다.단 단순 뺼셈으로는 곤란한 경우가 있다. 회전 횟수가 전체 풍선 수보다 많은 경우이다.풍선 수가 10, 쪽지에 적힌 수가 -12인 상황을 생각해보자.단순히 풍선 수에서 회전 횟수를 빼줄 경우 10 - 12 = -2, 음수가 ..
-
백준 1021번 회전하는 큐: C언어 풀이Programming/PS 2023. 10. 14. 14:09
백준 1021 회전하는 큐 문제의 C언어 해설입니다.큐의 회전을 구현하는 방법과, 문제에서 필요한 배열의 크기를 계산하는 방법을 설명합니다.전략큐의 회전 횟수를 어떻게 구할 수 있을까?처음엔 직접 회전을 구현하지 않고, 문제에 필요한 최솟값만 산출하는 방법을 잠깐 고민해봤다.시행착오 끝에, 입력 값 크기도 작겠다, 그냥 정직하게 회전을 구현하기로 했다. 오른쪽 회전의 구현은 간단하다. 큐에서 뽑은 원소를 다시 넣어주기만 하면 끝이다.왼쪽 회전의 구현은 해 줄 필요가 없다. 왼쪽 회전 횟수는 오른쪽 회전 횟수에서 유도할 수 있으니까.뽑아내려고 하는 수를 찾을 때 까지 오른쪽으로 회전하고, 회전 횟수를 센다.왼쪽 회전일 경우 "현재 원소 수" 에서 오른쪽 회전 횟수를 빼는 것으로 연산 횟수를 간단히 구할 수..
-
백준 2161번 카드 1: C언어 풀이Programming/PS 2023. 10. 8. 00:00
2161 카드 1 문제의 C언어 해설입니다.2의 거듭제곱 크기의 원형 큐와 비트 연산을 활용하여, 나머지 연산을 최적화한 구현 방법을 설명합니다.원형 큐 구현 최적화다른 코드 보다가 발견한 테크닉.원형 버퍼의 크기를 2의 거듭제곱으로 잡는다.head, tail 이 경계를 넘어갈때 나눗셈 대신 size-1(1로만 이루어진 비트열)과의 bitwise and를 통해 나머지를 훨씬 빠르게 구할 수 있다.멋있어 보여서 바로 적용했다. 코드#include #define MAX_DECK_SIZE 1024#define REMAINDER_MASK 1023int queue[MAX_DECK_SIZE];int main(void){ int num_cards; scanf("%d", &num_cards); for..
-
백준 24511번 Queuestack: C언어 풀이Programming/PS 2023. 10. 7. 23:34
백준 24511 Queuestack 문제의 C언어 해설입니다.복잡한 자료구조 시뮬레이션을 시간 초과 없이 해결하기 위해 스택을 무시하고 큐의 요소만을 처리하여 단순화하는 방법을 설명합니다.전략컨베이어 벨트문제에서 주어진 로직을 그대로 구현했더니 시간 초과가 났다. 복잡한 문제 지문을 단순화해서 생각해볼 필요가 있다.먼저 스택 안에 들어있는 원소는 고려할 필요가 없다.First in Last out, 스택을 나올 일이 없기 때문이다.큐에 들어있는 원소는 계속해서 오른쪽 큐로 이동한다.즉 처음 큐에 들어있는 원소는 계속해서 오른쪽 큐로 이동한다.마치 컨베이어 벨트처럼.즉 굳이 작동시켜보지 않아도 출력을 알 수 있다.가장 오른쪽 숫자부터 차례로 리턴 될 것이다.예시로 예제 입력 1을 보자40 1 1 01 ..
-
백준 1725번 히스토그램: C언어 풀이Programming/PS 2023. 9. 30. 23:36
백준 1725 히스토그램 문제 C언어 해설입니다.백준 6549 히스토그램에서 가장 큰 직사각형 문제와 거의 완벽히 동일한 문제입니다.오름차순으로 구성된 스택에 높이와 너비를 가지는 구조체를 저장하여 히스토그램내 직사각형의 최대 넓이를 구하는 방법을 상세히 설명합니다.전략오름차순 스택오아시스 재결합문제와 유사하다.막대 그래프를 높이와 너비를 가지는 구조체로 정의한다. 막대는 스택에 저장해준다.막대 하나의 너비는 1이고, 연속한 같은 높이의 막대는 그 만큼의 너비를 가진 하나의 막대로 취급한다.스택안에 높이 3, 5, 6, 7인 막대들이 들어가 있다고 하자.이후 높이 4인 막대가 나타나면, 3과 4 사이 5, 6, 7은 더 이상 새로운 직사각형을 만드는 데 기여하지 못한다.정확히는 5, 6, 7에서 높이 4..