본문 바로가기

BOJ

[백준 C++] 1890 점프 점프 (0, 0)에서 (N - 1, N - 1)로 가는 경로의 수를 파악하는 문제다. 각 칸에는 그 칸으로부터 몇 칸을 움직일 수 있는지 정해져있으며, 오른쪽이나 아래로만 움직일 수 있다. 한 번에 움직일 수 있는 거리는 0보다 크거나 같고, 9보다 작거나 같다. 한 번에 움직일 수 잇는 거리가 0이 될 수도 있다는 점을 못봐서 한번 틀렸었다.(메모리 초과)또한 가능한 경우의 수가 최대 $2^{63} - 1$이라고 제한을 줬으며, 중간값이 이 값보다 커질 가능성은 없으므로 cache는 long long 타입으로 해도 충분했다.그 이외에는 주의할 사항이 없다. 123456789101112131415161718192021222324252627#include using namespace std;#define ..
[백준 C++] 피사노 주기와 행렬 제곱을 활용한 피보나치의 수 구하기 피보나치 수 3피보나치 수 6 백준 블로그를 참고했다. N 번째의 피보나치 수를 구해야 할 때 N 의 수가 충분히 작다면 재귀함수나 반복문, 메모이제이션을 활용해서 문제를 풀면 된다. 하지만 '피보나치 수 3' 나 '피보나치 수 6' 처럼 N의 범위가 1,000,000,000,000,000,000 까지라면 위에서 언급한 방법으로는 시간을 맞출 수 없다. 그래서 두가지 방법을 활용할 수 있는데 하나는 '파사노 주기이며 다른 하나는 행렬의 제곱이다. 피보나치 수 3피보나치 수 3은 N의 범위가 1,000,000,000,000,000,000 까지고 결과값을 1,000,000으로 나눈 값을 출력해야 한다. 피보나치 수를 M 으로 나눈 수는 항상 주기를 가지게 되는데, 이를 피사노 주기(Pisano Period)..
[백준 C++] 1021, 5430번 회전하는 큐, AC 회전하는 큐AC 어제에 이어서 이중 연결 리스트로 문제를 풀어봤다. 이제 어느정도 감이 잡혔다. 이중 연결 리스트를 만들 때 head 와 tail 을 꼭 초기화시켜 줘야한다. 그리고 노드끼리 연결이 잘 되어있는지 확인 또 확인해야한다. 마지막으로 head 와 tail 에는 데이터가 저장되어있지 않으면 데이터를 출력할 때 head 와 tail 의 데이터는 출력하지 않도록 주의 해야한다. 회전하는 큐코드를 작성하기 전에 어떻게 풀지 생각해놓고 풀었고, 그대로 작성하니 맞았다. 노드가 10 개 있을 경우에는 head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - tail 과 같이 작성했다. 시작할 때 currNode 는 head 이며, currNode 를 기준으로 오른쪽으로 가야..
[백준 C++] 10866, 1406번 덱, 에디터 덱에디터 이중 연결리스트를 공부하려고 푼 문제다. 에디터 문제를 먼저 풀었는데 정말이지 죽을 뻔 했다. Node 의 previous Node 와 next Node 를 모두 연결하는 작업이 너무 헷갈리기도 했고, 실수도 많이 할 수 밖에 없는 자료구조인 것 같다. 그래도 에디터 문제를 풀면서 Node 들과 씨름을 하다 보니 좀 익숙해져서 덱 문제는 훨씬 쉽게 풀었다. 덱덱 문제는 사실 STL 에 있는 것을 가져다와서 사용해도 되는데 처음부터 STL 에 길들여지면 안될 것 같아서 직접 구현하려고 마음먹었다. 이중 연결리스트로 구현할 수있다는 말을 듣고 이중 연결 리스트를 공부해보기로 했다. 사실 덱을 위한 이중 연결리스트는 중요한 기능이 빠져 있다. 에디터 문제에서도 나오겠지만 이중 연결리스트는 그 이름 답..
[백준 C++] 2054번 괄호의 값 괄호의 값 한 시간 안에 푸는 연습을 했는데 정신을 차리고 보니 네 시간이 지나 있었다. 전에 괄호로 이루어진 문자열이 올바른 괄호 문자열인지 판단하는 문제가 있었는데 그 문제를 조금 더 심화시킨 문제다. 그 문제에서는 '(' 와 ')' 만 쓰였다면, 이 문제에서는 '(', ')', '[', ']' 가 쓰인다. 또한 괄호의 조합에 따라 계산을 또 해야해서 문제 자체는 재미있었지만 복잡했다. 문제를 풀고 다른 사람의 풀이를 보니 나처럼 푼 사람이 잘 없어서 좀 자세하게 남기고자 한다. 표로 이해하는 게 더 쉬울 것 같다. 표를 보자. 1. 스택을 두 개 선언했다. 하나는 괄호를 쌓는 곳, 나머지 하나는 계산 결과를 담고자 만든 것이다. 두 번째 설명이 좀 애매한데 예를 들어, 예제 입력 1에서 $(()[[..
[백준 C++] 6591, 9375번 이항 쇼다운, 패션왕 신혜빈 이항 쇼다운 언뜻 보면 쉬워 보이면서도 수상쩍은 조건이 있다. 입력되는 두 수는 $2^{31}-1$을 넘지 않으며, 정답이 $2^{31}$보다 작은 경우만 입력으로 주어진다고 한다. $2^{31}-1$은 int형 자료형이 가질 수 있는 최대치이다. int 자료형을 쓰도록 유도하는 함정이라고 생각한다. 하지만 계산 중에 나오는 값이 int 자료형의 범위를 넘을 수 있으며, 이런 경우는 오버플로우 되므로 틀린다고 나올 것이다. 그것만 빼고는 따로 주의할 점이 없다. 123456789101112131415161718#include using namespace std;typedef long long ll;int main() { int n, k; while (1) { cin >> n >> k; if (n == 0..
[백준 C++] 11050번, 11051번, 11401번 이항계수 1, 2, 3 이항 계수 1이항 계수 2이항 계수 3 비록 문과생이지만 나름 수학에 자신있던 편이었어서 쉽게 풀 줄 알았다가 이틀동안 개고생을 했다. 페르마의 소정리, 확장 유클리드 알고리즘, 나머지 연산 등등... 아는 걸 찾는게 빠를 정도로 다 몰랐다. 이번 기회에 이항 계수 문제를 푸는 몇가지 알고리즘을 정리해야겠다는 생각을 했다. 이항 계수는 고등학교 수학 과정에서, 그리고 대학교 통계 수업에서 배웠던 걸로 기억한다. 이항 계수란 n 개의 원소에서 r 개를 뽑아내는 방법의 수를 의미한다. 보통 nCr 의 형태를 띄고 있으며, 계산을 할 때는 다음과 같이 했던 것으로 기억한다. $$\binom{n}{r} = \left( \frac{n!}{r!(n - r)!} \right)$$ 1. 이항 계수 1 이항계수 1은 다..
[BOJ C++] 1874번 스택 수열 스택 수열 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 먼저 들어간 자료가 제일 나중에 나오는 (FILO, first in last out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,00..

티스토리툴바