본문 바로가기

전체 글249

[BAEKJOON]14916 거스름돈 문제 요약알고리즘 분류: 그리디난이도:  Silver5문제내용:2원, 5원 동전으로 거스름 돈을 줄수 있다.거스름돈이 N일때 최소 동전 개수를 구하여라(안되면 -1로 출력하여)사이트: https://www.acmicpc.net/problem/14916  문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 최대 거스름돈이 10만이라서 모든 경우의 수를 구하면 시간 초과가 나서 O(N) 탐색으로 푸는 방법을 찾아야 될것이다. 그래서 이번 문제는 그리디로 풀것이다. 그리디에 대한 설명은아래글로 확인 해보면 된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알.. 2024. 11. 10.
[BAEKJOON]27961 고양이는 많을수록 좋다 문제 요약알고리즘 분류: 그리디난이도: Broze1문제내용:다음중 2가지 마법만 사용 할수있다.생성 마법: 고양이 1$1$마리를 마도카의 집에 생성한다.복제 마법: 현재 k개 있으면 k마리 이하만 복제 가능하다.사이트: https://www.acmicpc.net/problem/27961문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 10^12승 숫자 만큼 탐색하면 시간 초과가 나서 안될것이다. 그래서 O(logN)만큼 나오도록 구현 해야 한다. 그래서 이 문제는 그리디로 접근해야 한다. 그리디에 관련 내용은 아래글에서 확인해보면된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택.. 2024. 11. 10.
[BAEKJOON]7569 토마토 문제 요약알고리즘 분류: BFS, 그래프난이도: Gold5문제내용:문제풀이 CodePythonimport sysfrom collections import dequeinput = sys.stdin.readlinedef solution(boxs, location): dx = [0, -1, 0, 1] dy = [-1, 0, 1, 0] dz = [-1, 1] days = 0 queue = location while queue: z, y, x = queue.popleft() value = boxs[z][y][x] for i in range(4): fx = x + dx[i] fy = y + dy[i].. 2024. 11. 9.
[BAEKJOON] 2644 촌수계산 문제 요약알고리즘 분류: BFS, DFS난이도: Silver2문제내용:사이트: https://www.acmicpc.net/problem/2644문제풀이 CodePython Javaimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Map> adj = new HashMap(); int N .. 2024. 11. 4.
[BAEKJOON] 2805 나무 자르기 문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용: 사이트: https://www.acmicpc.net/problem/2805문제풀이 CodePythonn, m = map(int, input().split())trees = list(map(int, input().split()))min_value = 1max_value = max(trees)while min_value mid]) if m > lenth: max_value = mid - 1 else: min_value = mid + 1print(max_value)Javaimport java.io.BufferedReader;import java.io.IOException;import java.io... 2024. 11. 2.
[BAEKJOON] 11561 징검다리 문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:1번부터 N개번 징검 다리가 있다.첫 징검다리는 아무대나 점프할수 있다.그 다음 징검다리는 이전 이동한 거리보다 1이상 더 긴거리로 이동해야 한다.N번 까지 최대 몇번 건널수 있는지 구하여리첫줄에 케이스 T가 주어지고 각 케이스마다 N이 주어진다.사이트: https://www.acmicpc.net/problem/11561 문제풀이이번 문제에서 최대 징검다리수가 10^16 이다. 이정도 숫자이면 1 부터 10^16까지 탐색하면 시간초과가 나올것이다. O(N) 탐색이 아닌 O(logN)의 탐색으로 처리할수 있도록 해야 시간복잡도 문제를 해결할수 있다. 그래서 이번 문제는 이진 탐새으로 풀어야 할수 있다. 이진 탐색 관련글은 아래에서 확인.. 2024. 10. 29.

티스토리툴바