전체 글361 [BOJ]1327번: 소트 게임 문제: https://www.acmicpc.net/problem/1327 브루트 포스(완전 탐색)을 통해 해결할 수 있습니다. 브루트 포스 방법은 BFS를 사용하였습니다. 큐에서 하나씩 숫자를 뽑은 후 그 숫자를 처음 인덱스부터 N-K인덱스까지 순회하며 K 범위 내 숫자를 전부 뒤집고 다시 큐에 집어넣습니다. 이 작업을 반복하며 해당 숫자가 오름차순으로 나오는 경우를 리턴해줍니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1327.java 2022. 3. 7. [BOJ]20040번: 사이클 게임 문제: https://www.acmicpc.net/problem/20040 유니온/파인드 문제입니다. 진행된 차례 m의 상한이 100만이므로 한 차례마다 사이클 탐색에 O(M)이 소모되면 O(M^2)으로 시간초과가 됩니다. 그러므로 현재 차례에서 사이클을 탐색하는데 시간을 줄여야 시간 초과가 나지 않습니다. 사이클 판별 방법 1. 매 두 점이 들어올 때 마다 두 점을 union 연산으로 같은 컴포넌트로 연결시켜줍니다. 2. 특정 차례에서 들어온 두 점이 이미 같은 컴포넌트에 있다면, 이 둘을 연결시키면 싸이클이 만들어집니다. 싸이클 판별인 find 연산에 O(logM)이 걸리므로 시간 복잡도는 O(MlogM)입니다. 코드: https://github.com/cotchan/algorithm/blob/mai.. 2022. 3. 6. [BOJ]1477번: 휴게소 세우기 문제: https://www.acmicpc.net/problem/1477 nnnyeong님 풀이를 참고하여 해결하였습니다. 이분 탐색을 활용한 결정 문제입니다. 결정 조건은 "휴게소 M개 사이의 거리를 distance 로 하였을 때 몇 개의 휴게소를 새로 세울 수 있느냐" 입니다. 그리고 이 distance 값을 이분탐색으로 찾으면서 M개 이하를 세울 수 있는 distance의 최솟값을 구하면 됩니다. M개 이하라고 한 이유는, M개 미만의 휴게소를 세워서 distance 조건을 만족할 수 있다면 휴게소를 한 개 씩 더 추가해서 distance를 더 줄일 수 있고 이렇게 늘려가다보면 결국 딱 M개의 휴게소를 세울 때의 거리가 정답 후보가 됩니다. 그 정답 후보들의 최솟값을 구해주면 됩니다. 코드: htt.. 2022. 3. 6. [PRGRMS]92335번: k진수에서 소수 개수 구하기 문제: https://programmers.co.kr/learn/courses/30/lessons/92335 시뮬레이션 문제입니다. 제일 중요한 조건은 '단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.'라는 조건입니다. 위 조건으로 인해 아래 3단계를 거쳐서 정답을 구할 수 있습니다. 1. 주어진 숫자를 k진수 변환 2. 0을 기준으로 split 3. 남아있는 숫자들에 대해 소수 판별 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/k%EC%A7%84%EC%88%98%EC%97%90%EC%84%9C%20%EC%86%8C%EC%88%98%20%EA%B0%9C%EC%88%98%20%EA%B5%AC%ED%95%98%EA%B8%B0.java 2022. 3. 5. 이전 1 ··· 9 10 11 12 13 14 15 ··· 91 다음
