목록알고리즘 스터디 (37)

히치키치

[백준] 2096번 : 내려가기 - Python(파이썬)

문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 요점 dp 배열 슬라이딩 윈도우 까다로운 메모리 점화식 원리 코드 #문제 : https://www.acmicpc.net/problem/2096 n=int(input()) table=[list(map(int,input().split()))for _ in range(n)] large=small=table[0] for i in range(1,n): large=[max(large[0],large[1])+table..
알고리즘 스터디 2021. 7. 6. 13:07
[백준] 1976번 : 여행 가자 - Python(파이썬)

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

문제 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...
알고리즘 스터디 2021. 5. 25. 16:47
[백준] 13913번 : 숨바꼭질4 - Python(파이썬)

문제 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..
알고리즘 스터디 2021. 5. 25. 16:40
Prev 1 2 3 4 5 6 7 8 ··· 10 Next