Programming/PS
-
백준 1715번 카드 정렬하기: C++ 풀이Programming/PS 2024. 5. 1. 17:09
백준 1715 카드 정렬하기 문제의 C++ 해설입니다.우선순위 큐(최소 힙)를 사용한 일반적인 풀이와 배열을 사용한 더 효율적인 풀이, 두 가지 방법을 설명합니다.백준 13975 파일 합치기 3 와 유사한 문제입니다.기본 접근: 우선순위 큐 활용비교 횟수 최소화 전략제시문에서도 언급하듯, 카드 묶음을 고르는 순서에 따라 비교 횟수가 매우 달라진다.카드를 합치며 묶음 크기가 누적으로 더해지기 때문이다.큰 값을 누적으로 더하는 것 보다, 작은 값을 누적으로 더하는 게 좋다.따라서 비교 횟수 최소화를 위해 현재 카드 묶음 중 크기가 가장 작은 두 카드 묶음을 먼저 합쳐야 한다.우선순위 큐를 사용하는 이유와 시간 복잡도카드를 저장하기 위해 일반적인 배열을 사용한다고 생각해보자.배열을 정렬하면 크기가 가장 작은 ..
-
백준 7562번 나이트의 이동: C언어 풀이Programming/PS 2024. 2. 28. 02:40
백준 7562 나이트의 이동 문제의 C언어 해설입니다.일반적인 BFS 구현에서 시작해, 체스판 크기를 조작해 실행 시간을 최적화 하는 과정을 단계적으로 설명합니다.기본 접근: BFS를 이용한 나이트의 이동 구현나이트의 처음 시작 포지션을 큐에 넣는다. 움직일 수 있는 8가지 경우의 수에 대해 BFS를 돌려준다.목표 지점에 도달하기까지의 소요 시간은 매 iteration 마다 큐의 크기 만큼만 pop 하는 것으로 계산할 수 있다. 구현 코드#include #define MAX_BOARD_SIZE 300#define VISITED 1struct position{ short row, col;};struct board{ int cells[MAX_BOARD_SIZE][MAX_BOARD_SIZE]; ..
-
백준 이항 계수 시리즈 풀이 (이항 계수 2, 이항 계수3, 이항 계수와 쿼리)Programming/PS 2024. 2. 27. 00:53
백준 11051번 이항 계수 2, 11401번 이항 계수 3, 13977번 이항 계수와 쿼리 문제에 대한 C언어 해설입니다.페르마의 소정리로 모듈러 곱셈 역원을 구하고, 거듭제곱을 최적화하여 큰 수의 이항 계수를 효율적으로 계산하는 방법을 단계적으로 설명합니다.11051 이항 계수 2백준 11051번 이항 계수 2자료 구조 말고 다른 유형도 풀어볼까 하다가 마주친 문제 문제를 풀기 위해서 이항 계수의 정의에 따라 다음을 계산해야 한다.${n \choose k} = \frac{n!}{r!(n-r)!}$문제는 입력 결과값이 엄청 크다는 것이다.n = 1000, k = 500 일때 결과값만 해도 $10^{299}$ 를 넘는다.C의 unsigned long long 값, $2^{64}- 1$ 을 아득히 초월하..
-
백준 9934번 완전 이진 트리: C언어 풀이Programming/PS 2023. 10. 25. 17:39
백준 9934 완전 이진 트리 문제의 C언어 해설입니다.트리를 직접 구현하는 방법 대신, 중위 순회 결과가 저장된 배열에서 층별 순회 결과를 수학적으로 도출하여 해결하는 방법을 설명합니다.전략트리 만들지 않기트리를 구성해서 bfs를 하면 간단한 문제이다.근데 그냥 빌딩 번호가 저장된 배열을 층별 순회 순서대로 출력하면 더 간단하지 않을까?중위 순회 순서대로 저장된 배열을 층별로 읽을 수 있는 어떤 적절한 규칙이 분명 있을 것이다 라고 생각했다.그렇게 노트랑 팬 들고 삽질하면서 다음 규칙을 찾았다.level 3의 첫 번째 노드 왼쪽에는 깊이가 2인 포화 이진 트리가 존재한다.level 3의 각 노드 사이에는 깊이가 3인 포화 이진 트리가 존재한다. 중위 순회 결과는 왼쪽부터 순서대로 배열에 저장되어 있다..
-
백준 3190번 뱀: C언어 풀이Programming/PS 2023. 10. 15. 03:47
백준 3190 뱀 문제의 C언어 해설입니다.뱀을 덱 자료구조를 사용해 모델링하고, 타일의 상태와 뱀의 방향 전환을 구현하기 위한 전략을 설명합니다. 전략뱀을 덱으로 구성한다.뱀이 이동 할 때마다 머리/꼬리에서 삽입/삭제가 발생한다.따라서 뱀을 덱으로 구성하는 게 합리적이다. 덱의 원소는 NxN 보드 위 타일을 가르키는 포인터로 두었다.보드 위의 좌표(i, j)를 저장하는 것보다 직관적인것 같다.타일의 구성타일은 다음과 같은 4가지 상태 중 하나를 갖는다. 평원: 아무것도 없는 기본 상태이다.사과: 여기에는 사과가 놓여있다.뱀: 여기에는 뱀이 놓여져있다. 공허: NxN 보드의 바깥 공간을 의미한다. 이를 전부 enum으로 정의하기로 한다.여기서 굳이 4번, 공허 타일을 추가한 이유는 경계값 처리를 간단..
-
백준 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..