시나위

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 전형적인 유니온 파인드 문제인데 recursion 에러로 애를 먹었다. sys.setrecursion으로 해결하려했으나 못했고, 반복문으로 구현해서 통과했다. import sys; input = sys.stdin.readline def find(a, p): if a == p[a]: return a # p[a] = find(a, p) while a != p[..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 전형적인 백트래킹 문제이다. import sys; input = sys.stdin.readline def is_correct(value, r, c): global sudoku, find_list # 1 check row for i in range(9): if value == sudoku[r][i]: return False # 2 check col for i in range(9): if val..

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 ..

1. 계속 교육 한 주 동안 오전 8시부터 시작해서 오후 17시 까지 교육을 열심히 들었다. 교육은 주로 프로그래밍 관련이 아닌 SW 공학에 대한 내용들이었고, CS 지식이 부족했던 나에게 좋은 수업이었다. 광범위한 내용이 아닌 자동차 업계의 내용이긴 하지만 그래도 SW가 안들어가는 곳이 없다보니 얼추 비슷한듯 하다. 다음주부터는 리눅스와 C를 배우는데 기대가 된다. 2. 하루 지나서 작성했는데 주말엔 뭔가 바쁘진 않았다. 아무것도 하기 싫어서 쓰지도 않았나보다

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; ..