티스토리

무지성 PS

검색하기

블로그 홈

무지성 PS

sorryhyeon.tistory.com/m

세상에 못 푸는 문제는 없다. 내가 못해서다.

구독자: 2

방명록 방문하기

주요 글 목록

골드 이상 풀이 정리 2주차 1. 숫자 연결하기 (BOJ 1323)pigeonhole principle 언제 한번 순환소수 구할 때 나눗셈을 해본 적이 있다면 좋은 아이디어를 떠올릴 수 있다.1. 수를 계속 추가하면서(순환소수라면 0이었고, 이 문제에서는 N이다.) K로 나눠서 나머지를 알아낸다. 그후 그 나머지+N(여기선 문자열 연산이라 생각)을 다시 합쳐서 K로 나눈다.2. 계속 하다보면 언젠가 반복되었다.즉, 예제를 생각해보면 2%9=2 -> 22%9 -> 42%9 -> 62%9 -> ... 이런 식으로 계속 연산해준다. K로 나눈 나머지는 반드시 0~K-1이므로 비둘기집 원리에 따라 최대 K번 안에 반복된다. 같은 나머지가 나왔는데도 나머지가 0으로 안 나온다면 영원히 못 나누므로 -1을 출력하고 아니면 횟수를 출력하면 된다.. 공감수 0 댓글수 0 2024. 11. 5.
골드 이상 풀이 정리 1주차 1. 동전 (BOJ 9084)dp, knapsack 동전 하나를 잡고 그 동전의 값 이상부터 n까지 이전 값을 불러오면 된다. 당연히 0원은 무조건 만들 수 있으니 1로 초기화 해서 시작하면 된다. 2. 겹치는 선분 (BOJ 1689)sweeping, sorting imos법 같이 돌리면 된다. 즉, 시작 점은 1로 두고, 끝 점은 -1로 둬서 점의 위치를 중심으로 정렬해준다.예를 들어 (1, 5), (3, 6), (2, 3)가 있으면 (1, 1), (2, 1), (3, -1), (3, 1), (5, -1), (6, -1)로 될 것이다. 그리고 좌표 하나하나씩 순서대로 확인해서 변수에 +1, 혹은 -1을 하고 최댓값을 갱신하면 된다. 당연히 -1이 1보다 작으므로 먼저 계산되기 때문에 '선분의 끝 점에서.. 공감수 0 댓글수 0 2024. 10. 27.
[BOJ][Python] 백준 32454번 - Fibonacci Lucky Numbers 문제 링크: https://www.acmicpc.net/problem/32454 문제 풀이피사노 주기, 오일러 피 함수, 분할 정복을 이용한 거듭제곱 일단 $7^{7^{7^n}}$을 먼저 보면 벌써부터 답이 없어지는데, 이 수는 매우 크기 때문에 사실상 직접 구하는 것은 불가능하다. 그래서 접근하기가 힘든데, $7^{7^{7^n}}$번째 피보나치 수를 $10$번째 자리까지 출력하라고 적혀있다. 이 말은 피보나치 수를 구했을 때 $10^{10}$으로 나눈 값만 구하면 된다. 그렇다면 여기서 떠올리는 게 있다면 쭉쭉 풀려질 것이다. 피사노 주기를 이용하면 된다. 피보나치 수에서 나누는 값이 $10^{m} (m > 2)$라면 주기는 $15 \times 10^{m-1}$다. $m = 10$이므로 주기는 $15 .. 공감수 0 댓글수 0 2024. 10. 25.
[BOJ][Python] 백준 32242번 - $Axy+Bx+Cy+D=0$ 문제 링크: https://www.acmicpc.net/problem/32242문제 풀이폴라드 로, 정수론 처음에는 서브테스크로 나눠서 생각을 해봤는데, $A$가 0이냐 0이 아니냐를 기준으로 나눠서 생각했다. 생각해야할 케이스가 매우 많으므로 천천히 생각해봐야 한다. 1. $A=0$인 경우1-1. $B \neq 0$, $C \neq 0$ 인 경우$Bx+Cy+D=0$의 형태가 되는데 베주 항등식이 떠오를 것이다. 정수 해가 무한히 존재하는 지 혹은 없는지에 대해 알 수 있다.$GCD(B, C) = X$라 하고, 베주 항등식에 따르면 $X$가 $D$의 배수이면 정수인 $x, y$가 무수히 많기 때문에, 이를 판별해서 구하면 된다. 1-2. $B = 0$, $C \neq 0$ 인 경우$Cy+D=0$이 되고,.. 공감수 0 댓글수 0 2024. 9. 19.
랜덤 마라톤 14주차 A. Card Game Contest (백준 14551)조합론 각각의 덱은 독립적이므로 총 방법의 수는 $A_1$부터 $A_N$까지 곱하면 된다. 단, 덱이 없을 수도 있는데, 이때는 스킵하거나 0을 1로 바꾸면 된다. $M$으로 나눈 나머지를 구해야 하므로 곱할 때마다 모듈러 연산을 취해주면 된다. B. 행사장 대여 (Small) (백준 14732)구현 범위가 작으므로 좌표를 받을 때마다 그 부분의 영역들을 2차원 배열에 1로 채워주면 된다. 이후 넓이를 구할 때 1의 개수를 세어주면 된다. C. 체크포인트 달리기 (백준 29891)그리디, 정렬 일단 들어오는 모든 수가 양수 혹은 음수일 때를 생각해보면, $N$이 $K$의 배수라면 거리가 먼 순서부터 체크하던지, 가까운 순서부터 체크하던지 상관없지.. 공감수 0 댓글수 0 2024. 9. 5.
[BOJ][Python] 백준 3653번 - 영화 수집 문제 링크: https://www.acmicpc.net/problem/3653문제 풀이세그먼트 트리 N+M개의 배열을 생각해서 세그트리를 짜면 된다. 그리고 인덱스 배열을 하나 만들 건데 [0, n, n-1, n-2, ..., 1]로 만들어준다. 그 이유는 1이 가장 위에 있으므로 자신의 위쪽엔 아무것도 없다. 이를 배열로 생각하면 자신의 오른쪽에는 아무것도 없다라는 의미고 아래는 자신의 왼쪽이라고 생각하면 된다. 아무튼 인덱스가 지금 최대 n이니 책을 꺼냈다면 그 책의 인덱스는 이제 n+1이 되고 원래 있었던 인덱스의 세그 값은 0으로, 새롭게 만들어진 인덱스는 1로 업데이트 하면 문제에 대한 쿼리를 적절하게 수행할 수 있다. 코드 공감수 0 댓글수 0 2024. 6. 30.
[BOJ] 2023 11월 3주차 정리 2023년 11월 13일 (월) ~ 11월 19일 (일) - 푼 문제 (8 solved) 문제 링크: https://www.acmicpc.net/problem/13224 13224번: Chop CupOisín is amateur magician and is big fan of Chop Cup routine which involves three cups face down and one ball underneath one of the cups. He's only started to practice the trick and wants to test out if you can follow where the ball is without any trickswww.acmicpc.net 13324번 Chop Cup .. 공감수 0 댓글수 0 2023. 11. 15.
[BOJ][Python] 백준 9370번 - 미확인 도착지 문제 링크: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서www.acmicpc.net문제 풀이데이크스트라 처음에는 g와 h를 방문 했는지에 따라 처리를 했었다. g-h혹은 h-g를 방문했다고 체크를 하면서 해당 번호에 저장을 했었다. 문제는 가중치가 같은데 하나는 g-h 간선을 방문했고 하나는 방문을 안했다면 덮어질 수도 있다. 이 점까지 체크했고 정답을 확신 했었다. 하지만 이제는 시간 초과가 나기 시작했다. 아무래도 가중치가 같은 값이 수없이 많으면 또 그만큼 돌.. 공감수 1 댓글수 1 2022. 10. 11.
[BOJ][Python] 백준 9011번 - 순서 문제 링크: https://www.acmicpc.net/problem/9011 9011번: 순서 n개의 정수로 된 순서 S= (s1, s2, ..., sn)가 있다. 여기서 si ≠ sj이고, 1 ≤ si ≤ n이다. S로부터 새로운 순서 R = (r1, r2, ..., rn)을 얻을 수 있는데, 여기서 ri는 S의 부분 순서 {s1, s2, ..., si-2, si-1} 중에서 www.acmicpc.net 문제 풀이 구현 R 수열의 뒷부분부터 처리하면 어렵지 않다. 처리는 R[i]+1을 중심으로 하면 된다. 가령 R수열의 마지막은 오른쪽 부분이 없고 왼쪽에는 자신보다 작은 수의 개수이므로 R[i]+1로 자명하다. 그렇다면 중복 혹은 자신보다 작은 수가 오른쪽에 있는 경우는 어떻게 해야할까? 예제 1을 .. 공감수 0 댓글수 0 2022. 8. 5.
[BOJ][Python] 백준 16973번 - 직사각형 탈출 문제 링크: https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 문제 풀이 너비 우선 탐색, 누적 합 BFS를 이용하는 건 그다지 어렵지 않다. 대부분의 BFS 문제처럼 직사각형의 왼쪽 가장자리를 기준으로 방문하지 않았다면 방문해주고 벽이라면 방문하지 않는 등 일반적인 문제랑 비슷하다. 하지만 직사각형 전체 중에 벽이 있다는 걸 확인하는건 어떻게 해야할까? 먼저 H*W번을 매번 방문할 때 마다 체크해준다? 딱봐도 시간 초과.. 공감수 0 댓글수 0 2022. 8. 5.
[BOJ][Python] 백준 4658번 - 삼각형 게임 문제 링크: https://www.acmicpc.net/problem/4658 4658번: 삼각형 게임 삼각형 게임은 시작할때 여섯개의삼각형을 부여받는데, 각 변에는 숫자가 쓰여있다(그림 참고). 이 삼각형들을 돌리고 움직여서 육각형을 만들어야 하는데, 반드시같은 숫자가 쓰여있는 변끼리 www.acmicpc.net 문제 풀이 브루트포스 알고리즘 브루트포스로 대충 돌려서 풀었다. 테케가 몇 개인지 모르지만 한번 할때 $6!*3^{6}$ 정도니 시간 안에 들거 같다. 일단 삼각형을 입력받고 왼쪽 숫자는 0, 오른쪽 숫자는 1, 밑변 숫자는 2로 인덱스를 정하자. 다음 그림과 같다. 이런 삼각형이 주어졌을 때, 순서가 정해져있지 않기 때문에 순열을 이용해주고, i번의 삼각형의 1번 인덱스와 i+1번의 삼각형의.. 공감수 0 댓글수 0 2022. 8. 3.
[BOJ][Python] 백준 4696번 - St. Ives 문제 링크: https://www.acmicpc.net/problem/4696 4696번: St. Ives Input consists of multiple data sets. Each data set consists of a line with a single floating point number number representing the numbers of wives, sacks per wife, cats per sack, and kittens per cat that Robert encountered that year. End of input is indic www.acmicpc.net 문제 풀이 사칙연산 $1+n+n^{2}+n^{3}+n^{4}$ 를 구한 후 소숫점 셋째 자리에서 반올림 한다. 코드 공감수 0 댓글수 0 2022. 8. 2.
[BOJ][Python] 백준 11434번 - Ampelmännchen 문제 링크: https://www.acmicpc.net/problem/11434 11434번: Ampelmännchen When you unite two countries, they will typically have their own versions of most things, like road signs, foods, etc. If you basically have one of the countries “impose” its version on the other, this may feel to the other more like an annexation than www.acmicpc.net 문제 풀이 사칙연산 서쪽 사람들이 본인의 비전을 좋아하는 값과 동쪽 사람들이 서쪽 비전을 좋아하는 값을 더한 값.. 공감수 0 댓글수 0 2022. 8. 2.
[BOJ][Python] 백준 2344번 - 거울 문제 링크: https://www.acmicpc.net/problem/2344 2344번: 거울 세로 N, 가로 M 크기의 상자가 있다. 이 상자 안에는 몇 개의 거울이 들어 있다. 상자를 위에서 봤을 때, 거울은 한 칸 안에 대각선 모양으로 들어있다고 한다. 또, 상자의 테두리를 따라서 칸마다 www.acmicpc.net 문제 풀이 시뮬레이션 전형적인 시뮬레이션 문제이다. 5 4 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 으로 주어졌을 때를 시뮬레이션 해보자. 1~5번의 경우는 다음과 같다. 좌표와 방향을 이용해서 적절하게 풀 수 있다. 이때 x는 0보다 크거나 같고 n보다 작고 y는 0보다 크거나 같고 m보다 작으면 반복문을 종료시킨다. 방향은 1~5번일 때 →로 시작하게.. 공감수 0 댓글수 0 2022. 8. 2.
[BOJ][Python] 백준 20412번 - 추첨상 사수 대작전! (Hard) 문제 링크: https://www.acmicpc.net/problem/20412 20412번: 추첨상 사수 대작전! (Hard) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 문제 풀이 페르마의 소정리 페르마의 소정리를 이용하여 풀었다. $(a \times Seed+c) \equiv X1 \;(mod \; m)$와 $(a \times X1+c) \equiv X2 \;(mod \; m)$를 빼서 한개의 연립합동방정식을 만든다. $a(Seed-X1) \equiv X1 - X2 \;(mod \; m)$가 되는데 m은 소수이고 0 공감수 0 댓글수 0 2022. 7. 2.
[BOJ][Python] 백준 10172번 - 개 문제 링크: https://www.acmicpc.net/problem/10172 공감수 0 댓글수 0 2022. 5. 5.
[BOJ][C] 백준 10430번 - 나머지 문제 링크: https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 문제 풀이 사칙연산 모듈러 연산의 정의를 보여주는 문제. 물론 이 문제는 그냥 출력값만 주면 되지만 나중에 많이 써먹게 되는 내용이다. 코드 공감수 0 댓글수 0 2022. 5. 5.
[BOJ][C] 백준 10869번 - 사칙연산 문제 링크: https://www.acmicpc.net/problem/10869 10869번: 사칙연산 두 자연수 A와 B가 주어진다. 이때, A+B, A-B, A*B, A/B(몫), A%B(나머지)를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 사칙연산을 하면 되는 문제. 코드 공감수 0 댓글수 0 2022. 5. 5.
[BOJ][Python] 백준 23796번 - 2,147,483,648 게임 문제 링크: https://www.acmicpc.net/problem/23796 23796번: 2,147,483,648 게임 호준이는 2048 게임을 발전시킨 2,147,483,648 게임을 하고 있다. 2,147,483,648 게임은 \(8 \times 8\) 크기의 게임판에서 키보드의 방향키를 통해 \(2^k\) (\(1 \le k \le 30\))꼴에 해당하는 정수가 쓰여 있는 www.acmicpc.net 문제 풀이 2048 게임 구현 문제 상세 풀이는 나중에 코드 공감수 0 댓글수 0 2022. 5. 3.
[BOJ][C] 백준 10998번 - A×B 문제 링크: https://www.acmicpc.net/problem/10998 10998번: A×B 두 정수 A와 B를 입력받은 다음, A×B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 A와 B를 입력받아 A×B를 출력하는 문제 코드 공감수 0 댓글수 0 2022. 5. 3.
[BOJ][Python] 백준 10718번 - We love Kriii 문제 링크: https://www.acmicpc.net/problem/10718 10718번: We love kriii ACM-ICPC 인터넷 예선, Regional, 그리고 World Finals까지 이미 2회씩 진출해버린 kriii는 미련을 버리지 못하고 왠지 모르게 올해에도 파주 World Finals 준비 캠프에 참여했다. 대회를 뜰 줄 모르는 지박 www.acmicpc.net 문제 풀이 강한친구 대한육군을 2번 출력하면 되는 문제. 코드 공감수 0 댓글수 0 2022. 5. 3.
[BOJ][Python] 백준 1001번 - A-B 문제 링크: https://www.acmicpc.net/problem/1001 1001번: A-B 두 정수 A와 B를 입력받은 다음, A-B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 A와 B를 입력받아 A-B를 출력하는 문제 코드 공감수 0 댓글수 0 2022. 5. 3.
[BOJ][Python] 백준 1000번 - A+B 문제 링크: https://www.acmicpc.net/problem/1000 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 A와 B를 입력받아 A+B를 출력하면 된다. 코드 공감수 0 댓글수 0 2022. 5. 3.
[BOJ][Python] 백준 2559번 - 수열 문제 링크: https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 풀이 누적 합을 이용하는 문제. 브루트 포스를 이용한다면 N이 최대 10만 이므로 시간 초과가 날 수 있다. 누적 합을 이용한 배열을 만들어주고, 예제 2를 생각하면 첫 번째는 prefix_sum[5]-prefix_sum[0]이고, 다음은 prefix_sum[6]-prefix_sum[1], ... 이렇게 앞에 있는 누적합을 빼주면서 구하면 O(N)이므로 시간 초과나지.. 공감수 0 댓글수 0 2022. 5. 2.
[BOJ][Python] 백준 17265번 - 나의 인생에는 수학과 함께 문제 링크: https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 문제 풀이 재귀를 이용해 풀었다. N 범위가 최대 5라 완탐을 해도 오래 걸리지 않으니 그렇게 했다. 오른쪽 혹은 아래쪽으로만 가므로 방향을 2개 잡아주고, 범위에 넘어간다면 실행시키지 않는다. 연산자가 주어졌을 경우 연산자를 저장하고 바로 다음으로 넘기고 숫자가 주어졌을 경우 전에 연산했던 값과 바로 이전에 나왔던 연산자로 현재 값과 계산해주고 다시 저장한다. 이때 숫.. 공감수 0 댓글수 0 2022. 5. 1.
[BOJ][Python] 백준 8711번 - Odchudzanie 문제 링크: https://www.acmicpc.net/problem/8711 8711번: Odchudzanie Kozik postanowił się odchudzić. Jest po n dniach diety i intensywnego treningu, jednak waga nie spadała mu równomiernie, a czasem nawet (ku zdziwieniu Kozika) zwiększała się. Kozik codziennie zapisywał swoją wagę i teraz chce się pochwalić ko www.acmicpc.net 문제 풀이 최대에서 최소 빼기. 하지만 최댓값을 잘 잡아주어야 한다. 참고로 파이썬은 메모리 초과 때문에 list로 변환하지 말고 map.. 공감수 0 댓글수 0 2022. 5. 1.
[BOJ][Python] 백준 25083번 - 새싹 문제 링크: https://www.acmicpc.net/problem/25083 25083번: 새싹 아래 예제와 같이 새싹을 출력하시오. www.acmicpc.net 문제 풀이 text가 언어 제한이라 파이썬으로 했는데 '나 ""는 """을 이용해 간단히 출력할 수 있다. 코드 공감수 0 댓글수 0 2022. 5. 1.
[BOJ][Python] 백준 9501번 - 꿍의 우주여행 문제 링크: https://www.acmicpc.net/problem/9501 9501번: 꿍의 우주여행 꿍은 우주여행을 하고 싶어져서 우주여행을 계획하기 시작했다. 몇 가지를 고려해본 결과 우주여행에는 우주선의 연료와 목적지까지의 도착시간이 가장 큰 영향을 미치는것으로 파악됐다. 꿍 www.acmicpc.net 문제 풀이 목적지까지의 거리를 우주선의 최고속도를 나누면 몇 시간을 가야하는지 알 수 있다. 이 시간과 우주선의 연료소비율을 곱하면 목적지까지 가는데 걸리는 연료를 구할 수 있는데, 연료량과 비교하여 카운트 해주면 된다. 코드 공감수 0 댓글수 0 2022. 4. 24.
[BOJ][Python][C++] 백준 24417번 - 알고리즘 수업 - 피보나치 수 2 문제 링크: https://www.acmicpc.net/problem/24417 24417번: 알고리즘 수업 - 피보나치 수 2 코드1 코드2 실행 횟수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다. www.acmicpc.net 문제 풀이 dp를 이용해서 피보나치 수를 구하면 된다. 너무 웰노운인 문제다. 코드 파이썬 코드 C++ 코드 공감수 0 댓글수 0 2022. 4. 5.
[BOJ][Python] 백준 1312번 - 소수 문제 링크: https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 문제 풀이 간단하게 0을 추가하고 b로 나누어서 나머지를 구한 후 두 가지로 나뉘어서 생각할 수 있다. 1. 나머지가 0인 경우 나머지가 0이라면 n번째 자리까지 안구했더라도 전부 0이 되기 때문에 반복문을 나가고 0으로 출력한다. 2. 나머지가 0이 아닌 경우 만약 n번째 자리까지 왔다면 몫을 출력, 아니면 나머지에서 또다시 0을 붙여서 반복문을 돌려준다. 코드 공감수 0 댓글수 0 2022. 4. 5.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.