본문 바로가기

전체 글213

종강하며... 어느덧 1학기 종강학기 중에 이래저래 바빴고 포스트도 뜸했으나어쨌든 짬짬이 달려서 플래티넘을 달았다포스트 내역을 보니 PS 시작한 지 1년이 조금 안 되는 것 같은데느리다면 느리고 빠르다면 빠른 성과인 듯한...나는 나름 만족한다 플래티넘은커녕 골드조차 높아 보였는데 어쨌든 되긴 했으니 어제의 나보다 나아졌다면 틀림없이 성장한 것 그리고 최근 관심사가 AI 쪽으로 이동한 듯이번 학기 DL 관련 전공을 두 개 수강했는데 둘 다 꽤 재밌었고 좋은 경험이었음 rapid한 것이 마음에 든다ㅎㅎ 2025. 6. 23.
백준 7453: 합이 0인 네 정수 문제풀이 백준 분류 상으로는 이분 탐색을 사용하는 문제라 되어 있으나 다소 다르게 풀이이분 탐색 버전으로 풀어보지 않아서 무엇이 더 효율적인 풀이인지는 모르겠다.A, B, C, D, = [], [], [], []for i in range(n): arr = list(map(int, input().split())) A.append(arr[0]) B.append(arr[1]) C.append(arr[2]) D.append(arr[3])일단 입력을 열로 분리해서 A, B, C, D 배열을 각각 만들어 주었다. 생략해도 무방한 단계지만 직관성을 위해... A, B 원소의 조합을 구한 뒤 해당 원소와 절댓값이 같고 부호가 다른 값을 C, D 조합에서 찾는 방식으로 풀이한다.A, B, C,.. 2025. 6. 23.
백준 3015: 오아시스 재결합(python) 문제어렵다... "n명의 사람들 a, b, c, ... n이 서 있을 때 b의 키가 a보다 크다면 a는 b부터 n까지의 모든 사람을 보지 못함"의 아이디어를 떠올리는 게 중요한 듯 하다.N명의 사람들을 arr 배열에 저장하고, arr의 원소 i에 대해 i 다음의 사람들을 스택에 넣었다 빼면서 볼 수 있는 사람 수를 카운트한다.for i in arr: # i와 stack[-1]에 대해 카운트 case 1: 현재 사람이 스택 최상단의 사람보다 키가 클 경우while stack and i > stack[-1][0] # stack에는 (키, 개수) 형태로 저장 res += stack.pop()[1] # 다음 사람을 제거하고(조합에 포함되었으므로) 그 카운트를 결과에 추가현재 사람(i)이 스택 최상단 사람(sta.. 2025. 3. 2.
백준 1504: 특정한 최단 경로(python) 문제풀이 출발 지점 s와 도착 지점 e에 대해 v1, v2를 모두 지나는 최단 경로는 ①s -> v1 -> v2 -> e 또는 ②s -> v2 -> v1 -> e이다.출발 지점을 인자로 전달받는 dijkstra() 함수를 작성해 다익스트라 알고리즘을 사용하면def dijkstra(start): dist = [sys.maxsize for _ in range(N + 1)] visited = [False for _ in range(N + 1)] pq = PriorityQueue() dist[start] = 0 pq.put((0, start)) # pq = (거리, 노드) while pq.qsize() > 0: d, s = pq.get() if visi.. 2025. 2. 28.
백준 1238: 파티(python) 문제풀이 각 집에 대해, X에서 집으로 가는 경로와 집에서 X로 가는 경로를 더한 값이 최대인 집을 찾아야 한다. X->집과 집->X를 모두 구해야 하므로 모든 지점에서 다른 모든 지점까지의 최단 거리를 구하기 위해 플로이드-워셜 알고리즘을 사용하였으나, 플로이드-워셜 알고리즘의 시간 복잡도는 노드 개수 V에 대해 \(O(V^3)\)이므로 시간 초과 오류가 발생한다.더보기플로이드-워셜 코드 참고import sysinput = sys.stdin.readlineN, M, X = map(int, input().split()) # N=학생(노드), M=도로(간선), X=목적지(노드)dist = [[sys.maxsize for _ in range(N + 1)] for _ in range(N + 1)]for i i.. 2025. 2. 28.
백준 1644: 소수의 연속합(python) 문제풀이 에라토스테네스의 체 알고리즘을 사용해 N 이하 소수들을 배열에 저장한 후, 해당 배열에서 투 포인터 기법으로 부분합을 구하여 풀이한다.a = [False, False] + [True] * (N - 1) # [0, 1, 2, 3, ... N]primes=[]for i in range(2, N + 1): if a[i]: primes.append(i) for j in range(2 * i, N + 1, i): a[j] = False에라토스테네스의 체로 N 이하 소수를 구해 primes 배열에 저장한다.primes.sort()이후 투 포인터를 사용할 것이므로 primes 배열을 오름차순 정렬해 준다.left, right = 0 # 왼쪽, 오른쪽 인덱스res = 0while.. 2025. 2. 24.
백준 16724: 피리 부는 사나이(python) 문제풀이 지도의 각 칸을 노드로, 성우가 설정한 방향을 간선으로 생각하고 union-find를 사용해 유향 그래프 상 집합을 판별하여 풀이하는 문제다. 각 집합 당 하나의 SAFE ZONE을 배치한 것이 회원들이 지도 어느 구역에 있더라도 SAFE ZONE에 들어갈 수 있는 최소 개수이다.N, M = map(int, input().split())maps = []for _ in range(N): maps.append(list(map(str, input().strip())))입력은 maps 배열에 저장해 주었다. 이후 저장된 UDLR을 간선으로 변환한다.idx = 0graph = [[] for _ in range(N * M)]for i in range(N): for j in range(M): .. 2025. 2. 24.
백준 1266: 다각형의 면적(python) 문제풀이 중학교에서 배우는 사선 공식(신발끈 공식)을 사용하면 간단히 풀이할 수 있다. 정석적인 풀이가 맞는지는 모르겠으나 일단 이렇게 풀었다(...)import sysinput = sys.stdin.readlineN = int(input())vertex = []for _ in range(N): vertex.append(list(map(int, input().split())))vertex.append(vertex[0])res = 0for i in range(N): res += vertex[i][0]*vertex[i+1][1] - vertex[i+1][0]*vertex[i][1]print(abs(res)/2)사선 공식을 그대로 사용해주면 되므로 추가적인 설명은 생략 2025. 1. 8.
백준 1647: 도시 분할 계획(python) 문제풀이 MST를 구하고, MST 중 가중치가 가장 큰 간선을 절단해 마을을 2개로 분리하면 된다.MST를 구하기 위해 Kruskal 알고리즘과 Prim 알고리즘을 사용할 수 있는데, 2가지 방법으로 모두 구현해 보았다.1. Kruskal 알고리즘N, M = map(int, input().split())edges = [] #간선 리스트에 저장for _ in range(M): u, v, w = map(int, input().split()) edges.append((u, v, w))edges 배열에 출발 노드, 도착 노드(무향 그래프지만 편의상 출발-도착으로 지칭), 가중치를 저장한다. Kruskal 알고리즘을 사용하기 위해 이와 같이 저장하였고, 추후 Prim 알고리즘으로 풀이할 때는 연결 리.. 2025. 1. 8.
정규식(Regular Expression) 정규식- 문자들의 특정 패턴을 나타내기 위한 expression- 주로 검색을 목적으로 vi, grep, ex, sed 등에서 사용 정규식의 메타 문자(특수 문자)- 정규식의 행동을 제어하는 특수 문자- . * \ [ ] ^ $. any single character- '.'가 위치한 자리에 어떤 문자든 들어갈 수 있음- a.c는 aac, abc, acc, ... 등과 동일 ** 앞의 문자가 0번 이상 반복- a*c는 ac, aac, aaac, ... 등과 동일 \ Character escape- 메타 문자 의미 상실- '\' 뒤의 문자는 메타 문자로 사용되지 않음- a\.c의 '.'은 메타 문자로서의 '.'이 아닌 일반 문자 '.' ^'^' 뒤에 나오는 문자로 시작하는 문자열- ^x이면 x로 시작하는 .. 2024. 12. 8.

티스토리툴바