본문 바로가기

백준10

[백준] 4195번, 친구 네트워크 | (python,파이썬) 문제 링크 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 문제해결하기 기존 유니온파인드 문제와는 조금 특이하게 노드의 이름를 숫자가 아닌 문자열로 저장해야한다. 다행히 파이썬에는 사전 기능이있다 👍 복잡한 이름의 대한 정보를 저장할때는 사전을 사용하는 것이 최고인것 같다. 조상노드의 정보를 저장하는 parent, 친구 네트워크에 있는 친구 수를 저장하는 friend 총 2개의 사전을 만들었다. '친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.' 이는 곧 같은 집합 안에 있어야.. 2021. 8. 4.
[백준] 9184번, 신나는 함수 실행 | (python,파이썬) 문제 링크 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 ○ 동적계획법 ? → 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음 저장하여, 저장해둔 것을 활용하여 시간소요를 줄이고, 상위문제를 푸는 방법 조금 더 자세히 알아보기 ☞ 6. Dynamic Programming(동적 계획법) ㅣ최대 구간 합 계산 Dynamic Programming (동적 계획법) ? Divide＆conquer(분할정복)와 유사하게, 문제를 여러 작은 문제로 나누어 재귀적으로 해결하.. 2021. 8. 4.
[백준] 1003번, 피보나치 함수 | (python,파이썬) 문제 링크 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 ○ 동적계획법 ? → 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것. 조금 더 자세히 알아보기 ☞ 6. Dynamic Programming(동적 계획법) ㅣ최대 구간 합 계산 Dynamic Programming (동적 계획법) ? Divide＆conquer(분할정복)와 유사하게, 문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법이다. 차이점은 큰 문제의 해답이 작은 문제의 해답들의 식으로 corin-jaesung.tistory.com 문제해.. 2021. 8. 3.
[백준] 1976번, 여행 가자 | (python,파이썬) 문제 링크 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 문제해결하기 문제가 굉장히 복잡해보이지만, 유니온 파인드 개념을 잘 활용하면 쉽게 풀 수 있는 문제이다. 예를들면, 2가지 길만 있다고 생각해보자 1. 종로 ↔ 광화문 ↔ 홍대 2. 건대 ↔ 안양 ↔ 홍대 건대에서 광화문을 가려면 ? 건대 → 안양 → 홍대 → 광화문 안양에서 종로를 가려면 ? 안양 → 홍대 → 광화문 → 종로 이는 '홍대'라는 접점이 있기 때문에 가능한 일이다. 이를 조상으로 설정하면 된다. 정답코드 import sys sys... 2021. 7. 28.

티스토리툴바