Algorithm

문제 링크 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 문제 풀이 처음에 순차탐색으로 풀었더니 시간 초과가 나왔다. 이진탐색으로 코드를 수정하니 답을 맞힐 수 있었다. import sys # 가지고 있는 카드 개수 N = int(sys.stdin.readline()) # 가지고 있는 카드 숫자 cards = list(map(int, sys.stdin.readline().split())) # 검사해야 할 카..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 문제 풀이 이진 탐색을 통해 풀이를 했다. 입력받은 집의 위치에 대해 먼저 정렬을 진행하고, 이진 탐색에 대한 끝점을 제일 긴 거리로 처음에 두어 이진탐색을 진행한다. 변수 current는 공유기를 둔 위치를 나타낸다. import sys N, C = map(int, sys.stdin.readline().split()) house..

문제 링크 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 문제 풀이 이분 탐색으로 푸는 문제이다. 시작점을 1, 끝점을 입력받은 len의 최댓값으로 두고 mid를 구하여 len에서 뺀 값을 모두 더하는 것으로 상근이가 얻을 수 있는 길이를 구한다. 이 때, 주의해야 할 점은 나무의 길이가 중간값보다 길 때만 빼야한다는 것이다. 이 조건문을 빼놓으면 마이너스 값도 얻을 수 있는 값을 더할 때 포함되므..

문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 문제 풀이 이분 탐색으로 풀이를 하면 되는 문제이다. 길이를 기준으로 랜선의 개수를 결과내면 된다. 1을 시작값, 입력받은 길이 중 최댓값을 마지막값으로 하여 중간값을 정하고 해당 중간값으로 길이를 나누어 나온 개수를 합쳐 해당 개수가 요구받은 N값보다 작을 경우 중간값을 줄이기 위해 end 값을 mid - 1로, N값보다 클 경우 중간값을 늘리기 위해..

문제 링크 https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 문제 문제 풀이 처음에 제출했던 코드는 아래와 같다. n = input()[::-1] convert10 = 0 result = "" for i in range(len(n)): convert10 += int(n[i]) * (2 ** i) while convert10 != 0: result += convert10 % 8 convert10 //= 8 print(result[::-1]) 이렇게 직접 2진수를 10진수로 변환하고, 그것을 다시 8진수로 변환하는 코드를 짜서 제출했는데 수정을 계속 해..

문제 링크 https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문제 문제 풀이 1234(2)를 10진수로 변환하려 할 때 2^3 * 1 + 2^2 * 2 + 2^1 * 3 + 2^0 * 4 의 계산으로 변환된다. 이 원리를 활용해서 N을 입력받고 0부터 순서대로 B^(len(N) - 1)까지 곱해지는 것에 대해 for문으로 작성하였다. N, B = input().split() N = N[::-1] B = int(B) table = "012345678..

문제 링크 https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문제 문제 풀이 진법 변환 과정이 갑자기 기억이 안나서 헤맸다..ㅋㅋㅋ B진법으로 변환하려면 10진수 N을 숫자 B로 나머지가 0이 될 때까지 계속 나누어 나온 나머지를 저장하고 그 저장된 나머지를 반대로 표현하면 변환이 완료된 것이다. 이것을 코드로 표현하면 문제 풀이는 끝난다. 또 한가지 주의할 점은 10부터 35까지는 숫자 표현이 불가능하므로 미리 문자열에 알파벳을 저장해두어..

문제 링크 https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 문제 문제 풀이 t = int(input()) def gcd(a, b): if b == 0: return a else: return gcd(b, a % b) for _ in range(t): arr = list(map(int, input().split())) k = arr.pop(0) sum = 0 for i in range(k): for j in range(k)..