[파이썬] 백준 11724 : 연결 요소의 개수

[파이썬] 백준 11724 : 연결 요소의 개수 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 실버 2 그래프, BFS, DFS 접근 방향없는 그래프이므로 간선의 양 끝점을 서로 연결되도록 만든다. bfs탐색을 하다가 큐의 값이 텅텅 비게되면 탐색이 끝나므로 그때 카운트를 해주는 방법으로 연결 요소의 개수를 셈할 수 있다. 코드(BFS) import sys; input = sys.stdin...

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 6.
• textsms

[파이썬] 백준 5525 : IOIOI

[파이썬] 백준 5525 : IOIOI 5525번: IOIOI (acmicpc.net) 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 실버 2 문자열 접근 n이 1 : IOI n이 2 : IOIOI n이 3 : IOIOIOI 먼저 반복문을 돌리면서 I가 위치한 인덱스 값을 새로운 리스트에 append한다. 리스트의 i번째 값과 i-1번째 값의 차가 2라면 IOI와 같은 경우이므로 카운터 변수를 하나 증가시키는 방법으로 IOI를 탐색할 수 있..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 4.
• textsms

[파이썬] 백준 18870 : 좌표 압축

[파이썬] 백준 18870 : 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 실버 2 정렬 접근 입력받은 값을 오름차순 정렬하여 또 다른 리스트에 값을 저장한다면 다음과 같이 될 것이다. nums = [2, 4, -10, 4, -9] new_nums = [-10, -9, 2, 4, 4] new_nums에서 가장 작은 값을 기준으로 0부터 값을 부여하면 new_nums = [0, 1,..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 3.
• textsms

[파이썬] 백준 1780 : 종이의 개수

[파이썬] 백준 1780 : 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 실버 2 분할정복, 재귀 접근 이 문제를 풀기전에 백준의 색종이 만들기 문제를 먼저 풀어보는 것이 좋다. https://afterdawncoding.tistory.com/145 [파이썬] 백준 2630 : 색종이 만들기 [파이썬] 백준 2630 : 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 3.
• textsms

[파이썬] 백준 9020 : 골드바흐의 추측

[파이썬] 백준 9020 : 골드바흐의 추측 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 실버 1 정수론, 소수 판정 접근 먼저 아리토스테네스의 체를 이용해 소수를 판정한다. 제곱근보다 작은 수 범위에서 합성수를 걸러내면 빠르게 소수를구할 수 있다. 소수중에서 x2를 한 값이 입력한 값을 넘는 경우부터 구한 소수를 역순으로 탐색하면서 두 소수의 합이 입력한 값과 같은 경우일 때를 출력하도록 했다. 다만 이 방법은 입력한 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 1.
• textsms

[파이썬] 백준 4948 : 베르트랑 공준

[파이썬] 백준 4948 : 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 실버 2 정수론, 소수 판별 접근 에라토스테네스의 체로 소수를 판별하는 방법을 사용하면 간단하게 구할 수 있다. 다만 내가 작성한 방법은 pypy3에서만 통과되었다. 코드 import sys; input = sys.stdin.readline def isPrime(num): for i in range(2, int(num**0.5) + 1): if n..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 30.
• textsms