본문 바로가기
728x90
반응형

알고리즘109

[백준] 11724번: 연결 요소의 개수 - python https://www.acmicpc.net/problem/11724 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 그래프 문제를 많이 풀어본적이 없어서 구현을 어떻게 해야할지 애를 많이 썻던 문제 아이디어 간선의 개수를 gragh 리스트에 전부 저장을 해준 뒤 방문 유무를 체크하면서 BFS로 색칠을 해준다. 그 후 cnt값을 계속 증가시키면서 최종 cnt를 출력하는 방식으로 구현하였다. from collections import deque imp.. 2024. 4. 5.
[백준] 5347번: LCM - python https://www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 간단한 최소공배수 문제 간만에 최소공배수를 어떻게 구해야했는지 상기시킬 수 있었던 문제였다. 아이디어는 a * b 를 한 다음에 빼나가면서 작은게 0이면 그 나머지 값으로 나누는 아이디어다. n = int(input()) for i in range(n): a, b =map(int,input().split()) tmp = 0 s = a * b while b: tmp = b b = a % b a = tmp print(s // .. 2024. 4. 4.
[백준] 2630번: 색종이 만들기 - python https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 처음에 작성한 무지성 4로 나눠 재귀하기 코드이다. 너무 비효율적이고 틀렷다고 떠서 다시 로직을 작성하였다. n = int(input()) arr = [] blue = 0 white = 0 def paper(n, x_start, x_end, y_start, y_end): global blue global white x_mid = (x_start + x_end) //2 y.. 2024. 4. 4.
[백준] 18870번: 좌표압축 - python https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 사실 처음 보고 O(n^m) 제곱으로 순간 하면 편하겠다.. 라고 생각했지만 알고리즘을 공부하는 사람으로 그짓은 이제 못하겠다. 무조건 해시맵이나 집합 자료형을 쓰는 거라고 생각했고, 코드를 작성했다. 처음에 입력받고, 입력받은 것을 토대로 set자료형으로 받고 정렬을 위해 리스트로 반환한다. 그 다음 dic로 인덱스와 값을 순서대로 저장한다. .. 2024. 4. 4.
728x90
반응형

티스토리툴바