히치키치

문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 find-union 문제 Find-Union 알고리즘 초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화 union : 두 원소가 a, b가 속한 집합 합침 find : 원소 a가 주어지면 해당 원소가 속한 집합 반환 트리 구조 사용 : 알고리즘 구현 주어진 원소의 갯수만큼 사용하지 않을 값 (-1) 생성 루트 노드의 인덱스 찾음 루트 노드가 다르면 size/height가 더..

문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 풀이 야구 구현 : one iterator : out count, base1, base2, base3 = 0 3 아웃 전까지 게임 진행 홈으로 들어온 사람 수 = result에 따른 총점 / base 갱신 다음 타자로 순번 넘겨주기 3 아웃 후 최고 점수 갱신 4번 타자 고정, 순열 조합 빡빡한 시간 제한 : 최소한의 함수, 최대 단일 변수 이용 참고 https://rhdtka21.tistory...

문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS : 자식 노드 하나씩 방문 : 주어진 값인지 확인 : que 이용 시간 : 깊이 하나씩 내려갈 때마다 +1 경로 : 이전 노드 (부모 노드) 하나씩 넣기 -> 거꾸로 출력 코드 from collections import deque def path(x): arr = [] temp = x for _ in range(dist_time[x]+1): ar..

문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 BFS 탐색 인접행렬 : 노드 간의 연결 여부 check visited : 각 노드에 count로 방문하기까지 거쳐온 횟수 코드 문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 from collections import deque def bfs(v, visited, adj): count = 0 q = deque([[v, count]]) #노드, 몇 번 거쳐왔는..