alpyrithm_알파이리즘

9012 괄호 www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 풀기 전 공부할 것 : 자료 구조, 문자열, 스택 풀이 1 vps를 확인하는 check 함수를 만든다. cnt를 0으로 초기화한다. 그리고 vps에서 괄호를 하나씩 꺼낸다. 꺼낸 괄호가 ')' 모양이라면 cnt에 더하기 1을 한다. 꺼낸 괄호가 '(' 모양이라면 cnt가 0보다 작거나 같으면 올바른 괄호가 아니다. cnt가 0보다 클 때 cnt에 빼기 1을 한다..

1837 암호제작 www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 www.acmicpc.net 문제 풀기 전 공부할 것 : 큰 수 연산 풀이 k보다 작은 소수로 p가 나누어 떨어지면 좋지 않은 암호이기 때문에 k보다 작은 소수들을 찾아야 한다. k보다 작은 소수를 찾았다면 각각의 소수로 p를 나눌 수 있는지 확인하고 그 결과를 출력하면 된다. p, k = map(int, input().split()) prime = [False, False] + [True] * (k-2) for i in..

1244 스위치 켜고 끄기 www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제 풀기 전 공부할 것 : 구현 풀이 on_off를 통해 1이면 0으로 바꾸고 0이면 1로 바꿀 수 있도록 한다. 학생수만큼 for문을 돌면서 남학생인 경우, 여학생인 경우로 나눠서 스위치 작업을 진행한다. 출력할 때 20개씩 끊어서 출력한다. import sys input = sys.stdin.readline on_off = {1:0, 0:1} n = int(input()) ..

5347 LCM www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 정수론 유클리드 호제법 풀이 a와 b의 최소 공배수를 구하는 방법은 a와 b를 곱하고 a와 b의 최대 공약수를 나누는 방법이 있다. 따라서 최대 공약수를 구하는 gcd 함수를 정의한다. 유클리드 호제법을 이용한다. 그리고 최소 공배수를 구한다. import sys input = sys.stdin.readline def gcd(a, b): while b: mod = b b = a % b ..

10211 Maximum Subarray www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 누적 합 풀이 연속하는 부분 배열의 원소의 합이 가장 큰 것을 찾는 문제이다. dp를 이용해서 해결할 수 있다. 연속하는 부분 배열이기 때문에 이전의 값에서 현재 값을 더한 값(dp[i-1]+arr[i])과 현재 값(arr[i])을 비교해서 더 큰 값을 저장하면 된다..

2776 암기왕 www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 문제 풀기 전 공부할 것 : 이분 탐색, 정렬 풀이 1 수첩1에 있는 숫자를 set으로 입력받는다.(같은 숫자를 여러 번 봐도 하나만 적혀 있으면 된다.) list로 받으면 시간 초과가 발생한다. 수첩2에 있는 숫자를 for문을 통해 반복하면서 수첩1에 있는 숫자인지 확인한다. import sys input = sys.stdin.readline t = int(input()) for _ in range..

11441 합 구하기 www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 문제 풀기 전 공부할 것 : 누적 합 풀이 구간의 합을 구하는 문제로 누적합을 이용하면 쉽게 해결할 수 있다. 누적합 cum array를 구한다. cum에 nums[0]을 넣어둔다. for문으로 반복하면서 cum의 마지막 숫자(지금까지 누적합)와 현재 nums를 더하면 만들 수 있다. i, j 구간의 합을 출력한다.(i..

1431 시리얼 번호 www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 문제 풀기 전 공부할 것 : 정렬 풀이 n과 시리얼 번호를 입력받는다. 모든 자릿수의 합(숫자만)을 구하는 sum_num 함수를 정의한다. 시리얼 번호를 lambda 함수를 통해 길이, 모든 자릿수의 합, 사전 순으로 정렬한다. 시리얼 번호를 하나씩 출력한다. import sys input = sys.stdin.readline def sum_num(s): res = 0 for i ..