java157 [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] 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. [BAEKJOON] 1072 게임 문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:X: 게임 횟수, Y: 이긴 횟수, Z: 승률(정수)계속 이긴다고 가정 했을때 몇판 더해야 승률이 변하는지 구하여라 만약 변하지 못하면 -1로 반환 하여라사이트: https://www.acmicpc.net/problem/1072 문제풀이 이번 문제는 하나씩 +1 씩 대입해서 정답은 나오지만 최대 숫자가 100억이다. 그리고 승률은 소수가 아닌 정수이다. 그럼 변화할라면 1%올라가야 하는데 1000억기준으로 올라갈라면 최대 10억번을 탐색 해야 한다. 그럼 초당 연산 1억기준으로 O(N)탐색 하면 오류가 날수 있다. 그래서 O(logN)탐색 시간초과 이내로 끝내야 통과가 된다. 그래서 이진탐색으로 해결할것이다. 이진탐색에 대한 내용은.. 2024. 10. 28. [Leetcode]1222. Queens That Can Attack the King 문제 요약알고리즘 분류: 배열, 시뮬레이션, 구현난이도: Medium문제내용:8 × 8 체스말이 주어진다. 체스말에서 king 1명, queen N명이 있다.Queem 중에서 왕을 잡을수있는 Queen의 위치들을 반한 하여라단 앞에 가로 막는 퀸이 있으면 그것은 제외 해야 한다.사이트 주소: https://leetcode.com/problems/queens-that-can-attack-the-king/description/문제풀이 이번 문제는 구현 문제중에서 시뮬레이션 문제이다. 각 Queen을 이동 시켜 King까지 갈수 있는지 체크만 하면 되는 문제이다. 일단 퀸이 움직일수있는 방향은 대각선, 가로, 세로 총 8군대이다. 하지만 각 queen이 8방향 탐색하면 시간적으로 비효울이 나와서 반대.. 2024. 10. 27. 이전 1 ··· 3 4 5 6 7 8 9 ··· 27 다음
