본문 바로가기

알고리즘184

[BAEKJOON]11055 가장 큰 증가하는 부분 수열 문제 요약알고리즘 분류: dp, LIS난이도:  Silver2문제내용:수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.사이트: https://www.acmicpc.net/problem/11055문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된.. 2024. 11. 24.
[BAEKJOON]11722 가장 긴 감소하는 부분 수열 문제 요약알고리즘 분류: dp, LIS난이도:  Silver2문제내용:수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.사이트: https://www.acmicpc.net/problem/11722문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된다.https://jih3508.tistory.com/46 [알고리즘.. 2024. 11. 24.
[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.

티스토리툴바