알고리즘/문제풀이7 [BOJ][Python] #1012 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제풀이 DFS 알고리즘을 적용하여 풀었다. 1. 입력받은 배추의 위치를 값 1로 설정한다. 2. 그래프를 돌다가 값이 1인 위치가 나오면 상하좌우를 확인한 후, 배추가 심어진 위치면 0으로 바꾼다. 3. 탐색이 완료되면 cnt += 1을 수행한다. 4. 2, 3번의 과정을 반복한 후, 최종적으로 필요한 배추흰지렁이 수(cnt)를 출력한다. >> DFS 알고리즘 적용 풀이 import sys sys.setrecursionlimit(100000) input = sys.stdi.. 2022. 10. 8. [BOJ][Python] #13164 행복 유치원 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 풀이과정 우선, k개의 조를 배정하므로 조를 나누기 위한 경계는 k-1개여야 한다. '조 내에서 가장 키가 큰 원생과 작은 원생의 키 차이만큼 비용이 든다'고 했으므로 원생들 간의 키 차이가 가장 큰 경계값을 기준으로 나눠야 한다. 예제의 경우, 원생들 간 차이값은 1 -2- 3 -2- 5 -1- 6 -4- 10 이므로 4와 2를 기준으로 조를 나눠야 비용이 적게 든다. 정리하자면, 비용을 가장 적게 들게 하기 위해서는 차이가 큰 경계를 기.. 2022. 7. 24. [BOJ][Python] #1543 문서 검색 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이과정 string 비교 문제였다. 이 문제에서 주목할 부분은 'index값을 어디로 옮겨줄 것인가'였다. 같은 부분을 탐색한 뒤에 그 문자열 길이만큼 옮겨주면 된다. >> 코드 doc = input() sch = input() cnt = 0; i = 0 while i 2022. 5. 18. [BOJ][Python] #16953 A → B 16953번: A → B 첫째 줄에 A, B (1 ≤ A > 코드 n, N = inpu.. 2022. 5. 17. [BOJ][Python] #1946 신입사원 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 1. 서류심사 순위로 오름차순 나열한다. 2. 서류심사 순위가 가장 높은 지원자 A의 면접성적 순위보다 낮은 지원자 B는 A보다 순위가 높은 성적이 없으므로 탈락한다. >> A의 면접점수 순위를 max값으로 설정한 후에 다른 지원자의 순위를 순서대로 비교해가며 순위가 더 낮은 지원자의 수(cnt)를 계산한다. cnt의 값이 올라가면서 max값은 합격한 다른 지원자의 면접점수 순위로 바뀌게 된다. >> 코드 import sys n = i.. 2022. 5. 16. 이전 1 2 다음
