본문 바로가기

Algorithm231

[백준] 3020번 개똥벌레 사용 언어 - Python3 문제 - 3020번 개똥벌레 (골드 5) 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 정답 이모스법, prefix 누적합 문제 (정답 맞춘 여부 O) 1. 이모스법 https://imoz.jp/algorithms/imos_method.html 막대의 시작 = +1 막대의 끝 = -1 prefix 누적합 구하면 겹치는 수 구할 수 있다. 2. 석순과 종유석 range(0,n) for문을 반복하면서 짝수라면 = 석순 = 왼쪽에 붙어있음 = 시작은 항상 0 line[0] += 1 끝은 .. 2023. 10. 24.
[백준] 11600번 구간 합 구하기 5 사용 언어 - Python3 문제 - 구간 합 구하기 5 (실버 1) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 정답 누적된 숫자들의 prefix 2차원 형태 (정답 맞춘 여부 X) 1. input graph[y][x] prefix도 [n+1][n+1] 배열로 만들기 2. 누적합 구할때 규칙 찾기 3. output 새로운 y1,x1,y2,x2 입력될 때마다 answer print 하기 import sys input = sys.stdin.readline n, m =.. 2023. 10. 24.
[백준] 2304번 창고 다각형 사용 언어 - Python3 문제 - 2304번 창고 다각형 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 정답 누적된 숫자들의 합 prefix 응용버전 (정답 맞춘 여부 X) 1. input 입력받은 x와 y를 graph 형태로 저장해주고, x_list, y_list로 따로 리스트에 저장해준다. 가장 큰 x와 y 값을 maxHeight, maxWidth로 저장해준다. 2. prefix, suffix 예시 그림처럼 x가 6이었는데 그 다음 값이 3이라면 x는 6으로 유지되어야 한다. 하지만,.. 2023. 10. 23.
[백준] 1912번 연속합 사용 언어 - Python3 문제 - 1912번 연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 정답 누적된 숫자들의 합 기억하기 (정답 맞춘 여부 X) 컴퓨터에게 기억하는 방법 알려주기 1. prefix라는 누적합 배열 생성 2. 값이 너무 작아지면, 기존의 값 무시하고 새로 시작하기 max(prefix[i] + arr[i], arr[i]) 3. 최대값 구하기 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int,input().spl.. 2023. 10. 23.
[백준] 2559번 수열 사용 언어 - Python3 문제 - 2559번 수열 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 정답 누적된 숫자들의 합 기억하기 (정답 맞춘 여부 X) 컴퓨터에게 기억하는 방법 알려주기 1. prefix라는 누적합 배열 생성 2. B만큼 떨어져 있는 누적합끼리 빼주기 3. 최대값 구하기 A,B = map(int,input().split()) arr = list(map(int,input().split())) # 누적합 배열 만들기 prefix = [0 for _ in range(A+1)] #.. 2023. 10. 23.
[백준] 14252번 공약수열 사용 언어 - Python3 문제 - 14252번 공약수열 14252번: 공약수열 서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘 www.acmicpc.net 정답 최대공약수 GCD(A,B) (정답 맞춘 여부 X) arr 한개씩 확인하면서 두 값 사이에 gcd 최대공약수가 있다면, 몇개의 값이 필요한지 검사한다. a+1부터 b까지 for문 반복하면서, gcd(a,j) 또는 gcd(b,j) 최대공약수가 존재한다면, tmp += 1, count += 1 최대공약수 존재하지 않고 for문이 끝났다면, count += 2 import sys input = sys.st.. 2023. 10. 23.
[백준] 2436번 공약수 사용 언어 - Python3 문제 - 2436번 공약수 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 정답 최대공약수 GCD(A,B), 최소공배수 LCM(A,B) (정답 맞춘 여부 X) 최대공약수 GCD(A,B) 1. GAP을 줄이기 공약수 = 일정한 간격으로 JUMP해서 A와 B 모두에 도달할 수 있는 수 GCD(12,8) = 0부터 8까지, 8부터 12까지 JUMP가 가능한 수 = GCD(8,12-8) GCD(A,B) = GCD(B-A,A) = GCD(A-(B-A), B-A) 두 수이 최대공약수 = 간격.. 2023. 10. 23.
[백준] 1407번 2로 몇 번 나누어질까 사용 언어 - Python3 문제 - 1407번 2로 몇 번 나누어질까 1407번: 2로 몇 번 나누어질까 자연수 N이 주어지면, 자연수를 유지하면서 N을 2로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 15의 www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 X) 모든 숫자는 1로 나누어 떨어짐 -> F(A)는 기본 최소 A이다. 2의 거듭제곱으로 나눠주면서, 최소 몇개가 2의 거듭제곱으로 나눠지는지 확인한 후 그 값만큼 더해준다. A부터 B 구간 = B-A+1 = B-(A-1) => A에 1을 빼주고 tmp_a와 tmp_b를 계산한 후, print(tmp_b - tmp_a) .. 2023. 9. 22.
[백준] 14232번 보석 도둑 사용 언어 - Python3 문제 - 14232번 보석 도둑 14232번: 보석 도둑 희대의 도둑 효빈이는 세계 최고의 보석가게 영선상에 잠입할 계획이다. 이 영선상은 최고의 보석가게답게 최고의 보안장치를 두고 있는데, 이 보안장치를 해제하지 않는다면 보석을 여러 개 www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 O) n을 i로 나눴을 때 0이라면 = 약수라면, n = n/i로 업데이트 반복한다. answer 빈 리스트를 만들어줘서 약수들 저장! n이 1이 아니라면, 마지막 n의 값을 answer에 추가해준다. 예. n=15 => [3], n=15/3=5 => [3,5] n = int(input()) answer = [] for i in range(2, int(n**0.5).. 2023. 9. 22.
[백준] 11653번 소인수분해 사용 언어 - Python3 문제 - 11653번 소인수분해 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 정답 최적화 - 정수론(수학) (정답 맞춘 여부 O) n을 i로 나눴을 때 0이라면 = 약수라면, n = n/i로 업데이트 같은 i로 나눈 값이 0으로 나누어 떨어진다면 계속 i로 나눠줌 안 나누어 떨어질 때까지! 반복 n = int(input()) if n == 1: print('') else: for i in range(2, n+1): if n % i == 0: while n % i == 0: print(i) n = n / i 레퍼런스 정답 깃허브 https://github.com/yyeongeun/codingtest/.. 2023. 9. 21.

티스토리툴바