전체 글

[Silver III] 피보나치 함수 - 1003 문제 링크 성능 요약 메모리: 79508 KB, 시간: 16 ms 분류 다이나믹 프로그래밍 문제 설명 다음 소스는 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) (두 ..

[Silver II] 나무 자르기 - 2805 문제 링크 성능 요약 메모리: 155812 KB, 시간: 608 ms 분류 이분 탐색, 매개 변수 탐색 문제 설명 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예..

[Silver I] IOIOI - 5525 문제 링크 성능 요약 메모리: 69260 KB, 시간: 152 ms 분류 문자열 문제 설명 N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. 출력 S에 PN이 몇 군데 포함되어 있는지 출력한다. 풀이 i) n의 길이에 맞는 IOI 문자열 Pn을 생성한 뒤, 배열을 순회하면서 만약 해당 문자열과 값이 같다면..

[Silver III] 1, 2, 3 더하기 - 9095 문제 링크 성능 요약 메모리: 69100 KB, 시간: 12 ms 분류 다이나믹 프로그래밍 문제 설명 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 풀이 이 문제는 규칙..

[Silver III] 계단 오르기 - 2579 문제 링크 성능 요약 메모리: 69100 KB, 시간: 8 ms 분류 다이나믹 프로그래밍 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세..

이 앱은 Apple Developer Academy @ Postech에서 진행한 MC3 프로젝트 때 개발한 앱입니다. 인원도 4명으로 제일 적었고, 해야할 것들도 매우 많았지만,,, 완벽한 팀원들 덕분에 배포까지 완료하였습니다 ㅎㅎ 하지만 배포 과정에서 여러 가지 우여곡절이 많았고, 사실 아직 심사 중이기 때문에 리젝을 당할 수도 있지만,, 배포 과정을 직접 진행한 과정을 정리해두고 싶어서 포스팅을 하고자 합니다. 우선 처음으로 배포 과정을 진행해보았는데, 배포 해보고 싶다는 저의 의견을 들어주신 팀원분들 감사드립니다 ^_^ (꾸벅) 과정 앱스토어 커넥트에 추가하기 우선 앱 스토어 커넥트에 들어가 본인의 계정으로 로그인한 뒤, 나의 앱을 선택해줍니다. + 버튼을 통해 신규 앱을 생성해줍니다. 앱 정보 입..

누적 합 누적 합이란 수열에 대해 각 인덱스까지의 구간의 합을 구하는 것을 의미합니다. 모든 구간에 대해 단순하게 반복하여 하나씩 더해가는 방법을 사용하게 되면 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있습니다. 하지만 이전 인덱스까지의 누적합에 현재 값을 더하는 방식인 누적 합을 사용하면 O(n)의 시간 복잡도를 가질 수 있습니다. 배열에 따라 누적합을 저장해놓은 뒤, 구하고자 하는 범위까지의 누적합에서 해당 범위에 포함되지 않는 범위를 빼주면 구할 수 있습니다. 따라서 배열의 특정 범위의 구간 합을 구하고자 한다면, 해당 알고리즘이 매우 유용할 수 있습니다. 예시 백준 11659 문제인 구간 합 구하기 4를 통해 누적합에 대해 알아보겠습니다. 우선 5 4 3 2 1에 대한 누적합을 구하고 배..

[Silver III] 구간 합 구하기 4 - 11659 문제 링크 성능 요약 메모리: 76204 KB, 시간: 196 ms 분류 누적 합 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 풀이 i) 처음에는 해당 값들을 전부 받은 뒤 인덱스가 같은 경우를 제외한 뒤, for문을 통해 합을 더하고, 출력하는 형식으로 생각했습니다. let nm = read..