문제 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 문제 풀이 다익스트라 알고리즘을 이용하여 각 노드의 최단 거리를 구해주면 된다. 코드 import collections import heapq V,E = map(int,input().split()) K = int(input()) # 그래프 생성 graph = collections.defaultdict(list) for _ in range(E): u,v,w = map(int,inp..

문제 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 문제풀이 답이 여러개 이기때문에 위상정렬을 해주는 것 말고는 딱히 어려운 부분이 없다 코드 from collections import deque import collections v, e = map(int,input().split()) #진입차수 처리할 리스트 indegree = [0] *(v+1) #그래프 생성 graph = collections.defaultdict(li..

문제 www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 그리디 알고리즘 문제로 +연산을 먼저처리하고 - 연산을 처리해주면 된다. 1. 숫자와 문자 를 분리하여 저장. 2. 문자중 +먼저 처리 3. +처리 후 -처리 코드 s =input() nums = [] num = '' # 숫자 문자 분리 for char in s: if char.isdigit(): num+=char else: nums.append(int(num)) num = '' nums...

문제 www.acmicpc.net/problem/5637 5637번: 가장 긴 단어 단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만 이루어져 있다. 단어와 다른 문자(마침표, 숫자, 심볼, 등등등...)로 이루어진 글이 주어졌을 때, 가장 긴 단어를 구하는 프로그램을 작성하시오. Apple의 www.acmicpc.net 문제풀이 정규표현식을 이용하여 알파벳과 '-' 을 제외한 문자를 제거하고 단어들을 길이에 따라 정렬해준다. 마지막단어가 'E-N-D'가 될때까지 반복. 코드 import re words = [] while True: words.extend(input().split()) if words[-1] =='E-N-D' : break words = [re.sub('[^a-z-]','',x.low..

문제 www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 문제풀이 N이 1이 될때까지, 주어진 맵을 4등분하고, 현재 숫자가 몇사분면에 있는지 확인하며 N을 줄여나간다. 코드 N,r,c = list(map(int,input().split())) result = 0 while N>=1 : temp = 2**(N-1) - 1 # 2사분면 if r

문제 www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 문제풀이 순서대로 전위순회 -> 중위 순회 -> 후위 순회를 출력하면된다. 코드 class Node: def __init__(self,data,left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node # 전위 순회 def pre_order(node): print(node.data, en..