분류 전체보기
-
2644. [Python]촌수계산Python_알고리즘/Silver II 2023. 9. 4. 19:28
1. 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB DFS(깊이 우선 탐색) 3. 파이썬 코드 import sys # 많은 인풋 처리 input = sys.stdin.readline # DFS 함수 def DFS(start): # 시작 위치 1로 방문처리 visited[start] = 1 global cnt global end # matrix로 접근 for i..
-
17299. [Python] 오등큰수Python_알고리즘/Gold III 2023. 9. 1. 15:52
1. 문제 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 512MB 스택 3. 파이썬 코드 N = int(input()) num_list = list(map(int,input().split())) stack = [0]*N ans = [0]*N # 각 숫자가 몇개 나왔는지 체크해줄 딕셔너리 num_dict = {} for i in num_list: if i in num_dict: num_dict[i] += 1..
-
1527. [Python] 금민수의 개수Python_알고리즘/Silver I 2023. 8. 30. 19:24
1. 문제 https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB 재귀 3. 파이썬 코드 def DFS(num): # cnt 변수 글로벌 선언 global cnt # num 값에 "4" or "7" 추가 num = str(num) # 범위 내에 있으면 cnt 증가 if A 44 => 444 (값이 넘으면) 447(넘으면) 47 => 474(넘으면) 477(넘으면) 4로 돌아옴 초기값 : 7 ..
-
5002. [Python]도어맨Python_알고리즘/Silver II 2023. 8. 27. 21:02
1. 문제 https://www.acmicpc.net/problem/5002 5002번: 도어맨 첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X N: # 리스트가 존재하면 if words: # 값을 한개 더 뽑아본다 middle_check = words.popleft() # m_cnt 값이 w_cnt 값보다 큰 경우 if m_cnt > w_cnt: # m_cnt 값이 위에서 증가됐기 때문에 1 뺀다 m_cnt -= 1 # 한개 더 뽑은 값이 W 인 경우 if middle_check == "W": # w_cnt 값 1 증가 w_cnt += 1 # M 값이였던 check 값을 리스트에 왼쪽에 더해줌 words.appendleft(check) # M 인 경우 반복문 종료 else: break # m_cn..
-
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..
-
1012. [Python]유기농 배추Python_알고리즘/Silver II 2023. 8. 19. 23:43
1. 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 512MB DFS(깊이 우선 탐색) 3. 파이썬 코드 import sys input = sys.stdin.readline dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] # 깊이 우선 탐색 함수 def DFS(start): stack = [] stack.append(start) visited[start[0]][start[1]] = ..
-
1564. [Python]팩토리얼5Python_알고리즘/Silver II 2023. 8. 13. 15:09
1. 문제 https://www.acmicpc.net/problem/1564 1564번: 팩토리얼5 첫째 줄에 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. 또, 9보다 크거나 같다. www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB 수학 3. 파이썬 코드 N = int(input()) ans = 1 # 1 ~ N 값까지 반복문을 통해서 곱해나감 for i in range(1,N+1): # ans 값의 곱에 10^13 의 나머지를 계산해준다. # N값이 1,000,000 까지 들어오기 때문에 10^6 * 10^6 + 1의 값까지 10의 배수의 나머지를 취해준다. ans = (ans*i) % (10**13) # 만약 곱한 ans 가 10으로 나눠질 경우..