https://www.acmicpc.net/problem/2877 2877번: 4와 7 창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오. www.acmicpc.net 기사 공부하랴, 텝스 하랴 소홀히 했던 알고리즘을 정말 오랜만에 다시 풀어보았다. 4와 7로 이루어진 수 중, n번째로 작은 수를 출력하는 문제다. 단번에 아이디어가 떠오르지 않는데, 분명 패턴이 있을 것 같아서 찾을 때 까지 수를 계속 적어보았다. 문제에서 알 수 있듯, 이 문제는 이진수(0과 1로 이루어진 수)를 활용해 푸는 문제이다! 패턴을 살펴보자. 정수 1 = 이진수 1 = 4 정수 2 = 이진수 10 = 7 정수 3 = 이진수 11 = 44 ... 이런 ..
https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 어려워 보이지만 차근차근 따져보면 쉽게 풀리는 문제이다. 이 문제에서 가능한 연산은 오직 나누기3과 곱하기2 뿐이다. 그렇다면, 맨 앞에는 어떤 수가 와야할까? -> 인수3을 가장 많이 가지고 있는 숫자가 맨 앞에 와야한다! 왜 그럴까? 6 9를 예시로 보자, 6에서 9를 만들 수 있을까 라고 물어보면 답은 절대 불가능하다 이다. 15와 9를 예시로 들어도 마찬가지이다. 1. 곱..
https://www.acmicpc.net/problem/4587 4587번: 이집트 분수 입력으로 주어진 분수 M/N이 다음과 같이 나타낼 수 있다면, D1, D2, D3, ...를 공백으로 구분해 출력한다. (D1 ≤ D2 ≤ D3 ≤ ....) www.acmicpc.net 이 문제 역시 알고리즘 수업에 나온 문제가 백준에 있길래 풀어보았다. 내가 아는 이집트 분수의 풀이법은 2가지다. 1. 현재 분수에서 뺄 수 있는 가장 큰 기약분수로 빼면서 구하기 2. 현재 분수 p/q를 뒤집어서 q/p로 만든 후, 이 q/p보다 큰 정수를 선택하고, 그 정수를 역을 취해 원래 분수에 빼주는 방법 2번 방법이 시간적인 측면에서 훨씬 유리하기 때문에, 2번으로 해보려다가 문제의 조건을 보고 1번 방법을 택했다. (..
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 3 16을 예로 들어보자. 3부터 16까지 검사하면서 현재 숫자가 소수이면 출력해주는 구조인데, 그냥 구하면 시간초과가 발생할 것이다. 그리고 1은 좀 특별하게 예외처리를 해주어야 한다. 왜냐?? 1은 소수가 아니지만, 소수 판별 알고리즘에 걸리지 않아 소수로 판별되기 때문이다! 2부터 n의 제곱근까지 i를 증가시키면서 혹시 딱 나눠 떨어지는 수가 있다면, 소수가 아니므로 False를 반환하고, 검사에 걸리지 않았다면 True를..
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이는 다음과 같다. 예시로는 200을 들겠다! 200 = 1 + 199이다. 199 = 2 + 197이다. (이미 1을 위에서 써버렸으므로 수를 1증가시키면서 사용) 197= 3 + 194이다. ... 계속하다보면 수가 계속 줄어들어서 45 = 18 + 27 까지 오게 되고 27 = 19 + 9가 되면서 뭔가 이상한 순간이 생긴다. 9는 아까 써버렸는데 또 9가 나온다. 27을 더이상 쪼갤 수 없으므로, 200은 1~18 그리고 27까지해서 총 19개의 자연수로 나눌 수 있다! 즉, 200을 덧셈으로 쪼개나가면서..
https://www.acmicpc.net/problem/2588 2588번: 곱셈 첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다. www.acmicpc.net 파이썬으로 주 사용언어를 바꿔보려고 한다. (사실 C++도 애착이 깊은 언어라, 둘 다 잘하고 싶은 마음이 크다) 그래서 백준에 있는 파이썬 길라잡이 문제집을 통해 파이썬을 연습하는 중이다. 두 정수를 int형이 아닌 str형으로 받아서 인덱스를 이용해 곱하기 해주면 금방 풀리는 문제이다. import sys a = input() b = input() ans=0 ans = int(a) * int(b[2]) print(ans) ans = int(a) * int(b[1]) print(ans) ans = i..
