공대생 공부일지

[Silver IV] The Game of Death - 11558문제 링크성능 요약메모리: 19304 KB, 시간: 156 ms분류그래프 이론, 그래프 탐색, 구현, 시뮬레이션제출 일자2024년 8월 3일 18:57:30문제 설명희현이와 주경이는 The Game of Death를 좋아한다.The Game of Death 규칙:플레이어는 각자 한 명씩 지목을 한다(자신도 가능).처음 시작하는 사람은 임의의 자연수 K를 말한다.시작한 사람부터 지목한 사람을 차례대로 따라가다가 K번째 지목당한 사람이 걸리게 된다.희현이는 희현이부터 이 게임을 시작할 때 이 게임에서 반드시 주경이를 반드시! 걸리게 하고 싶다. 주경이가 걸릴 수 있도록 희현이를 도와주자.입력첫 줄에는 테스트 케이스의 숫자 T가 주어지며, 이어..

[Silver IV] 반복수열 - 2331문제 링크성능 요약메모리: 14164 KB, 시간: 104 ms분류구현, 수학제출 일자2024년 8월 3일 18:24:05문제 설명다음과 같이 정의된 수열이 있다.D[1] = AD[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서..

[Silver I] 소수&팰린드롬 - 1747문제 링크성능 요약메모리: 70660 KB, 시간: 260 ms분류브루트포스 알고리즘, 수학, 정수론, 소수 판정, 에라토스테네스의 체제출 일자2024년 8월 2일 18:17:58문제 설명어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력첫째 줄에 조건을 만족하는 수를 출력한다.풀이소수와 팰린드롬을 동시에 만족하는 숫자를 찾는 문제다. 소수는 1과 자기 자신을 제외한 수 중 약..

[Silver I] 회전 초밥 - 2531문제 링크성능 요약메모리: 18644 KB, 시간: 196 ms분류브루트포스 알고리즘, 슬라이딩 윈도우, 두 포인터제출 일자2024년 8월 2일 05:04:08문제 설명회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만..

[Silver I] 기타 레슨 - 2343문제 링크성능 요약메모리: 23544 KB, 시간: 340 ms분류이분 탐색, 매개 변수 탐색제출 일자2024년 8월 1일 17:16:29문제 설명강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 ..

[Silver I] 기타 레슨 - 2343문제 링크성능 요약메모리: 24028 KB, 시간: 524 ms분류이분 탐색, 매개 변수 탐색제출 일자2024년 8월 1일 04:21:30문제 설명강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 ..

[Silver I] 연산자 끼워넣기 - 14888문제 링크성능 요약메모리: 17148 KB, 시간: 144 ms분류백트래킹, 브루트포스 알고리즘제출 일자2024년 7월 31일 00:58:36문제 설명N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총..

[Silver I] 컴백홈 - 1189문제 링크성능 요약메모리: 14888 KB, 시간: 124 ms분류백트래킹, 브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2024년 7월 29일 22:27:25문제 설명한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다. cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 ..

[Silver I] 쿼드트리 - 1992문제 링크성능 요약메모리: 14708 KB, 시간: 144 ms분류분할 정복, 재귀제출 일자2024년 7월 28일 20:50:17문제 설명흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로..

[Silver I] 부등호 - 2529문제 링크성능 요약메모리: 27996 KB, 시간: 532 ms분류백트래킹, 브루트포스 알고리즘제출 일자2024년 7월 26일 20:21:49문제 설명두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.3 1 7 0이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만..