본문 바로가기

전체 글213

백준 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.
Linux 환경에서의 프로그램 실행 gcc: C 컴파일러$ gcc [options] FILE ...$ gcc file.c //a.out 파일 생성$ gcc -o file file.c //file 파일 생성- FILE은 무조건 C 파일(.c)- FILE을 컴파일한 실행 파일(.out) 생성- 파일명 옵션을 지정하지 않으면 컴파일 결과 a.out의 디폴트 파일명으로 생성* C++ 컴파일러는 g++library 만들기 및 사용$ ar [options] library.a file1.o file2.o file3.o- static library 파일은 (.a)r: include this(replace is exist)c: silently(if not exist)s: maintain table(symbol: file)x: extractt: print .. 2024. 12. 6.
Linux Commands Command vs. Instruction command:shell이 처리하는 cat, ls, cp, bash, vi, gcc 등(단, cd 등 내부 명령어는 bash가 직접 처리)의 독립적인 프로그램(실행 파일) instruction:CPU가 수행하는 add, sub, jump, branch, load, store 등의 기계어more$ more FILE- FILE 파일의 내용을 화면에 출력- 내용이 길 경우 한 화면씩 끊어서 보여준다는 점이 cat과의 차이- pipe("|")를 이용해 다른 프로그램과 동시에 사용되기도 less$ less FILE- 텍스트의 내용을 한 화면씩 끊어서 보여줌(more과 유사)- 앞의 내용으로 돌아갈 수 있음 date: 날짜 및 시간$ date$ date mmddhhmm- .. 2024. 12. 6.

티스토리툴바