Programming/PS
-
백준 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..
-
백준 3015번 오아시스 재결합: C 언어 풀이Programming/PS 2023. 9. 30. 22:49
백준 3015 오아시스 재결합 문제의 C언어 해설입니다.내림차순 스택을 이용한 구현에서, 시간 초과를 해결하기 위해 키가 같은 사람들을 하나의 구조체로 묶어서 처리하는 방법을 설명합니다.최종 코드는 C언어와 파이썬, 두 언어로 작성하였습니다.전략역시나 내림차순 스택오큰수 문제 와 유사한 문제다.스택에 사람들의 키를 하나씩 저장한다.스택은 항상 내림차순으로 정렬되어 있다고 가정한다.내림차순이 깨지는 순간을 살펴보자. 9, 8, 3, 2 다음 7이 나온 상황이다.키가 7인 사람과 스택안에 있는 사람들, 8, 3, 2는 서로 마주 볼 수 있다.7이 가로막기 때문에, 이후 어떤 숫자가 나오든 3, 2의 키를 가진 사람은 이후 사람을 볼 수 없다.이게 뭔가 직관적으로 생각해보면 조금 이상한 면이 있다.이를테면 키..
-
백준 2493번 탑: C언어, 파이썬 풀이Programming/PS 2023. 9. 30. 03:47
백준 2493 탑 문제 해설입니다.내림차순으로 구성되는 규칙을 가진 스택과 더미 데이터를 활용한 구현을 설명합니다.C언어와 파이썬, 두 언어로 최종 코드를 작성하였습니다.전략저번 오큰수 문제와 유사하다.이번엔 좌큰수를 찾는 문제라고 봐도 무방하다.또 탑의 높이가 아닌, 탑의 번호(위치)를 출력해야하는 점이 다르다.내림차순 스택스택에 탑의 높이를 저장한다. 스택은 항상 내림차순으로 정렬되어 있다고 가정한다.내림차순이 깨지는 순간을 살펴보자 7, 5, 3, 2 다음 4가 나왔다.이제 3, 2의 높이를 가지는 탑은 신호를 받을 수 없다. 4가 막고있기 때문이다.3, 2를 스택에서 없애준다. 스택에는 7, 5 가 남아있다.4의 신호를 받는 탑은 5이다. 이제 4를 스택에 넣어준다.물론 출력 값은 탑의 높이가 아..
-
백준 17298번 오큰수: C언어 풀이Programming/PS 2023. 9. 30. 02:03
백준 17298 오큰수문제의 C언어 해설입니다.내림차순 스택을 활용한 문제 풀이 방법과 이를 최적화하는 과정을 설명합니다.최종 코드로 파이썬 버전을 추가하였습니다.기본 접근: 내림차순 스택 구현내림차순 스택으로 오큰수 찾기스택에 수열의 원소를 하나씩 저장한다.스택은 항상 내림차순으로 정렬되어 있다고 가정한다. 내림차순이 깨지는 순간을 살펴보자. 8, 5, 3, 2 다음 7이 나온 상황이다.5, 3, 2의 오큰수는 7이다. 오큰수를 알아냈으니 스택에서 그냥 없애고 7을 넣어준다.스택에는 8, 7이 남게 되고 내림차순이 유지된다.인덱스를 저장해서 순서 처리하기문제는 순서다.위 예시를 다시 보자. 8, 5, 3, 2 에서 5, 3, 2의 오큰수가 7임을 알아냈다.한편 8의 오큰수는 아직 모른다. 즉 수열의 순..