시나위

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 최소 거리를 구하고 경로도 같이 구해야하는데 다익스트라 알고리즘에 경로도 같이 추가하면 쉽게 풀린다. # import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(s, e, adj_list): INF = 987654321 ret = None # dist, route ..

https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 도착지까지 최소거리를 찾아야해서 다익스트라 알고리즘을 사용해서 풀수있지만 도착지까지 갈 때 방향 전환까지 카운트해야해서 조금 까다로운 문제이다. 다익스트라 알고리즘에 진행방향과 방향을 전환한 횟수를 같이 추가해서 풀었다. import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(raser,..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 의존성을 확인하기위해 단방향 그래프를 그리고 다익스트라를 사용해서 그래프 탐색을 하면 된다. import sys; input = sys.stdin.readline from heapq import heappush, heappop def dijkstra(start, size, adj_list): ret = [0, 0] h = [(0, start)] visit = [0 for _ in range(size ..

https://programmers.co.kr/learn/courses/30/lessons/42861# 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 프림 알고리즘으로 풀었다. 크루스칼로도 풀어도 될듯 from heapq import heappop, heappush def solution(n, costs): answer = 0 adj_list = [[] for _ in range(n)] for s, e, c in costs: adj_list[s].append((c, e)) adj_list[e].append((c, s)) # prim visit = [0 for _ in range(n)] h = [(0, 0)..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 그래프 탐색 알고리즘중 하나인 floyd-warshall 알고리즘을 사용하는 문제이다. 해당 알고리즘은 dijkstra와 달리 모든점에서 모든점까지의 최소거리를 탐색할때 사용한다. floyd warshall 알고리즘을 간단하게 설명하면 (1) s에서 e까지의 거리를 직접 가는 경우(cost[s][e])와 (2) k 점을 거쳐 가는 경우(cost[s][k] + cost[k][e]) 두 개를 비교하면..

https://www.acmicpc.net/problem/2160 2160번: 그림 비교 N(2 ≤ N ≤ 50)개의 그림이 있다. 각각의 그림은 5×7의 크기이고, 두 가지 색으로 되어 있다. 이때 두 가지의 색을 각각 ‘X’와 ‘.’으로 표현하기로 하자. 이러한 그림들이 주어졌을 때, 가장 비 www.acmicpc.net C/C++을 다시 익히기 위해 푼 쉬운 구현문제이다. c처럼 푼 c++ #include // functions void array_input(int); int find_combination(int); void find_answer(int); int check_diff(int, int); // global variables char pictures[50][5][7]; int combi..

https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 그래프 탐색인데 1차원이라 생소하긴했지만 어려운 문제는 아니다. 단지 이전부터 많이 해왔던 것처럼 visit을 처음부터 잡아놓고 진행하면 메모리 초과가 나온다. 범위가 +-100,000,000이기 때문에 4 * 200,000,000 이므로 약 762MB 쯤 . 따라서 set이나 dictionary 자료구조를 사용해서 visit을 체크하면 된다. import sys; ..

https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net string을 숫자로 변환해서 조건안에 있는것만 체크했다. import sys; input = sys.stdin.readline def stringToMinutes(string): hh, mm = map(int, string.split(":")) return hh * 60 + mm def main(): S, E, Q = map(stringToMinutes, i..

https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 브루트포스로 범위 내 모든 값을 더하는 방식으로 구현했다. # import sys; input = sys.stdin.readline def main(): N = int(input()) num_task = [0 for _ in range(366)] for _ in range(N): s, e = map(int, input().split()) for i in range(s, e + 1): num_task[i] +=..

https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 분할정복으로 되어있는데 규칙성으로 찾았다. (k-1)를 binary로 바꾸고 모든 자리값을 더하면 해당 k번째 자리의 값이 된다. def main(): k = int(input()) - 1 answer = 0 while k: answer += k & 1 k >>= 1 print(answer % 2) if __name__ == "__main__": main()