티스토리

bright

검색하기

블로그 홈

bright

bright-code.tistory.com/m

알고리즘 자격증 2021 취업 목표 !!

구독자: 0

방명록 방문하기

주요 글 목록

# 1697 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net from collections import deque n, k = map(int,input().split()) t = [0]*100001 def bfs(): q = deque() q.append(n) while q: a = q.popleft() if a == k : print( t[k]) return for b in ( a-1, a+1, a*2): if 0 이동 가능한 칸으로 이동 -.. 공감수 0 댓글수 0 2021. 4. 10.
# 1715 카드 정렬하기 www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net import heapq import sys input = sys.stdin.readline n = int(input()) data = [] for i in range(n) : data.append(int(input())) heapq.heapify(data) result = 0 while data: first = heapq.heappop(data) if len(data) 공감수 0 댓글수 0 2021. 4. 10.
# 1238 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import heapq import sys input = sys.stdin.readline n, m, x = map(int,input().split()) # n 명, 도로 m 개 , x 마을에서 graph= [ [] for i in range(n+1)] for i in range(m): a,b,c = map(int,input().split()) graph[a].append((b,c.. 공감수 0 댓글수 0 2021. 4. 10.
# 18352 특정 거리의 도시 찾기 www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net import heapq import sys input = sys.stdin.readline n, m, k, x = map(int,input().split()) # 도시 도로 거리 출발 도시 graph = [ [] for _ in range(n+1) ] for i in range(m): a, b= map(int, input().split().. 공감수 0 댓글수 0 2021. 4. 10.
# 1504 특정한 최단 경로 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import heapq import sys input = sys.stdin.readline n, e = map(int,input().split()) # 정점, 간선 graph=[ [] for _ in range(n+1) ] for i in range(e): a,b,c = map(int,input().split()) graph[a].append((b,c)) graph[.. 공감수 0 댓글수 0 2021. 4. 10.
# 1916 최소비용 구하기 파이썬 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import heapq import sys input = sys.stdin.readline n = int(input()) # 도시 m = int(input()) # 버스 graph = [ [] for _ in range(n+1)] for i in range(m): s,e,c = map(int,input().split()) graph[s].append((e,c)) # 도착, 비용.. 공감수 0 댓글수 0 2021. 4. 9.
# 1753 최단 경로 파이썬 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 sys import heapq input = sys.stdin.readline V,e = map(int,input().split()) # 정점, 간선 k = int(input()) # 시작 graph = [ [] for _ in range(V+1)] for i in range(e): u,v,w = map(int,input().split()) graph[u].append( .. 공감수 0 댓글수 0 2021. 4. 9.
# 10942 팰린드롬? 파이썬 www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net # 시간 초과 from collections import deque n = int(input()) data = list(map(int,input().split())) m = int(input()) result = [1]*m for i in range(m): s,e = map(int,input().split()) if e-s 1 : if d.pop() != d.popleft() : result[i] = 0 for i in range(m): print(.. 공감수 0 댓글수 0 2021. 4. 9.
# 10211 Maximum Subarray 파이썬 www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net t = int(input()) def max_sub(): n = int(input()) data = list(map(int,input().split())) for i in range(1,len(data)): data[i] += data[i-1] if data[i-1]>0 else 0 return max(data) p = [] for i in range(t).. 공감수 0 댓글수 0 2021. 4. 9.
# 1890 점프 파이썬 www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net import sys n = int(input()) graph = [list(map(int, input().split())) for i in range(n)] d = [ [0]*n for _ in range(n) ] d[0][0] = 1 for i in range(n): for j in range(n): if i == j == n-1 : break a = graph[i][j] if i+ a < n : .. 공감수 0 댓글수 0 2021. 4. 8.
#1743 음식물 피하기 파이썬 www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net from collections import deque n, m , k = map(int,input().split()) # 세로 가로 음식물 수 graph = [ [0]*m for i in range(n)] for i in range(k): a,b = map(int,input().split()) graph[a-1][b-1] = 1 dx = [-1,1,0,0] dy = .. 공감수 0 댓글수 0 2021. 4. 8.
# 9465 스티커 파이썬 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net def sticker(n,data): data[0][1] += data[1][0] data[1][1] += data[0][0] for j in range(2,n): data[0][j] += max( data[1][j-2], data[1][j-1] ) data[1][j] += max ( data[0][j-2], data[0][j-1] ) return max(data[0][n-1], data[1][n-1.. 공감수 0 댓글수 0 2021. 3. 11.
# 11725 트리의 부모 찾기 파이썬 # 11725 from collections import deque n = int(input()) # 노드의 수 tree = [ [] for _ in range(n+1) ] for i in range(n-1): a, b = map(int,input().split()) tree[a].append(b) tree[b].append(a) def bfs(): q = deque() q.append(1) visited = [0] * (n+1) visited[1] = 1 while q : x = q.popleft() for i in tree[x]: if visited[i] == False: visited[i] = x q.append(i) return visited result = bfs() for i in range(.. 공감수 0 댓글수 0 2021. 3. 11.
# 2644 촌수계산 1. 시간 초과 코드 # 2644 n = int(input()) # 전체 사람의 수 a, b = map(int,input().split()) m = int(input()) # 관계의 수 graph = [ [] for _ in range(n+1) ] for i in range(m): p, c = map(int,input().split()) graph[p].append(c) def bfs(x, y): p ,cnt = 0, 1 while 1: for i in range(1,n+1): if x in graph[i]: p = i break if p == 0 : return -1 else : cnt += 1 if y in graph[p] : return cnt else : x = p print( bfs(a,b) ).. 공감수 0 댓글수 0 2021. 3. 11.
# 2217 로프 acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net # 2217 n = int(input()) # 로프의 수 data = [] for i in range(n): data.append(int(input())) data.sort(reverse=True) max_w = [] for i in range(n): max_w.append( data[i]*(i+1)) print(max(max_w)) 너무 어렵게 생각하지 않는 것이 중요하다. 기본적으로 입력받은 중량 값을 역.. 공감수 0 댓글수 0 2021. 3. 8.
#13305 주유소 파이썬 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net # 13305 n = int(input()) # 도시의 수 dist = list(map(int, input().split() )) cost = list(map(int, input().split() )) # 처음 출발할 때, 무조건 기름 필요 total = cost[0]*dist[0] m = cost[0] # 나보다 작은 값이 나오면 그 이후로 그 값으로 계산 # 마지막 나라의 가격은 사실상 사용되.. 공감수 0 댓글수 0 2021. 3. 8.
# 4796 캠핑 www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net # 4796 data = [] while True : L, p, v = map(int, input().split() ) if L + p + v == 0 : break else : data.append([L,p,v]) for i in data : L, p, v = i[0], i[1], i[2] cnt = ( v//p )*L re = v - p*(v//p) if re 공감수 0 댓글수 0 2021. 3. 8.
# 1476번 : 날짜 # (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) year = list(map(int,input().split())) for result in range(1,7981): if result % 15 == year[0] or ( result%15 == 0 and year[0] == 15 ) : if result % 28 == year[1] or (result%28 == 0 and year[1] == 28 ) : if result % 19 == year[2] or ( result%19 == 0 and year[2] == 19) : print(result) 문제에 보면 주어진 시간이 2초로 긴 편이다. 완전 탐색으로 접근해서 풀어도 무방하다. 주의! 15/28/19 로 나누어 떨어지면 나머지.. 공감수 0 댓글수 0 2020. 10. 15.
# 2309번 : 일곱 난쟁이 # 난쟁이 키 합이 100 from itertools import combinations height = [] for i in range(9): height.append(int(input())) height.sort() combi = list(combinations(height,7)) for i in combi : h_sum = 0 for k in range(7): h_sum += i[k] if h_sum == 100 : result = i break for k in range(7): print(result[k]) 조합 ( combination ) 모듈을 통해 완전 탐색으로 풀이한다. 조합의 결과는 튜플로 나옴에 유의한다. from itertools import combinations combi = li.. 공감수 0 댓글수 0 2020. 10. 15.
# 1439번: 뒤집기 S = input() count = 1 for i in range(len(S)-1): if S[i] != S[i+1]: count += 1 print( count//2 ) 바뀌는 것을 세면, 실제 바뀐 것은 1번 인데 앞, 뒤로 카운트 되기 때문에 마지막에 2로 나누어 준다. 처음 시작 할 때 바뀌는 것은 1 번만 카운트 되므로 count = 1 부터 시작한다. 공감수 0 댓글수 0 2020. 10. 15.
# 2583번: 영역 구하기 import sys sys.setrecursionlimit(10000000) m, n, k = map(int, input().split()) # 세로 가로 직사각형 수 # 직사각형으로 채워지면 1, 안 채워지면 0 graph = [ [0]*n for _ in range(m) ] for i in range(k): s1, e1, s2, e2 = map(int,sys.stdin.readline().split()) for x in range(s1,s2): for y in range(e1, e2): graph[y][x] = 1 def dfs ( x, y, cnt ): graph[y][x] = 1 cnt += 1 move_x = [-1,1,0,0] # 가로 -> n move_y = [0,0,-1,1] # 세로 ->.. 공감수 0 댓글수 0 2020. 10. 12.
# 2468번: 안전 영역 import copy import sys sys.setrecursionlimit(10000000) n = int(input()) graph = [] max_h = 0 for i in range(n): graph.append(list(map(int,sys.stdin.readline().split()))) max_h = max( max_h, max(graph[i])) save = [0] * ( max_h +1 ) save[0] = 1 # 비가 안오면 전 영역( 1개 ) 이 안전하다. def dfs ( x,y,h, tmp_graph): move_x = [-1,1,0,0] # 가로 move_y = [0,0,-1,1] # 세로 tmp_graph[x][y] = 0 for i in range(4): nx = x + .. 공감수 0 댓글수 0 2020. 10. 12.
# 4963번: 섬의 개수 import sys sys.setrecursionlimit(10000000) def island(w,h): graph = [] for i in range(h): graph.append( list(map(int,sys.stdin.readline().split()))) move_x = [ -1, 1, 0, 0, -1,-1,1,1 ] # x는 세로, 순서대로 가로 세로 대각선 move_y = [ 0, 0, -1, 1, -1,1,-1,1 ] # y는 가로 def dfs ( x,y ) : graph[x][y] = 0 for i in range(8): nx = x + move_x[i] ny = y + move_y[i] if nx=w : continue if graph[nx][ny] : dfs( nx, ny ) co.. 공감수 0 댓글수 0 2020. 10. 12.
# 11724번: 연결 요소의 개수 import sys sys.setrecursionlimit(10000000) n, m = map(int,sys.stdin.readline().split()) graph = [ [] for i in range(n+1) ] for i in range(m): start, end = map(int,sys.stdin.readline().split()) graph[start].append(end) graph[end].append(start) visited = [False] * (n+1) def dfs ( graph, v,visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs( graph, i, visited) cnt = 0 for i in ran.. 공감수 0 댓글수 0 2020. 10. 12.
# 1260번: DFS와 BFS DFS def dfs( v, visited_dfs ): if not visited_dfs[v-1] : visited_dfs[v-1] = True print(v, end=' ') if v in graph.keys(): for i in graph[v]: dfs( i, visited_dfs ) 1. 시작 노드를 stack 에 넣고 방문 처리 2. stack의 최 상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 stack 에 넣고 방문 처리 -> 최 상단 노드 중 방문하지 않은 인접 노드가 없으면 최상단 노드 pop 3. 반복 BFS def bfs( v, visited_bfs ) : queue = deque() queue.append(v) while queue : now = queue.poplef.. 공감수 0 댓글수 0 2020. 10. 11.
깊이/너비 우선 탐색(DFS/BFS)-여행경로* def solution(tickets): routes = dict() for t1, t2 in tickets: if t1 in routes: routes[t1].append(t2) else: routes[t1] = [t2] for r in routes.keys(): routes[r].sort(reverse=True) st = ['ICN'] ans = [] while st: top = st[-1] if top not in routes or len(routes[top])==0: ans.append(st.pop()) else: st.append(routes[top].pop()) ans.reverse() return ans ... 아직 dfs-bfs 가 익숙하지 않다. 엄청 어렵다. step 1 ) 갈 수 있는.. 공감수 0 댓글수 0 2020. 10. 11.
# 1924: 2007년 x, y = map(int,input().split()) # 월 일 month = [0,31,28,31,30,31,30,31,31,30,31,30,31] day = [ 'SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT' ] today = 0 for i in range(1,x): today += month[i] today += y print ( day[today%7] ) 공감수 0 댓글수 0 2020. 10. 7.
# 1157: 단어 공부 n = input() n = n.upper() cnt = [0] * 28 for i in n : cnt [ ord(i)-65 ] += 1 tmp = sorted(cnt) if tmp[-1] != tmp[-2]: print( chr( cnt.index(tmp[-1]) +65 )) else: print("?") www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 공감수 0 댓글수 0 2020. 10. 7.
# 18406: 럭키 스트레이트 n = list(map(int,input())) left, right = 0, 0 for i in range( len(n)//2 ): left += n[i] right += n[ len(n)-i-1 ] if left == right : print("LUCKY") else: print("READY") 공감수 0 댓글수 0 2020. 10. 7.
# 2805: 나무 자르기 # 시간초과 n, m = map(int,input().split()) # 나무의 수, 필요한 길이 trees = list(map(int,input().split())) h = max(trees) for i in range(h,0,-1): total = 0 for j in trees: if i = m : print(i) break 문제에서 나무의 최대값 이 매우 크게 잡혀 있는 것을 볼 수 있다. 이렇게 그냥 풀면 당연히 시간초과가 나온다. # 정답 n, m = map(int,input().split()) # 나무의 수, 필요한 길이 trees = list(map(int, input().split())) start, end = 1, max(trees) w.. 공감수 0 댓글수 0 2020. 10. 5.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.