https://www.acmicpc.net/problem/1371 1371번: 가장 많은 글자 첫째 줄부터 글의 문장이 주어진다. 글은 최대 50개의 줄로 이루어져 있고, 각 줄은 최대 50개의 글자로 이루어져 있다. 각 줄에는 공백과 알파벳 소문자만 있다. 문장에 알파벳은 적어도 하나 이 www.acmicpc.net 문제해석 입력된 글중 가장 많이 나온 알파벳을 찾아 출력하는 프로그램을 작성하는 문제이다 코드 word = [0 for i in range(26)] while True: try: inStr = str(input()) for s in inStr: if s.islower(): word[ord(s)-97] += 1 except EOFError: break for i in range(26): if..
Koala - 11기
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 알고리즘 분류 정렬 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 1. 국어 점수가 감소하는 순서로 2. 국어 점수가 같으면 영어 점수가 증가하는 순서로 3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 ..
문제 :2947번: 나무 조각 (acmicpc.net) 2947번: 나무 조각 첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다. www.acmicpc.net 코드 코드 설명 위 문제는 버블정렬(bubble sort)과정을 전부 출력하는 것이다. 그래서, 먼저 for문을 이용해 버블정렬을 진행할 수들을 입력 받아서 배열에 저장해준다. 그 후, while문을 통해서 완전히 정렬될 때 까지 반복을 해주는데 내부에 for문을 이용하여 인접한 자리의 수끼리 비교를 한 후 오름차순이 될 수 있도록 바꿔주거나 그대로 둔다. 이때, 인접한 자리의 수가 변경된 경우, 변경된 배열을 출력을 해준다. w..
Problem Solution 1) 변수 및 배열 선언 및 입력 받기 2) 두 개의 포인터를 사용하여 합이 0에 가까운 두 수를 찾기 두 개의 포인터 'left'와 'right'를 배열의 양 끝으로 초기화하고 합이 0에 가까운 두 수를 찾기 위해 'left' 포인터와 ' right' 포인터를 이동시키면서 최적의 값을 찾는다. 반복문은 'left'와 'right'가 같아질 때까지 계속 실행된다. 최솟값을 저장하는 'minVal'을 갱신하면서, 합이 0에 더 가까워질 때마다 그 때의 두 수를 'ans'에 저장한다. 3) 'ans' 벡터에 저장된 두 수를 출력한다. Answer #include #include #include #include using namespace std; int main() { int ..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net # 풀이 일반적인 이중포문으로 생각하고 돌리면 쉽지만, 시간 초과가 난다. 이럴 때 사용하는것이 투포인터인데, 투포인터를 사용하여 시간복잡도를 줄이면 된다. m=3이고 배열 1,2,3,5,4 라고 생각했을 때, 먼저 정렬을 해준다. 그러면 1,2,3,4,5인데 이때, 두수를 비교해보자 1과 1: 차이가 0이므로 틀림. 1과 2: 차이가 1이므로 틀림. 1과 3: 차이가 2이므로..
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net Algorithm k개의 구간안에 있는 초밥들과 쿠폰으로 받을 수 있는 초밥중 서로 다른 초밥 개수의 최댓값을 구하는 문제이다. 구간을 정해주기 위해 투포인터를 사용하였다. 서로 다른 초밥의 개수를 구하기 위해 딕셔너리를 사용하였다. 회전초밥이므로 확인해야 하는 구간은 총 n개이고, 예제 입력1에서 25,7,9,7을 고르는 경우도 있으므로 초밥종류를 가..
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net # 문제 설명 - N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다"라고 한다. - N개의 수가 주어질 때, 그 중에서 좋은 수의 개수는 몇 개인지 출력한다. 수의 위치가 다르면 값이 같아도 다른 수이다. # 풀이 방법 - 오름차순 정렬 후 각각의 수가 좋은 수인지 찾는다. - 투포인터 (s=0, e=n-1)를 통해 두 인덱스 값의 합이 목표보다 작으면 e--, 크면 s++를 해준다. -..
https://www.acmicpc.net/problem/2234 코드 # 성곽 # 복습 횟수:2, 01:30:00, 복습필요O import sys from collections import deque si = sys.stdin.readline M, N = map(int, si().split()) # 가려는 방향에도 벽이 있는지를 체크해야한다. 북남서동 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] tmp_list = [] for i in range(N): tmp_list.append(list(map(int, si().split()))) graph = [[[] for i in range(M)]for i in range(N)] def converter(i, j): val = tmp_l..
1. 문제 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 2. 코드 n = int(input()) def fib(n): fibs = [0, 1, 1, 1] if n == 1 or n== 2 or n==3: print(1) exit() else: for i in range(4,n+1): fibs.append((fibs[i-1])+fibs[i-3]) # print('fibs :',fibs) return fibs[-1]..
문제 출처 : https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t..
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제 해석 저장된 사이트 주소의 수 N 비밀번호를 찾으려는 사이트 주소의 수 M 를 입력하여 찾고 싶은 주소의 비밀번호를 출력하는 문제이다. 찾으려는 주소를 차례대로 하나씩 출력하면 된다. 코드 N, M = map(int, input().split()) c = dict() for i in range(N + M): if i < N: a, b = map(str, inpu..
문제 https://www.acmicpc.net/problem/9625 알고리즘 분류 - 다이나믹 프로그래밍 코드 K = int(input()) dp = [[0 for _ in range(2)] for _ in range(K+1)] dp[0] = [1, 0] dp[1] = [0, 1] for i in range(2, K+1): dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] print(dp[K][0], dp[K][1]) 풀이 직접 써서 계산해보면 1번째: b 2번째: ba 3번째: bab => ba + b 4번째: babba => bab + ba 로 n-1번째와 n-2번째를 더한 것이 n번째임을 알 수 있다 때문에 b와 a의 개..
