ABC 293 복기 - D Tying Rope - 그래프 연결요소, cycle 판단 -

1. 연결요소 연결 요소(Connected Component) (velog.io) 연결 요소(Connected Component) 그래프 중에서는 위 그림과 같이 여러 개로 나누어져 있을 수도 있다. 위 그림을 보고 두 개의 그래프라고 볼 수도 있지만, 하나의 그래프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 그 이유 velog.io 위 그래프가 2개의 그래프로 볼 수도 있지만, 1개의 그래프가 2개의 연결요소를 가진다고 볼 수 있다. 연결요소(connected component)는 해당 요소에 속하는 모든 정점을 연결하는 경로가 있어야하고 또 다른 연결요소에 속한 정점과 연결하는 경로가 없어야한다. 2. 문제 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수..

• format_list_bulleted 경쟁 프로그래밍/Atcoder
• · 2023. 3. 12.
• textsms

정수론 - 방정식을 만족하는 순서쌍의 수 세기 - 브루트포스 탐색 범위 줄이는 테크닉 익히기

1. 문제 C - Four Variables (atcoder.jp) C - Four Variables AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이1 당연히 안될 것 같지만 방법을 모르겠다면 브루트포스로 접근하는게 기본이다 AB+CD = N을 만족하는 양의 정수쌍 A,B,C,D를 찾기 위해 1부터 N까지 순회해본다 이 값을 AB = x라 하고, 그렇다면 CD는 자동으로 N-x로 결정된다 그리고 AB = x에서 1부터 x까지 순회해서 그 수를 A라 하고, 만약 x가 A로 나누어 떨어진다면 B를 찾은 것이다. 마..

• format_list_bulleted 경쟁 프로그래밍/Atcoder
• · 2023. 3. 11.
• textsms