minimimi

문제출처] https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문제요약 문자열에서 문자가 연속하는 문자로만 이루어져있는 지 판단 풀이 ord() 와 chr() 함수의 사용 ord()는 문자를 아스키코드 정수형으로 변환해주는 파이썬 내장 함수이다. 이를 이용해서 char 형의 알파벳 혹은 숫자를 확인 가능하다. ord('A')-ord('A') # 0 ord('B')-ord('A') # 1 ord('Z')-ord('A'..

문제출처] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제요약 1차원 배열 누적합(PREFIX SUM) 알고리즘 문제 풀이 누적합의 기본 알고리즘은 N부터 M까지의 합을 (M까지의 합) - (N까지의 합) 을 이용하여 계산하는 것이다. 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline n,m = map(int, input().split()) number..

문제출처] https://www.acmicpc.net/problem/9184 문제요약 재귀 함수를 다이나믹 프로그래밍으로 구현하기 풀이 식이 모두 주어줘 있는 재귀 함수이므로 다이나믹 프로그래밍만 구현해주면 된다. 다이나믹 프로그래밍에서 가장 중요한 점은 "이미 계산했던 값은 다시 계산하지 않는다."이다. 그래서 dp라는 리스트를 만들어 계산했던 값은 저장해 주면 된다. dp 리스트를 선언할 때 인풋값의 범위가 -50 ~ 50 이므로 사이즈를 102로 하였다. 음수값이 들어오더라도 리스트의 뒤의 값부터 인덱싱을 하기 때문에 추가적인 코드를 짤 필요는 없다. 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline dp = [[[False for _..

문제출처] 문제요약 트리의 부모 찾기 (find parent) 문제 풀이 파이썬 딕셔너리를 이용한 그래프 구현 https://zero-rabbit.tistory.com/47 [백준] 11724 연결 요소의 개수 문제출처] https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양.. zero-rabbit.tistory.com find parent def find_parent(start): for i in tree[start]: if parents[i] == 0: parents[i] = start find_par..

문제출처] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 같은 숫자를 포함하는 순열을 구해야 된다. 파이썬에서 그러한 함수를 지원하지 않기 때문에 일반 순열 함수를 이용하여 순열을 구한다음 set 자료형을 사용하여 중복을 제거해주었다. 주의할 점은 음수 나누기 양수를 할 때, 음수를 우선 양수로 변환한 다음 나눗셈을 한 뒤 다시 음수로 변화해줘야 된다는 점이다. 소스코드는 Pytho..

문제출처] https://www.acmicpc.net/problem/4949 문제요약 스택을 활용한 괄호 확인하기 문제 풀이 우선 문장이 주어지므로 문장에서 괄호만 리스트로 빼내야 된다. parentheses = ['(', ')'] square_brackets = ['[', ']'] while True: sentence = input() if sentence == '.': break brackets_list = [] for text in sentence: if text in parentheses or text in square_brackets: brackets_list.append(text) 반복문을 돌면서 독점(.)이 나올때까지 문장을 입력받는다. 괄호는 리스트로 미리 정의해 두었다. text가 괄호에..

문제출처] https://www.acmicpc.net/problem/3036 문제요약 톱니바퀴가 맞물려 돌아갈 때 회전 수 구하는 문제 풀이 첫 번째 링과 각 링의 최대 공약수를 구하여 각각 나누어 준 후 첫 번째 링을 최대 공약수로 나눈 몫은 분자로 나머지 링을 최대 공약수를 나눈 몫은 분모로 취하면 된다. 최대 공약수를 구하는 방법은 2609번 최대공약수와 최소공배수 문제의 유클리드 호제법을 이용하면된다. 2609번문제풀이 링크] https://zero-rabbit.tistory.com/53 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline def gcd(a, b): # 무조건 a > b 유지 if a > b: pass else: a, ..

문제출처] https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제요약 최소공배수 구하기 풀이 2609번 최대공약수와 최소공배수 문제와 같이 유클리드 호제법을 이용하여 풀면 된다. 2609번문제풀이 링크] https://zero-rabbit.tistory.com/53 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline def gcd(a, b): # 무조건 a > b ..