본문 바로가기

Class 337

[백준 01003] 피보나치 함수 [Python] 문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.두 번째 호출한 fibon.. 2024. 7. 23.
[백준 11726] 2×n 타일링 [Python] 문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.풀이dp[i] : 2xi 크기의 타일을 채우는 모든 경우의 수 n = 1 일때 1 : 2x1타일 1개로 채우는 방법n = 2 일때 2 : 2x1, 1x2 타일을 각각 2개로 채우는 방법n >= 3에 대해서는 점화식을 세울 수 있다.dp[i - 1]에 대해 2x1타일을 1개 붙이거나, dp[i - 2]에 대해 1x2 타일을 2개 붙이는 경우를 활용할 수 있다.이때, dp[i - 2]에 대해 .. 2024. 7. 21.
[백준 21736] 헌내기는 친구가 필요해 [Python] 풀이 단순한 graph 문제이다. 입력을 받으면서 탐색 위치를(I)를 찾아주자. BFS로 풀이했다. 벽(X)이 아닌 경우와, 이미 방문하지 않은 공간을 탐색해주어야 한다. 위의 조건이 성립하고, 도연이가 사람(P)을 만났다면 만난 사람 수를 업데이트 해주자. 만약 만난 사람이 0명이라면 "TT"를 출력해주어야 한다는 점도 유의하자. 소스코드 소스코드 보기 출처 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 2023. 6. 10.
[백준 20529] 가장 가까운 세 사람의 심리적 거리 [Java] 풀이 N개의 중 3개의 MBTI에 대해서 가장 작은 심리적 거리를 구해야 한다. 모든 경우의 수를 전부 탐색하면 N^3 이기에 당연히 시간초과가 발생할 것이다. 때문에 구한 거리가 0인지 확인을 하고, 중간에 loop를 빠져나와야 한다. 비둘기집 원리를 통해 더 줄여보자. MBTI에 대한 심리적 거리의 최선의 경우는 뭘까? bruteforce이지만, 심리적 거리가 0인 경우 더 이상의 탐색이 무의미하기에 중단 해주어 시간초과가 발생하지 않는다. 심리적 거리가 0이라는 조건 이후의 탐색이 무의미하다면, 심리적 거리가 0이 되는 최악의 경우는 무엇일까? 바로 비둘기집 원리에 따른 33명이다. 서로 다른 MBTI를 가진 16명이 2명씩 총 32명 있을 경우 심리적 거리는 0이 될 수 없다. 33명부터 동일한 .. 2023. 6. 7.
[백준 14940] 쉬운 최단거리 [Java] 풀이 각 지점에서 목표지점(2) 까지의 거리를 출력하는 문제로 반대로 생각해서 목표지점에서 출발해 갈 수 있는 모든 거리에 대한 거리를 계산하는 문제로 풀이할 수 있다. 입력을 받으면서 목표지점(=출발지점)을 찾으면 0으로 대신 넣어주고, 1이면 -1로 넣어주자. 그 외의 숫자는 그대로 넣어주면 된다. 1일 때 -1을 넣어주는 이유는 출발지점으로부터 출발했을 때 갈수없는 땅(0)으로 둘러싸인 영역은 도달할 수 없는 위치(-1)임을 미리 표시하기 위함이다. 출발지점에서 도달할 수 있는 영역의 1들이 전부 -1 로 바뀌면 문제가 없을까? 그렇다, 어차피 도달할 수 있는 영역의 거리들은 이전에 도달한 거리의 값(출발지점 = 0 이므로 0 이상의 수)에 1을 더한 값이기에 결국은 덮어쓰일 것이다. 그 이후로는 .. 2023. 6. 7.
[백준 6064] 카잉 달력 [Python] 풀이 부터 시작해 주어진 M, N에 관련된 조건에 맞게 두 자연수를 1씩 증가(이 때 k도 1씩 증가) 해야 한다. 증가한 두 자연수가 이 되기 전에 와 일치하면, 그때의 k를 출력하면 된다. 기본적인 로직은 아래와 같다. 단순히 (M, N, x, y)가 (39999, 40000, 39999, 40000) 으로 주어져도 LCM(39999, 40000) = 1,599,960,000 이기에 위의 방식대로 모든 수를 다 구하면 시간초과가 발생할 것이다. 난이도가 실버1로 낮은 편이고, 주어지는 수 또한 작은 수에 해당되기에 중국인의 나머지 정리를 사용하지 않고도 풀이할 수 있다. 아래와 같은 풀이 과정을 통해 접근이 가능하다. 구하고자 하는 k는 이 가 되기 위해 (x = y)가 아닌 이상 M, N의 배수에 .. 2023. 4. 22.

티스토리툴바