개발자 퉁이리

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 슬라이딩 윈도우 ⊙ 문제 접근 과정 그렇게 어렵지는 않은 문제다. 공간 복잡도를 조금만 신경 쓴다면. 메모리 제한이 4MB이기에 공간을 잘 사용해야 한다. 변수를 여러 개 설정해주고 매번 갱신해 공간을 절약하는 방법을 선택했다. 아래 예시를 통해 접근 과정을 알아보자. 3 1 2 3 4 5 6 7 8 9 N=3, 3줄을 입력받는다. 첫 번째 줄은..

www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 ⊙ 문제 접근 과정 문제를 보고 제일 먼저 잔돈을 배열로 정리했다. 그다음 무한 루프 문을 만들고 배열 인덱스를 활용하여 count를 올려주고 break를 통해 탈출하는 반복문 코드를 짰다. 배열을 이용하여 잔돈 정리 count 값 초기화 index를 활용해 입력받은 값 비교 입력받은 값이 더 크면 잔돈을 빼고 c..

www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 ⊙ 문제 접근 과정 조건에서 입력도 무작위가 아닌 친절하게 오름차순으로 정렬하여서 입력하라고 한다. 막힘없이 코드를 작성했고 예제 입출력과 같은 값을 출력할 수 있었다. 하지만 틀렸다고 떴다. 아래 코드이다. #include using namespace std; int m..

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그리디 알고리즘 정렬 ⊙ 문제 접근 과정 그리디 알고리즘이다. 그리디 알고리즘은 배열을 하면 손쉽게 풀 수 있다. 값을 입력받고 오름차순으로 정리한 뒤에 순서대로 result 변수에 값을 넣어주고 값을 도출해냈다. ⊙ 문제 풀이 #include #include #include using namespace std; int main() { vector vec; int N; int to..

www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 문자열 ⊙ 문제 접근 과정 배열에 크로아티아 알파벳을 넣어주고 입력받은 문자열에 있는지 없는지 찾아줬다. 있다면 다른 하나의 문자로 변경해주고 마지막에는 변경된 입력받은 문자열의 길이를 출력해주었다. string::npos는 find() 함수에서 찾는 단어나 문자열이 없으면 나오는 리턴 값이다. ⊙ 문제 풀이..

www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 정렬 ⊙ 문제 접근 과정 헤더 파일, 헤더 파일에 있는 sort와 vector를 이용하여 오름차순 정렬을 했다. 그다음 for each문을 이용하여 출력해줬다. ⊙ 문제 풀이 #include #include #include using namespace std; int main() { int a; cin >> a; int input[a]; vector ..

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 제한시간 때문에 상당히 애쓴 문제다. 정상적으로 출력되는데 시간 초과가 떠서 cin, cout을 printf와 scanf로 바꿨다. 그래도 시간 초과가 떴다. 내 첫 번째 풀이다. (시간 초과) #include using namespace std; int count_zero = 0; int count_one = 0; int fibonacci(int n) { if (n == 0) { count_zero++; r..

www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 다이나믹 프로그래밍 ⊙ 문제 접근 과정 어머나, 문제에 정답이 적혀있다. F(n) = F(n-1) + F(n-2) // (n>=2) 코드로 그대로 옮기자 ⊙ 문제 풀이 #include using namespace std; int def(int n) { if (n==0) { return 0; } else if..

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 3,4개 정도를 직접 풀어보면서 규칙을 찾고 점화식을 만들면 된다. 1-> 1 2-> 2 3-> 4 4-> 7 5-> 13 점화식으로 표현하면 solution(n) = solution(n-1) + solution(n-2)+ solution(n-3) //(n>3) ⊙ 문제 풀이 t= int(input()) def solution(n): if n==1: return 1 elif n==2: return 2 elif ..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 오늘 스터디에서 공부한 BFS를 적용해서 풀었다. BFS는 Breadth First Search이다. 넓이 우선 탐색, 그래프 탐색 중 하나이다. 가장 짧은, 가장 빠른과 같은 것을 물어보면 BFS를 생각하자. 그리고 파이썬에서 queue는 반드시 deque를 사용..