[파이썬] 백준 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

인텔리제이(Intelij) 한글 깨짐 인코딩 에러 해결 방법

인텔리제이(Intelij) 한글 깨짐 인코딩 에러 해결 방법 구글에서 수십 개의 글을 참고하면서 겨우 겨우 해결한 방법을 정리합니다. 1 : 인텔리제이를 기본 경로로 설치했다면 C:\Program Files\JetBrains\IntelliJ IDEA 2019.1.3\bin\ 을 열어봅니다. 경로를 못찼겠다면 바로가기 파일에 오른쪽 마우스 클릭 - 속성 - 파일 위치 열기를 선택합니다. 64비트 OS라면 idea64.exe.vmoptions를, 32비트라면 idea.exe.vmoptions를 메모장 파일로 열어줍니다. 맨 밑에 -Dfile.encoding=UTF-8을 입력해주고 저장합니다. 인텔리제이를 재시작해서 잘 되는지 확인해봅니다. 2 : 안되는데요? 설정으로 들어갑니다. 에디터 - 코딩 스타일 - ..

• format_list_bulleted 문제 해결
• · 2022. 4. 2.
• 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