note

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 일반적인 크루스칼 알고리즘으로 풀면 된다. 1. 간선 -> 비용 기준 오름차순 정렬 2. 사이클이 발생하지 않으면(= parent가 같지 않으면) union 한번 에러났었는데,,, 어이없게도 cost 기준으로 정렬한다는 생각에 사로잡혀서 간선에 대한 정보 a, b, c를 입력 받을 때 c, a, b로 입력받음,,ㅎ 실수하지 말자 import sys s..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 입력받는 요소가 사람이름이기 때문에 숫자로 관리하기 위해 딕셔너리(people)를 선언하고 1. a, b 입력받아서 2. 딕셔너리에 존재하지 않으면 추가, parent 추가 3. union 그 후 연결되어 있는 요소들의 개수를 출력하기 위해 원래 count 함수를 썼는데 제대로 못 잡아내길래 for문을 썼다 ㅎㅎ시간초과 import sys sys.setrecursionlimit(1000..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제의 해결법은 쉽게 생각해낼 수 있었다. 입력된 여행 계획의 도시들이 서로 연결되어 있는지만 확인하면 된다. 도시들의 연결 정보를 입력받을 때 1이면 union해준다. 계획을 입력받은 후 시간을 줄이기 위해 리스트에서 중복 원소를 제거해주고 find를 통해 모두 같은 부모를 가지고 있는지(= 하나의 집합인지) 확인해주면 된다. def find_parent(parent, x): if parent[..

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 이코테에서 풀었던 문제 그대로 나왔다. https://sssbin.tistory.com/193 그래서 알고리즘 다시 정리한다는 마음으로 내 손으로 직접 풀었지만 ,, 시간 초과로 실패 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return ..

다양한 그래프 알고리즘 - 그래프: 노드 + 간선 ㄴ '서로 다른 개체(혹은 객체)가 연결되어 있다' ㄴ 인접행렬(2차원 배열) - 메모리↑, 시간↓ / 인접리스트(리스트) - 메모리↓, 시간↑ - 그래프 vs 트리 그래프 트리 방향성 방향 그래프 / 무방향 그래프 방향 그래프 순환성 순환 / 비순환 비순환 루트 노드 존재 여부 X O 노드간 관계성 X 부모-자식 관계 모델의 종류 네트워크 모델 계층 모델 서로소 집합 - 서로소 집합: 공통 원소가 없는 두 집합 - 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 ㄴ union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 ㄴ find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 # ..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음엔 예제를 봐도 문제가 이해가 잘 안 갔었다. 그래서 관련 글들을 찾아보다가,, 벨만-포드 알고리즘이라는 것을 알았다. 이 문제는 음수 간선이 존재하기 때문에 사이클을 순환할수록 가중치가 감소하는 경우가 발생한다. 따라서 일반적인 다익스트라 알고리즘으로 풀 수 없고, 벨만-포드 알고리즘으로 풀어야 한다. 예제2를 보면 사이클을 계속 ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 반드시 통과해야만 하는 정점이 있기 때문에 1 -> v1 -> v2 -> n 1 -> v2 -> v1 -> n 다익스트라를 세번(1번 출발, v1 출발, v2 출발) 돌려서 두 값 중에 최소값을 찾아주면 된다 처음에 실패해서 찾아보니까 값을 세번 더하기 때문에 무한값을 줄여주면 된다고 해서 줄였는데 (1e9 -> 1e8) 여전히 틀림,,,, 자세히 보니..

https://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 heapq import sys input = sys.stdin.readline INF = int(1e9) v, e = map(int, input().split()) k = int(input()) graph = [[] for i in range(v+1)] distance = [INF] * (v+1) for _ in range(e): x, y, w =..

https://sssbin.tistory.com/188 설정 에 있다. S3 버킷에 사진을 업로드하고 carRecog/request 토픽에 message를 publish 2. index.js (람다코드) var AWS = require('aws-sdk'); var iotdata = new AWS.IotData({ endpoint: '엔드포인트', }); var client = new AWS.Rekognition(); var bucket = '버킷 이름'; exports.handler = async function (event) { var photo_target = event.image + '.jpg'; const params = { Image: { S3Object: { Bucket: bucket, Nam..

https://sssbin.tistory.com/187 AWS 기반 주차 관리 시스템 (1) AWS IoT Core mqtt를 이용하여 간단한 AWS 기반 주차 관리 시스템을 만들어보고자 한다. camera.js -> 번호판 이미지를 S3에 업로드하고 request 토픽에 publish 하고 이때 람다함수가 호출되어 rekognition 진행 후 detect 토 sssbin.tistory.com 1. IAM 계정에서 역할 만들기 2. 람다 함수 만들기 3. AWS IoT > 메시지 라우팅 > 규칙 > 규칙 생성 4. 람다함수에 트리거 추가 camera.js -> carRecog/request 토픽에 publish 하면 람다에서 이 메시지를 읽기 위해 규칙 쿼리를 SELECT * FROM 'carRecog..