네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 2. 풀이 과정 1. 주어진 문자열이 "AFCA"이라면 A = 1000+1, F = 100, C = 10으로 자릿수만큼 수를 더해준다. 다음 문자열을 읽을 때는 이 값에 누적으로 더해주면 된다. 2. 누적으로 더한 수들을 정렬해서, 제일 큰 수를 가진 알파벳부터 9 => 8 => 7 ... 순으로 할당하는 것이 제일 큰 수를 만들 수 있다. 따라서 출력값은 (해당 알파벳이 가진 수..

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2. 풀이 과정 현재 위치에서 선택할 수 있는 방안은 2가지다. 1) 이전 값에 연속해서 더하기 2) reset하고 현재값부터 다시 시작하기 따라서, 현재값과 연속해서 더한 값 중에 큰 수를 선택해나간다. n = int(input()) arr = list(map(int, input().split())) for i in range(1, len(arr)): arr[i] = max(arr[i], arr..

1. 문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이과정 아스키코드로 오름차순으로 정렬한 후, 뒤에서부터 출력한다. print(*sorted(input())[::-1],sep='')

1. 문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 2. 풀이 과정 n = int(input()) A = list(map(int, input().split())) A.sort() l = 0 r = n-1 result = [A[l], A[r]] while l < r: a = A[l] + A[r] if abs(a) < abs(sum(result)): #절댓값이 제일 작은 값 저장 result = [A[l],..

1. 문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 2. 풀이 과정 n이 5이고 검사하는 값을 mid = 6이라고 할 때, 6보다 작거나 같은 값의 수는 아래와 같다. 1*1, 1*2, 1*3, 1*4, 1*5 2*1, 2*2, 2*3, 2*4 ,2*5 3*1, 3*2, 3*3, 3*4, 3*5 4*1, 4*2, 4*3, 4*4, 4*5 5*1, 5*2, 5*3, 5*4, 5*5 각 행에서 6보다 작은 값의..

1. 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 2. 풀이과정 입력된 값을 하나씩 읽어가면서, 결과 배열에 들어갈 위치를 이진탐색을 통해 찾는다. #입력 : 10 20 15 30 70 50 10 10 20 10 15 10 15 30 10 15 30 70 10 15 30 50 결과 배열의 마지막 값보다 크면 제일 뒤에 추가하고, 아니면 자기보다 작은 값들의 뒷자리를 차지하도록 만든다. 방법 1) 이진탐색 구현 import sys inp..

1. 문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 2. 풀이 과정 방법 1) 다음 코드에서는 사전 자료형을 사용하였다. - 이진탐색을 시도했으나 시간 초과로 실패하였다. 하나의 값을 찾을 땐 효율적이지만, 다수의 값을 찾고 그 값들이 중복 가능할 때는 특정 값의 개수를 저장해놓고 꺼내서 출력하는 것이 더 빠르다. import sys input = sys.stdin.readline n = int(inpu..

1. 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 풀이 과정 방법 1) 자신의 앞에 있는 값들 중 자신과 작으면서 길이가 최대인 값에 1을 더한 값이 자신이 최대가 될 수 있는 값이다. n = int(input()) arr = list(map(int, input().split())) result = [0]*(n) result[0] = 1 for i in..

1. 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2. 풀이 과정 피보나치 수열이 사용되는데, 이유는 아래 그림을 참고하길 바란다. n= int(input()) def case_count(n): if n

1. 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 2. 풀이과정 방법 1) DFS 이용 - Python 시간 초과, PyPy로 제출 import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [input() for _ in range(n)] visited = [False]*26 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] r..