히히

백준 11053 : 가장 긴 증가하는 부분 수열 (Python)

문제 : www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 조금 찾아봤다. 쉬운 문제였다. A에 수를 입력받고 dp에 해당 위치까지 가장 긴 부분 수열을 저장한다. i번째의 수를 포함한 dp는 i보다 작은 위치를 확인하며 [본인보다 작은 A값의 dp중 가장 큰 dp + 1 ]을 한 값이다. n = int(input()) A = list(map(int, input().split(..

백준 11726번 : 2xn 타일링 (Python)

문제 : www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 dp에 2x1부터 경우의 수를 입력한 뒤 입력된 수를 참고하여 다음 2xn 크기의 타일링을 계산한다. 현재 주어진 타일로 겹치지 않게 가장 작게 사각형을 채우는 방법은 ①세로 타일 하나로 2x1 만들기 ②가로 타일 두개로 2x2 만들기 이다. ex) 세로 타일 두개로 2x2를 만드는 경우는 ①의 경우에 속하므로 겹치는 경우이다. 따라서 2xn 타일링 경우의 수는 [ 2x(n-1)에 ①을 붙이는 경우 + 2x(n-2)에..

백준 1003번 : 피보나치 함수 (Python)

문제 : www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 기존 피보나치와 동일하게 해결하면 된다. result 리스트에 초기 0의 출력 수 , 1의 출력 수를 각각 저장한 뒤 result[i]의 출력 수는 i-1의 출력수 + i-2의 출력수 값이다. n = int(input()) for _ in range(n): case = int(input()) result = [[1,0],[0,1]] for i in range(2,case+1): temp = [result[i-1][0]+result[i-2][0] ,result[i-1][1]+result[i-2]..

백준 1541번 : 잃어버린 괄호 (Python)

문제 : www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 숫자와 부호를 나누어 리스트를 만든다. (nums, chars) 주어진 부호는 +와 -밖에 없으므로 모든 +를 먼저 한 뒤에 나온 모든 수에 대해 -를 하면 최소값이 나온다. a-b+c가 있을 때 a-(b+c) = a-b-c가 되기 때문 chars에서 + 부호의 인덱스가 i라면 nums리스트에서 i와 i+1 인덱스의 값을 더해 nums[i]에 저장한다. 이때 이미 더해진 값임을 표시하기 위해..

백준 2667번 : 단지번호붙이기

문제 : www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 너비 우선 탐색으로 해결하였다. 모든 위치를 한번씩 방문하고 해당 위치에 집이 있을 경우(==1) 큐에 추가한다. while que에서 상하좌우 중 집이 있을 경우 큐에 추가한다. 큐에 추가를 할때 마다 k + 1을 해주고, 큐가 끝나면 num리스트에 k값(단지당 집의 개수)을 추가한다. 최종적으로 num리스트의 길이와 정렬된 num을 출력한다. N = int(input()) house = [] f..

백준 11399번 : ATM

문제 : www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 가장 시간이 조금 걸리는 사람부터 기계를 쓰도록 한다. 가장 앞사람의 시간은 총 n번 더해지고 뒤로 갈수록 -1번씩 더해진다. n = int(input()) atm = list(map(int, input().split())) atm.sort() result = 0 for i in atm: result += i*n n -= 1 print(result)

백준 2579번 : 계단 오르기

문제 : www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 엄청 틀린 문제다. 두번 연속이 안된다는 조건 때문에 현재 연속 상황을 변수로 넣고 하며 다이나믹 프로그래밍을 진행했다. 결국 답을 찾아본 문제다. dp에 계단을 더할때 현재 계단만 더할 생각을 했다. ① i - 2 최대값 + i 계단 / ② i - 3 최대값 + i - 1 계단 + i 계단 중 더 큰 값을 dp값으로 지정해주면 된다. 처음에는 ③ i - 4 최대값 + i - 2 계단 + i - 1 계단 을 ..

백준 9095번 : 1, 2, 3 더하기

문제 : www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 쉬운 문제니 보자마자 다이나믹을 떠올려야 한다. n이라는 숫자가 있으면 n을 1, 2, 3 의 합으로 만들수 있는 경우의 수는 n-1을 1,2,3의 합으로 만드는 경우 + n-2를 1,2,3의 합으로 만드는 경우 + n-3을 1,2,3의 합으로 만드는 경우이다. 각 마이너스된 숫자에 1, 2, 3을 더하면 n이 되기 때문이다. num에 입력을 받고 sum123에 num최대값까지 경우의 수를 입력한 다음 해당하는 부분을 출력한다. n = int(input()) num = [] sum123 = []..

[Pandas] 데이터 프레임 그래프로 나타내기

1. 데이터 프레임 만들기 2. 그리기 3. 속성 변경하기 데이터 프레임 만들기 result = pd.concat([resultA,resultB], axis=1) result.columns = ['A', 'B'] print(result) resultA와 resultB를 합쳐 result라는 데이터 프레임을 생성하였다. 범위에 해당되는 인덱스 수를 카운트한 데이터이며 A와 B를 비교하는 그래프를 그리려 한다. 그리기 그래프의 모양 중 '선 형태의 그래프, 가로축의 바, 세로축의 바' 세가지 그래프를 다뤄보려 한다. A와 B 그래프를 겹쳐 그릴것이므로 두개를 써주면 하나의 그래프에 겹쳐서 나온다. import matplotlib.pyplot as plt plt.plot(result.index, result...

백준 7576번 : 토마토 (Python)

문제 : www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 먼저 반복문을 돌아 notyet에 익지 않은 토마토 개수를 저장하고, 익은 토마토를 큐에 쌓는다. 큐에서 pop했을 때 상하좌우중 익지 않은 토마토(0)일 경우 0을 익은 토마토의 넘버 + 1로 변경한 뒤 좌표를 큐에 쌓는다. 큐가 끝났는데 notyet이 남아있다면 -1, 아니라면 마지막 토마토 넘버 - 1 을 출력한다. from collections import deque M, ..