💻 Problem문제 보러 가기  N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.  💡 Approach이 문제의 시간 제한은 0.25초이다.1초가 약 1억이니 0.25초면 약 25,000,000이다.피보나치의 기본 재귀 코드는 시간복잡도가 2^n이기에 재귀로 풀면 안 된다. 피보나치 수열은 n이 2 이상일 때, f(n) = f(n-1) + f(n-2) 이다.재귀로 풀면 f(n)을 구할 때, f(n-1)을 구하기 위해 f(n-2)를 계산했음에도 f(n-2)를 다시 구해서 f(n-1)과 더해야 한다. 사진으로 보면 이해하기 더 쉽다.위 사진에서 f(5)를 구하려고 할 때, 중복 계산이 여러 번 발생하는 것을 확인할 수 있다. DP..

💻 Problem문제 보러 가기 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.  첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1 이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.   입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push 연산은 +로, pop 연산은 -로 표현하..

💻 Problem문제 보러 가기 선생님이 다시 사용한 채점 방법은 두 해전을 골라 순서가 일치하면 점수를 주는 방법이다. 즉, 선생님은 학생의 답 중에 N(N-1)/2개의 쌍을 모두 고른 뒤, 올바른 순서로 적혀 있으면 1점을 주려고 한다. 최종 점수는 획득점수/(N(N-1)/2)가 된다.문제의 정답과 현우가 작성한 답안이 주어졌을 때, 현우의 점수를 구하는 프로그램을 작성하시오. 💡 Approach처음엔 시간을 제대로 보지 않고 그냥 브루트포스로 풀면 되지 않을까 싶었다.import sysinput = sys.stdin.readlinedef grade(): global score # 학생의 답 중에 2개를 고른다 for i in range(n): for j in ..

💻 Problem한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 22 × 22 크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다. 💡 Approach2차원 배열의 영역을 4분할한다.Z 순서대로 왼쪽 위(0), 오른쪽 위(1), 왼쪽 아래(2), 오른쪽 아래(3)이동 횟수는 0으로 시작한다.4개의 영역 중 타겟 좌표가 어디에 위치하는지 찾는다.타겟 좌표가 위치하는 영역..

💻 Problem문제 바로가기 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.아래 그림은 원판이 5개인 경우의 예시이다.  💡 Approach이전에 풀어봤던 문제지만 알고리즘을 오래 안 하면서 다 까먹어서 다시 풀어봤다.하노이탑 규칙은 어렸을 때 많이 해봐서 이해하고 있었지만, 이를 어떻게 구현해야 할지 감이 안 왔다.하노이..

📒 반복(Iteration)과 재귀(Recursion)반복과 재귀는 유사한 작업을 수행할 수 있다반복은 수행하는 작업이 완료될 때까지 계속 반복루프 (for/while, do~while 구조)재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법어떠한 개념이나 문제에 대한 정의를 그 개념이나 문제를 포함하는 작은 개념이나 문제로 나타내고 그 작은 개념, 부문 문제들에 동일하게 적용더 이상 작은 개념 부분 문제가 없을 때 ⇒ 재귀의 끝하나의 큰 문제를 해결할 수 있는 (해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다재귀 함수로 구현 📒 재귀 함수 (recursive function)함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수일반적으로 재귀적 정의..

문제 링크 https://www.acmicpc.net/problem/28127 문제 의찬이는 숫자가 적힌 블록으로 탑 쌓기를 즐긴다. 어느 날 선우는 의찬이가 쌓는 탑에 규칙이 있음을 알게 되었다! 선우가 알아낸 규칙은 다음과 같다. 의찬이가 쌓는 탑은 꼭대기가 1층이고, 1층에는 a개의 블록이 존재한다. 1층의 가장 왼쪽 블록에는 1이 적혀있으며, 블록에 적힌 숫자는 오른쪽으로 갈수록 1씩 증가한다. i번째 층의 가장 오른쪽 블록보다 i+1번째 층의 가장 왼쪽 블록이 1더 크다. i번째 층에 있는 블록의 수보다 i+1번째 층에 있는 블록의 수가 d개 더 많다. 아래 그림은 1에서 4층까지 a=1이고 d=2일 때 의찬이가 쌓은 탑의 모습이다. 각 숫자가 적힌 블록의 위치를 모조리 외운 의찬이는 선우가 던..

28107: 회전초밥 (Silver 1) https://www.acmicpc.net/problem/28107 문제 회전 초밥 가게에 N명의 손님이 있고, 요리사는 M개의 초밥을 순서대로 만든다. 요리사가 초밥을 만들 경우, 1번 손님부터 N번 손님의 순서대로 그 초밥을 받게 된다. 만약 먼저 초밥을 받는 손님이 초밥을 먹을 경우, 뒤의 손님들은 해당 초밥을 먹을 수 없다. 만약 아무도 해당 초밥을 먹지 않는다면, 초밥은 버려진다. N명의 손님은 각자 먹고 싶은 초밥이 적힌 주문 목록을 가지고 있다. 목록에 적힌 초밥의 순서에 상관 없이 만약 목록에 적혀있는 초밥이 앞에 오면 반드시 먹는다. 만약, 목록에 적히지 않은 초밥을 받는다면 그 초밥은 반드시 먹지 않는다. 단, 손님들은 다양한 초밥을 먹고 싶어하..