본문 바로가기

반응형

전체 글

(155)
[BEAKJOON] 백준 2004번 : 조합 0의 개수 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제 접근 이전 팩토리얼 문제를 풀어봤으면, 한 팩토리얼 값의 5의 승수가 겹치는 수를 구해야한다. 문제는 nCr의 값을 구하는 것이기 때문에, 이항 계수의 공식을 생각하면 된다. 이항 계수의 공식은 팩토리얼 값으로 이루어져 있어서 이를 이용하면 쉽게 풀 수 있을 것이다. 조합은 영어로 combination이며, 고교 수학 내에서는 대문자 C를 사용하여 표현한다. 조합의 뜻은, nCr 의 뜻은 'n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수' 이다. ..
[BEAKJOON] 백준 6588번 : 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 문제 파악 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + ..
[BEAKJOON] 백준 1978번 : 소수찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수는 1과 자기 자신을 제외한 숫자 외에는 약수가 될 수 없다. 가장 기본적으로, 소수를 구하는 방법으로는, 해당 주어진 숫자를 2부터 본인숫자까지 나누어지지 않은다면 소수인데, 아니면 소수가 아닌 것이다. 그렇게 해당 주어진 숫자를 차례차례 계산하는 방법도 있기는 한데, 시간 복잡도가 높을 것이다. 2에서부터 자기 자신까지 모두 나눴을 때 나머지가 0이 되면 소수가 아니며, 0이 한번도 나오지 않는다면 소수이다. 구하려는 숫자가 커질 수록 시간이 그만큼 늘어나게..
[독서] 무엇이 조직을 움직이는가, 패드릭 렌치오니 알면서도 실천하지 않는 것은, 진정 아는 것이 아니다. - 소크라테스 ​ ​ 이 책은 인류 역사상 가장 위대한 발명품은? 이라는 질문으로부터 시작한다. 가장 위대한 발명품은 "조직"이라고 본다. 조직이 없었다면 모든 발명품들이 인류 역사를 바꿀 만큼 현실화될 수 없을 것이라고 한다. 스콧 켈러와 콜린 프라이스가 주장하듯이, 조직화를 통해 모두가 협력하여 끊임없이 진보를 추구했기에 인류 역사는 오늘에 이를 수 있었다고 해도 과언이 아니다. ​ 조직은 강력하다. 조직이 지난 강력한 힘은 시너지 효과를 창출하는 조직력에서 나온다. - 무엇이 조직을 움직이는가 中 ​ 이러 조직력의 강력한 힘에서의 문제는, 어떻게 해야 조직력을 극대화시켜 위대한 조직을 만들 수 있느냐 그러기 위해서는 조직 전체가 공동의 목표를 ..
[독서] 우리는 모두 각자의 별에서 빛난다 - 누구든지 꼭 읽어봤으면 하는 책 세상에서 나의 마음과 가치관을 위해 한 권만 고를 수 있다면, 이 책을 고를 것. 나에게 삶의 지혜 뿐만 아니라 사명을 느끼게 해주었다. ​ ​ 이 책을 처음 보았을 때는, 카이스트 총장님께서 쓴 책이라는 것을 알았고, 별로 재미가 없고 지루할 줄 알았다. 나에게 와닿는 내용이 없을거라고 생각해서 기대를 안했었다. 그러나 책을 점점 읽어갈수록 생각은 잘못되었다는 것을 알았고, "우리는 모두 각자의 별에서 빛난다"라는 책은 정말 나에게 꼭 필요한 책이라는 것을 깨달았다. ​ ​ 이 책의 앞 부분과 같이, 나는 무엇을 하며 어떻게 살아야 할까? 왜 나는 남보다 잘하는게 없을까? 자신이 있는게 없다는 생각을 했었다. 어른이 된다는 것은, 마냥 설레임이 가득한 것보다는, 이제 온전히 스스로가 책임을 지어야 되는..
[BEAKJOON] 백준 2609번 : 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 설명 최대공약수와 최소공배수를 구하는 문제이다. 풀이 코드 나는 처음에 input으로 a, b를 입력 받고, 둘중에 큰 값을 확인한 후, 최대공약수는 가장 정석적인 방법으로, 최소공배수는 당시에 풀때는 자각하지는 못했지만, 유클리드 호제법으로 접근을 했다. 최대공약수를 먼저 구해서, 최대공약수에 대한 정보를 안 상태로 최소공배수와 연관성을 가지고 있지 않을까에서 시작된 접근법이었다. import sys input = sys.stdin.readline a, b..
[BEAKJOON] 백준 17413번 : 단어 뒤집기 2 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 문제 설명 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '
[BEAKJOON] 백준 1158번 : 요세푸스 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제이다. 문제 설명 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열..

반응형