본문 바로가기

파이썬91

[BAEKJOON]13417 카드 문자열 문제 요약알고리즘 분류: deque, 문자형, ASCII난이도:  Silver3문제내용:가장 처음에 가져온 카드는 자신의 앞에 놓는다.그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.사이트: https://www.acmicpc.net/problem/13417문제풀이 이번 문제에서는 데크활용 하는 문제이다.데크 자료구조는 앞뒤로 삽입, 삭제가 용이 하는 점에서 이용하면 앞에 문자보다 우선 순위가 크면 뒤로 추가 하고 작으면 앞으로 추가만 하면 된다. 하지만 문자형은 단순하게 크기 비교 처리하기가 힘들다 .. 2024. 11. 12.
[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] 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.

티스토리툴바