728x90 반응형 Python3173 2022.02.14 [백준] (python 파이썬) 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 이 문제를 보고 처음 아래와 같이 코드를 작성했을 때, 각 시간을 arr에 입력 받고 시작시간으로 오름차순 정렬하고 시간이 같을 시, 종료시간을 오름차순으로 정렬했다. 그리고 이중 for문을 돌려 각 인덱스별로 시작했을 때의 최대 회의 수를 count배열에 넣고 max함수를 이용해 최대값을 출력했다. 그러나 시간초과가 발생했다....O(N^2)이라서 그런거같다....그래서 시간복잡도를 어떻게 줄일까 하면서 생각해보았다. 그러다 모든 회의에 대한 최대값을 구할 필요가 없다고 생각이 들었다. 왜냐하면 arr배열.. 2022. 2. 14. 2022.02.14 [백준] (python 파이썬) 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 총 3가지 경우를 먼저 생각해 볼 수 있다. 1. 현재 꽂아야 할 용품이 멀티탭에 꽂혀 있는 경우 2. 멀티탭에 빈자리가 있을 경우 3. 멀티탭이 꽉 차있을 경우 이중 3번째의 경우 다시 2가지로 나누어 생각해 볼 수 있다. 3.1 멀티탭에 꽂혀있는 용품 중, 앞으로 꽂아야 할 용품 리스트에 없는 경우 3.2 만약 멀티탭에 꽂혀있는 용품들이 앞으로 모두 다시 꽂아야 할 경우 이렇게 보면 총 .. 2022. 2. 14. 2022.02.14 [백준] (python 파이썬) DNA https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 처음 이 문제를 이해하기가 어려웠다. 그래서 구글링 중, 위 그림을 발견하였다. 위의 그림처럼 같은 위치에 있는 DNA중 가장 많이 나온 DNA와 그 DNA를 제외하고 나온 DNA의 갯수를 모두 더해주면 답을 구할 수 있다. 이 문제는 각 상황에서의 최선을 찾는 문제이기 때문에 그리디 알고리즘을 사용할 수 있다. 1 2 3 4 5 6 7 8 9 1.. 2022. 2. 14. 2022.02.14 [백준] (python 파이썬) DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 이 문제는 dfs와 bfs를 모두 사용하여 답을 구하는 문제이다. 먼저 각 정점과 연결된 정점들을 graph에 저장한다. 문제에서 연결된 정점들이 많으면 번호가 작은거 부터 방문하라고 했으니 각각의 graph를 sort로 정렬해 준다. dfs함수를 먼저 실행시켜주고 bfs함수를 실행하기 전, vis배열을 초기화 시켜준다.(dfs함수를 실행하면서 이미 사용.. 2022. 2. 14. 이전 1 ··· 31 32 33 34 35 36 37 ··· 44 다음 728x90 반응형
