![]()
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제분석 분류 구간합(Prefix sum) 다이나믹 프로그래밍(Dynamic Programming) 문제설명 배열의 크기 N 입력 구간합 구하는 횟수 M 입력 배열 입력, 구간합 좌표 입력 입력된 좌표 (시작X, 시작Y) (종료X, 종료Y) 사이의 구간을 입력 구간합 -> O(N)의 속도로 문제 도출 입력 4 3 1 2 3 4 2 3 4 5 3 4 5 6..
![]()
2504번: 괄호의 값 (acmicpc.net) 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 소스코드 문제풀이 많은 시간을 투자했는데 결국 구글링의 힘을 빌려 알고리즘을 보고 구현만 직접 한 문제이다. 어떤 변수를 통해서 값을 곱하고 나눠야 하지않을까 까지는 접근하였는데, 너무 복잡하게 생각했는지 아니면 남은 한 문제만 빨리 해결하고 싶어서 그랬던 건지 직전 인덱스의 값만 보고 result에 더할 생각을 하지 못했다. 결국 내가 생각한 방법이 틀렸구나 모르겠다 하고 검색한 것인데 예상외로 너무 단순해서 ..
![]()
https://www.acmicpc.net/problem/14627 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 www.acmicpc.net [문제 해석] 이 문제는 이분 탐색 문제로, 최소값과 최대값을 고려하면서 적절한 값을 찾아가는 문제이다. 이 문제에서 주의할 점은 라면에 넣을 파의 양이라는 점이다. [소스코드] S, C = map(int, input().split()) pa = [] for _ in range(S) : pa.append(int(input())) start, end =..
![]()
https://www.acmicpc.net/problem/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 문제 분석 배열에서 일정 범위 a~b에 정수 k를 더하는 명령을 여러 번 수행하는 문제입니다. 단순히 매 명령마다 배열에서 a~b까지 k를 더하도록 구현하면 시간복잡도가 O(NM)이 되어 시간 안에 문제를 풀 수 없습니다. 더 좋은 방법은, 명령의 범위 a, b와 더할 숫자 k를 기록하는 배열을 만들고, 누적합을 이용하여 원래 배열에 더해주는 것입니다. 이렇게 구현하면 시간복잡도는 ..
![]()
백준 1644 소수의 연속합 Intro Solution 입력되는 수보다 작은 소수들을 합하여 입력된 수를 만들어야 하고, 해당 소수들은 연속된다. 먼저 에라토스테네스의 체를 이용하여 입력 이하의 소수의 목록을 만든다. 소수 목록의 누적 합 리스트를 만든다. 투 포인터(l, r)를 이용해 포인터를 뒤로 옮겨가며 답을 구한다. 3.1. 포인터 l부터 포인터 r까지의 소수의 합이 n과 동일할 때 정답으로 출력할 변수에 1을 더한다. 3.2. 소수의 합이 n보다 작으면 오른쪽 포인터를 한 칸 이동한다. 3.3. 소수의 합이 n보다 크거나 같으면 왼쪽 포인터를 한 칸 이동한다. Code def primes(n): # 에라토스테네스의 체 if n < 2: return [0] is_prime = [True] * (n..
https://www.acmicpc.net/problem/3181 3181번: 줄임말 만들기 꿍은 만사가 귀찮아서 말을 하기도 귀찮아 한다. 그래서 하려는 말을 대신해줄 줄임말을 만들려고 하는데 나름 규칙을 만들었다. 하려는 말은 최소 하나 이상의 단어를 포함하는데 각 단어들은 www.acmicpc.net 문제분석 'i', 'pa', 'te', 'ni', 'niti', 'a', 'ali', 'nego', 'no', 'ili' 의 문자열이 입력값에 있으면 출력 시 앞글자를 따오면 안된다. 소스코드 a = input().split() li1 = ['i', 'pa', 'te', 'ni', 'niti', 'a', 'ali', 'nego', 'no', 'ili'] r = a[0][0] for i in range(..
![]()
14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 해석 NxM 크기의 직사각형 안에 있는 로봇청소기가 청소한 칸의 개수를 구하는 문제이다. 청소기는 특정 알고리즘에 따라 움직이므로 해당 알고리즘을 그대로 구현하여 시뮬레이션 해야한다. 코드 문제 풀이 처음 변수 선언 부분부터 설명하자면 arr는 NxM의 직사각형이 들어갈 list이고 0은 빈칸, 1은 벽, 2는 이미 청소한 칸을 나타낸다. flag는 로봇청소기가 해야할 알고리즘 단계를 나타내며 0은 문제의..
![]()
코드 print("FA") 풀이 이 문제의 재미있는 점은 사실 모든 자연수는 FA라는 것으로 귀결된다는 점이다. 두 자리 이상의 자연수는 함수를 거듭할수록 작아지고, 한자리수가 되면 그 결과값이 바뀌지 않으므로 모든 자연수는 FA가 된다. 이 부분을 이용하여 어떤 입력이 들어오든 단순히 'FA'를 출력하는 코드를 작성하였다.
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 분석 크기가 n인 집합을 v1 그리고 크기가 m인 집합을 v2라고 하였을 때, v1의 원소 중 v2보다 작은 것이 몇개인지 카운트 하는 문제이다. 다양한 풀이 방법이 있지만, 완전 탐색으로 풀었다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..
![]()
문제 https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net '문자열의 앞과 뒤에 공백이 있을 수도 있다'는 문제 조건에 주의하여야한다. 코드 #1 sentence = input() print(len(sentence.split())) #2 바로 적용 print(len(input().split())) 풀이 - 'The Curious Case of Benjamin Button' 이라는 예제를 입력 받았을 때, split() 함수가 적용되면 sente..
![]()
https://www.acmicpc.net/problem/1673 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net 문제 코드 풀이 문제 해석이 조오끔 난해했다. 맨처음 n마리의 치킨을 시키면 그만큼의 도장이 또 생기고, 그를 k 번 나눈 몫만큼의 치킨을 또 시킬 수 있고, 그만큼의 도장이 또 생긴다. 이렇게 생긴 도장이 맨처음 시킨 치킨 n마리만큼의 도장//k 만큼을 합친 것 만큼 또 합쳐져 시킨을 시킬 수 있다. 이를 while 문으로 계속 돌려 끝까지 돌린다음 나온 총 먹은 치킨 값이 답으로 도출이 된다.
![]()
문제분석 분류 수학 구현 문제설명 입력 출력 소스코드
