![]()
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제분석 맨 오른쪽부터 왼쪽으로 일정 높이를 가진 탑에서 신호를 송신하면 신호를 보낸 탑보다 높이가 높은 탑만 신호를 수신할 수 있다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서있다고 하자. 그러면, 높이가 4인 다섯번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 5인 탑을 지나쳐 높이가..
![]()
https://www.acmicpc.net/problem/14593 14593번: 2017 아주대학교 프로그래밍 경시대회 (Large) 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)는 2009년 제1회를 시작으로 2014년 제6회까지 개최된 아주대학교 학생들을 위한 프로그래밍 경시대회이다. 2017년, 다른 학교에서 활발히 www.acmicpc.net 문제 분석 문제의 설명중 대부분은 실제 경시대회 규칙인듯하여, 중요한 부분만 뽑아 분석하자. ! 해결한 문제 점수의 총합이 높은 참가자가 더 높은 순위를 가진다. ! 점수의 총합이 같은 경우, 제출 횟수가 적은 참가자가 더 높은 순위를 가진다. ! 점수의 총합과 제출 횟수가 같은 경우, 마지막으로 점수를 획득한 문제의..
![]()
문제 https://www.acmicpc.net/problem/13410 13410번: 거꾸로 구구단 일반적인 구구단에서 가장 큰 수는 마지막 항의 값이 제일 크다. 거꾸로 구구단에서는, 각 항에 구구단의 계산 결과로 나온 값을 뒤집어 저장을 한다. 이렇게 하면 가장 큰 값이 항상 마지막이 www.acmicpc.net 풀이 거꾸로 숫자를 출력하기 위해서 곱셈 결과를 str 타입 캐스팅하여 String으로 바꾼 뒤에 거꾸로 뒤집어 주고, 이를 int로 타입 캐스팅한다. 이를 리스트에 넣어서 max 값을 출력한다. 코드 n, k = map(int, input().split()) mul = [] for i in range(1, k+1): mul.append(int(str(n*i)[::-1])) print(ma..
https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 소스코드 k = int(input()) money = [] sum = 0 for i in range(k): num = int(input()) if num == 0: money.pop() else: money.append(num) for i in range(len(money)): sum += money[i] print(sum) 풀이 재민이가 입력할 케이스 k를 입력..
https://www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(
![]()
문제 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다. 출력 첫째 줄에 B진법 수 N을 10진법으로 출력한다. 예제 입력 1 ZZZZZ 36 예제 출력 1 60466175 [ 문제 분석 ] 진법이란 수를 셀 때 자릿수가 올라가는 단위를 기준으로 하는 셈법이다. 어떤 수를 n진법을 변환하려면 그 수를 0이 될 때까지 n으로 나누고, 그 나머지를 거꾸로..
![]()
https://70825.gitbook.io/koala_python_algorithm_study/ Python_Algorithm_Study - KOALA_Python_Algorithm_Study 스터디 진행자: 정다빈, 유완규 70825.gitbook.io 문제분석 입력받는 10진법의 숫자(N)를 다른 진법(B)으로 바꿔서 출력하는 문제이다. 또한, 10진법을 넘어가는 진법은 숫자가 아닌 알파벳이 나타나는데 알파벳은 대문자로 출력한다. 코드 문제풀이 10진법에서 다른 진법으로 바뀔 숫자(n)과 다른 진법(b)를 입력받는다. 그리고 하나의 딕셔너리에 각 진법에 해당하는 숫자 혹은 알파벳로 초기화시킨다. 왜냐하면 10진법에서 다른 진법으로 표현하기 위해서는 해당 값의 나머지를 필요로 하는데, 이 나머지가 해..
문제 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 해설 공유기의 갯수가 아니라 공유기가 설치되는 거리를 이분탐색으로 탐색하면 되는 문제였다. 완전탐색으로 할 경우엔 1부터 1000000000까지 가능하므로 시간초과가 나고 이분탐색으로 탐색시 logN이므로 시간안에 풀수있다. 공유기 거리가 늘어날수록 공유기 갯수가 줄어들므로 c보다 공유기 갯수가 적을때 거리(이분탐색하고자 하는 값)를 줄여가..
문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 해설 자른 종이안에 1, 0, -1 중 하나만 저장 되어 있는지 확인 하는 과정을 일일이 하면 시간 초과가 날까봐 어렵게 푼 문제이다.. (시간 복잡도 계산해보면 최악의 경우에도 가능) 구간합을 공부했던 것에 착안을 얻어 이차원 배열에서 d[i][j] = (1,1) ~ (i,j) 까지 -1,0,1의 개수를 저장해줬다 구조체를 사용했기 때문에 연산의 편의성을 위해 연산자 오버로딩을 ..
문제 링크 https://www.acmicpc.net/problem/2435 2435번: 기상청 인턴 신현수 첫째 줄에 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 주어진다. N은 온도를 측정한 전체 날짜의 수이다. N은 2이상, 100이하이다. K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사 www.acmicpc.net 풀이 입력받은 온도의 누적합(psum)을 구합니다. 온도를 측정한 날짜 N+1의 길이로 배열 psum을 만듭니다. (line 3) N+1인 이유는 첫째날이 포함되어 계산 시(left-1) 오류가 나지 않게 하기 위함입니다. (배열 맨 앞에 0을 추가) 반복문을 돌며 그 전날까지의 누적합과 해당 날짜의 온도를 더해줍니다. (line 5 ~ 6) 투 포인터를 이용..
![]()
문제링크 누적합을 이용한 문제 누적합이 뭐예요?? 리스트, 배열을 차곡차곡 누적하는 알고리즘이라고 보면 편할 듯하다. 문제 예제 입력 1 4 7 4 JIOJOIJ IOJOIJO JOIJOOI OOJJIJO 3 5 4 7 2 2 3 6 2 2 2 2 1 1 4 7 예제 출력 1 1 3 2 3 5 2 0 1 0 10 11 7 EX : (3,5) (4,7) 사이에 있는 J,I,O의 갯수를 출력 Solution 누적합을 저장할 osum,jsum,isum 배열을 맵 배열(arr)보다 1씩 크게 만들기 arr[i-1][j-1] == J 이면 jsum[i][j] +=1 하고 jsum[i][j] = jsum[i][j-1] + jsum[i-1][j] - jsum[i-1][j-1] + jsum[i][j] 더해준다. 전체소..
![]()
오늘은 백준 알고리즘 17179번 케이크 자르기 문제를 풀어보도록 하겠습니다. 문제부터 보겠습니다. 문제를 보시면 가장 작은 조각의 길이의 최댓값을 구하는 문제입니다. 탐색문제죠. 처음에 일반적으로 완전탐색을 고려합니다. 근데 범위를보니까 L이 400만이고 N이 1000입니다. 완전탐색으로 고려했을때 최소 40억의 연산이 필요하기 때문에 불가능하다는 사실을 알 수 있습니다. 연산의 수가 너무 크기때문에 이분탐색을 생각해보아야 합니다. 그래도 좀 까다로웠던 문제가 아닌가 싶습니다. 일단 저는 left = 0, right = l 로 잡고 mid = (left+right )/2로 했습니다. 여기서 mid는 가장작은 조각의 길이의 최대값이라고 가정하였습니다. 그리고 왼쪽부터 오른쪽으로 케이크를 자르도록 하였..
