분류 전체보기
-
7682. [Python]틱택토Python_알고리즘/Gold V 2024. 4. 17. 21:08
1. 문제 https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 구현 3. 파이썬 코드 while True: game = input() if game == "end": break game = list(map(str,game)) circle = game.count("O") cross = game.count("X") dot = game.count(".") if circle > cross: pr..
-
1456. [Python]거의 소수Python_알고리즘/Gold V 2024. 4. 14. 20:16
1. 문제 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 256MB 에라토스테네스의 체 3. 파이썬 코드 # 에라토스 테네스의 체를 end 범위까지 시행 def prime_check(end): prime_list = [False, False] + [True]*end for i in range(2,int(end**.5)+1): if prime_list[i]: for j in range(i*2,end+1,i)..
-
1141. [Python] 접두사Python_알고리즘/Silver I 2024. 4. 9. 21:12
1. 문제 https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB 정렬 그리디 알고리즘 3. 파이썬 코드 N = int(input()) # 단어 저장 word_list = [] # 단어 길이와 문자로 저장 for _ in range(N): word = input() word_list.append([len(word),word]) # 길이..
-
1253. [Python] 좋다Python_알고리즘/Gold IV 2024. 3. 13. 01:20
1. 문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 256MB 투 포인터 이분탐색 3. 파이썬 코드 N = int(input()) # 이분 탐색 num_list = list(map(int,input().split())) # 정렬 num_list.sort() cnt = 0 for i in range(N): # 시작 start = 0 # 끝 end = N-1 # 이분 탐색 진행 while start < end: # 시작 ..
-
1261. [Python]알고스팟Python_알고리즘/Gold IV 2024. 3. 6. 20:25
1. 문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 다익스트라 우선순위 큐 3. 파이썬 코드 import heapq N,M = map(int,input().split()) matrix = [ list(map(int,input())) for _ in range(M) ] # 방향배열 탐색 direction = [(0,-1), (-1,0), (0,1), (1,0)..
-
1916. [Python]최소비용 구하기Python_알고리즘/Gold V 2024. 3. 5. 01:02
1. 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 접근 방법 시간 제한: 0.5초 메모리 제한: 128MB 다익스트라 우선순위 큐 3. 파이썬 코드 import sys import heapq input = sys.stdin.readline N = int(input()) M = int(input()) matrix = [ [] for _ in range(N+1)] # 다익스트라 거리 distance ..
-
1753. [Python]최단경로Python_알고리즘/Gold IV 2024. 3. 3. 23:59
1. 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 256MB 다익스트라 3. 파이썬 코드 import sys import heapq input = sys.stdin.readline # 시작점을 기준으로 다익스트라 시작 def BFS(init): # queue 리스트 생성 queue = [] # 우선순위 큐 생성 heapq.heappush(queue,(..
-
2023. [Python] 신기한 소수Python_알고리즘/Gold V 2024. 2. 25. 15:10
1. 문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 4MB DFS(깊이 우선 탐색) 3. 파이썬 코드 # 재귀 제한 풀기 import sys sys.setrecursionlimit(10000) # DFS 함수 def backtracking(total, cnt): # 횟수가 N과 같으면 if cnt == N: # 값 출력 후 리턴 print(total) return # 2째 자리부..
-
9205. [Python] 맥주 마시면서 걸어가기Python_알고리즘/Gold V 2024. 2. 18. 15:11
1. 문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 2. 접근 방법 시간 제한: 1초 메모리 제한: 128MB 그래프 탐색 너비 우선 탐색 3. 파이썬 코드 import sys from collections import deque # 많은 인풋 처리를 위해 sys 사용 input = sys.stdin.readline T = int(input()) # 테스트 케이스 만큼 반복 for tc in range(T): store_cnt = ..
-
1569. [Python]정사각형으로 가리기Python_알고리즘/Silver II 2024. 2. 18. 14:57
1. 문제 https://www.acmicpc.net/problem/1569 1569번: 정사각형으로 가리기 정사각형으로 가려지는 점이란, 어떤 점이 그 정사각형의 한 변 위에 놓여져 있을 때, 정사각형으로 가려진다고 한다. 점이 N개가 주어진다. N개의 점 모두를 가릴 수 있는 정사각형을 구하는 프 www.acmicpc.net 2. 접근 방법 시간 제한: 2초 메모리 제한: 128MB 많은 조건 분기 3. 파이썬 코드 import sys input = sys.stdin.readline N = int(input()) square_point = set() min_x = sys.maxsize max_x = -sys.maxsize min_y = sys.maxsize max_y = -sys.maxsize che..