코딩테스트 대비/백준(BOJ)
[Python][백준/BOJ] 6118번 : 숨바꼭질
https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2
전체 글
개발..해볼까?
코딩테스트 대비/백준(BOJ)
[Python][백준/BOJ] 5567번 : 결혼식
https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 내 코드 import sys input = sys.stdin.readline n = int(input()) m = int(input()) visited =[0 for _ in range(n+1)] acq =[[]*(n+1) for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) acq[a].append(b) ..
코딩테스트 대비/백준(BOJ)
[Python][백준/BOJ] 11724번 : 연결 요소의 개수
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 내 코드 import sys input = sys.stdin.readline n,m = map(int, input().split()) graph=[[] for _ in range(n+1)] visited = [False]*(n+1) for _ in range(m): u, v = map(int, input().split()) graph..
코딩테스트 대비/백준(BOJ)
[Python][백준/BOJ] 20920번 : 영단어 암기는 괴로워
https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 내 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) memory = {} for _ in range(n): word = input().rstrip() if len(word) < m :#길이 체크 continue else: if word in mem..
코딩테스트 대비/백준(BOJ)
[Python][백준/BOJ] 19941번 : 햄버거 분배
https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 내 코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) s = list(input().rstrip()) cnt =0 for i in range(n): if s[i] == 'P': for j in range(i-k, i+k+1): if -1 < j < n and s[j] == 'H': s[j] = '0' cnt +=1..
코딩테스트 대비/백준(BOJ)
[Python][백준/BOJ] 19637번 : IF문 좀 대신 써줘
https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 내 코드 시간 초과된 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) lv ={} for _ in range(n): a, b = input().split() lv[a] = int(b) lv = sorted(lv, key = lambda x : x[1]) for i in r..
코딩테스트 대비/백준(BOJ)
[Python][백준/BOJ] 5014번 : 스타트링크
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 내 코드 import sys input = sys.stdin.readline from collections import deque total,now,dst,u,d= map(int, input().split()) visited = [False for _ in range(total+1)] cnt = [0 for _ in range(total+1)] def bfs(s): q = deque() q.append(s) ..
코딩테스트 대비/알고리즘
플로이드 워셜 알고리즘(Floyd Warshall)
플로이드 워셜 알고리즘 다이나믹 프로그래밍에 의거하는 알고리즘이다. 모든 노드 간의 최단거리를 구하는 것이 목적이므로, 2차원 인접 행렬을 구성한다. 다익스트라 알고리즘과 차이 다익스트라 알고리즘 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 1차원 리스트 기반의 최단 거리 테이블 사용 플로이드 워셜 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘(거쳐가는 정점을 기준으로 최단 거리를 구함) 2차원 리스트 기반의 테이블 사용 그래프의 간선들 중 음의 가중치가 존재해도 실행할 수 있음 주요 코드 inf = int(1e9) #무한을 의미하는 값, 보통 10억으로 초기화함 graph = [[inf]*(n+1) for _ in range(n+1)] #n은 노드..