Python_알고리즘/Silver III
-
11727. [Python]2*n 타일링 2Python_알고리즘/Silver III 2023. 8. 26. 16:50
1. 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 256MB DP(Dynamic Programming) 3. 파이썬 코드 # 1 1 # 2 3 # 3 5 # 4 11 # 5 21 # 6 43 # 7 85 # 8 171 N = int(input()) # DP 설정 DP = [1, 3] for i in range(2,N): # 이전 값 + 이전 전 값 * 2 하면 다음 값 DP.append((DP[i-1] + DP[i-2..
-
9095. [Python]1, 2, 3 더하기Python_알고리즘/Silver III 2023. 8. 25. 21:12
1. 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 512MB DP(Dynamic Programming) 3. 파이썬 코드 # 1 = 1 1 # 2 = 1+1 2 2 # 3 = 1+1+1, 2+1, 1+2 3 4 # 4 = 1+1+1+1, 3+1, 1+3, 2+2, 1+1+2, 2+1+1, 1+2+1 7 # 5 = 1+1+1+1+1, 3+2, 2+3, 1+1+3, 1+3+1, 3+1+1, 2+2+1 1+2+2, 2+1+2 1+1+1+2, 2+1+1+1, 1+2+1+1, 1+1+2+1 13..
-
11899. [Python]괄호 끼워넣기Python_알고리즘/Silver III 2023. 8. 20. 00:06
1. 문제 https://www.acmicpc.net/problem/11899 11899번: 괄호 끼워넣기 첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다. www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 32MB 스택 3. 파이썬 코드 words = input() stack = [] for word in words: # 스택에 값이 있을때 if stack: # 만약 닫는 괄호의 경우 if word == ")": # 여는 괄호가 스택의 top 에 있으면 pop if stack[-1] == "(": stack.pop() # 외의 경우 append else: stack.append(word)..
-
2606. [Python]바이러스Python_알고리즘/Silver III 2023. 8. 19. 23:55
1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB DFS(깊이 우선 탐색) 3. 파이썬 코드 n = int(input()) m = int(input()) # 컴퓨터 갯수만큼 생성 computers = [[] for _ in range(n+1)] # 그래프 방식을 통해서 연결된 컴퓨터 리스트 생성 for __ in range(m): v1, v2 = map(int,input().spli..
-
1347. [Python]미로 만들기Python_알고리즘/Silver III 2023. 8. 2. 15:50
1. 문제 https://www.acmicpc.net/problem/1347 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB 구현 3. 파이썬 코드 N = int(input()) direction = input() # 현재 위치를 0,0 으로 기준으로함 current_pos = [0, 0] # 남쪽을 보고 서있으므로 남쪽을 1로 정함 current_see = 1 # 움직인 방향을 리스트에 저장 초기값으로 현재위치 answer_list = [curre..
-
2607. [Python]비슷한 단어Python_알고리즘/Silver III 2023. 8. 2. 15:46
1. 문제 https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 구현 3. 파이썬 코드 import copy N = int(input()) word_list = [] answer = 0 # 단어들을 리스트에 저장 for _ in range(N): word_list.append(input()) # 첫번째 단어의 갯수를 세기위한 딕셔너리 word_dict = {} # 단어의 길이 word_le..
-
1021. [Python]회전하는 큐Python_알고리즘/Silver III 2023. 8. 2. 15:18
1. 문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB Deque(덱) 3. 파이썬 코드 # deque 선언 from collections import deque N, M = map(int,input().split()) # 찾고자 하는 숫자 리스트 answer_list = list(map(int,input().split())) # 초기 인덱스값 index = 0 # deque 선..
-
3077. [Python]임진왜란Python_알고리즘/Silver III 2023. 7. 26. 20:22
1. 문제 https://www.acmicpc.net/problem/3077 3077번: 임진왜란 첫째 줄에 해전의 개수 N이 주어진다. (2 ≤ N ≤ 2500) 다음 줄에는 올바른 정답이 공백으로 구분되어 주어진다. 그 다음 줄에는 현우가 작성한 답안이 공백으로 구분되어 주어진다. 해전의 이름은 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 딕셔너리 브루트 포스 3. 파이썬 코드 N = int(input()) # 정답 리스트 생성 answer_list = list(map(str,input().split())) # 제출 리스트 생성 check_list = list(map(str,input().split())) # 정답 갯수 체크 cnt = 0 # 시간 절약을 위..
-
3273. [Python]두 수의 합Python_알고리즘/Silver III 2023. 7. 25. 16:16
1. 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 투 포인터 정렬 3. 파이썬 코드 # N, num_list, x 값을 받는 부분 N = int(input()) num_list = list(map(int,input().split())) x = int(input()) # num_list 를 탐색하기 위해서 오름차순 정렬 nu..