본문 바로가기
728x90

algorithm

[백준알고리즘] 1978번: 소수 찾기 -Python, C++ [백준알고리즘] 1978번: 소수 찾기 -Python, C++ https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 다른 분들의 코드를 봤는데 너무 짧고 변수 명도 그냥 알파벳이라 보기 넘 힘들다 ㅠㅠㅠ 일단 다른분들은 나처럼 에라토스테네스의 체를 이용한 분들도 계셨고, 1부터 n까지 반복문을 돌면서 안에서 또 3부터? 반복문을 돌리면서 나눠 떨어지는지 확인함으로써 소수인지 판별해서 소수 리스트를 만들어서 사용한 분들도 계셨다. 아무튼 나는 에라토스테네스의 체를 사용했다. 에라토스테네스의 체의 위키 링크이다. http.. 더보기
[백준알고리즘] 11576번: Base Conversion -Python [백준알고리즘] 11576번: Base Conversion -Python https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 세계에서도 프로그래밍을 하고 싶었던 정이는 백준 사이트에 접속하여 문제를 풀기로 하였다. 그러나 미래세계는 A진법을 사용하고 있었고, B진법을 사용하던 정이는 문제를 풀 수가 없었다. 뛰어난 프로그래머였던 정이는 A진법으로 나타낸 숫자를 B진법으로 변환시켜주는 프로그 www.acmicpc.net A진법의 수를 m자리만큼 입력받아 B진법.. 더보기
[백준알고리즘] 2089번: -2진수 -Python [백준알고리즘] 2089번: -2진수 -Python https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다. 10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 처음 푼 코드는 내가 직접 찾은 방법이다... 창피하긴 한데 풀 때는 다 이렇게 푼 줄 알았다. 먼저, 내가 직접 문제를 해결한 방법을 설명.. 더보기
[백준알고리즘] 11005번: 진법 변환 2 -Python [백준알고리즘] 11005번: 진법 변환 2 -Python https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 www.acmicpc.net 이전에 ord()를 사용해서 아스키코드를 숫자로 변환해준 2745번 진법 변환과 달리 10진수를 해당 진법에 맞게 변환해줘야 한다. 따라서 여기서는 chr()을 사용했다. str()는 인자값을 그대로 문자열로 바꾸는 것이지만 chr()의 경우 주.. 더보기
[백준알고리즘] 2745번: 진법 변환 -Python [백준알고리즘] 2745번: 진법 변환 -Python https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 www.acmicpc.net 주어진 진법과 수를 10진수로 바꾸는 문제이다. 이번 문제에서는 A~Z를 확인하기 위해서 각 인덱스의 character마다 정수인지 확인하기 위해서 isdigit()을 사용했다. 숫자일 경우 그대로 int()를 씌워서 숫자로 만들었다. A~Z에 해당하는 값은.. 더보기
[백준알고리즘] 9613번: GCD 합 -Python [백준알고리즘] 9613번: GCD 합 -Python https://www.acmicpc.net/problem/9613 9613번: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 예제 입 www.acmicpc.net 이번에는 최대공약수를 구하기 위해 math 모듈의 gcd를 사용했다. 처음에는 유.. 더보기
[백준알고리즘] 1850번: 최대공약수 -Python [백준알고리즘] 1850번: 최대공약수 -Python https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. www.acmicpc.net 예제를 헷갈릴만하게 줬다. 처음에 보면 두 수의 차이만큼 1이 존재하는 것처럼 느껴진다. 하지만 뭔가 이상해서 생각해보니 두 수의 최대공약수만큼 1이 존재하는 것과 같았다. 두 수의 차이만큼 1이 존재하는 것이 아닌 것은 다음을 보면 알 수 있다. 입력으로.. 더보기
[백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python [백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 이번 문제는 주어진 두 수에 대한 최대공약수와 최소공배수를 구하는 문제이다. 이전에도 풀었던 문제인데 코드를 비교해보니 거의 같았다. 공식이 있어서 그런 것 같다. 최대공약수를 구하는 공식은 유클리드 호제법이다. 유클리도 호제법을 이용하면 다음과 같은 공식이 나오게 된다. 두 수 A와 B가 있을 때, A에 대하여 B를 나눈 몫이 X, 나머지가 R이라 하면, "A = B * X + R"의 식이 나오게 .. 더보기
728x90

티스토리툴바