[백준/Python] 20920번. 영단어 암기는 괴로워

문제https://www.acmicpc.net/problem/20920   풀이특정 길이 이상의 문자열을 입력받아 아래의 3가지의 조건으로 정렬하는것이 핵심이다.  1. 각 단어별 등장횟수를 기록해둔 숫자를 내림차순2. 등장 횟수가 같다면 단어의 길이로 내림차순3. 단어의 길이가 같다면 알파벳순 단어별 등장 횟수 기록은 defaultdict(int)를 이용하여 처음 등장하면 딕셔너리에 단어가 추가되며 값으로 1이 저장되고 두번째로 등장하면 값에 1씩 추가되는 방식으로 기록하였다. sorted(iterable 한 객체, key=lambda x: (-조건1, -조건2, 조건3))sorted와 key에 lambda식을 사용하면 첫번째 인자인 iterable 한 객체를 여러 조건으로 정렬가능하다.이 문제에서는 ..

• format_list_bulleted 알고리즘/백준
• · 2025. 2. 4.
• textsms

[백준/Python] 11726번. 2×n 타일링

문제https://www.acmicpc.net/problem/11726  풀이일단 직접 그려보자. 규칙이 보일듯 말듯 하다. 각 인덱스에서 n-1 인덱스에 등장했던 모양을 포함하는 수와 새로 등장한 모양의 수를 세서 더한 값은 다음과 같다. 그렇다. 각 색상은 이전의 두 숫자의 합이 다음 숫자가 되는 피보나치 수열을 따르고 있다.이제 정답 인덱스의 값을 구해서 10007로 나눈 나머지를 출력하면 된다.   정답 코드n = int(input())dp = [1, 2]while n > len(dp): dp.append(dp[-1] + dp[-2])print(dp[n - 1] % 10007) 점화식: dp[n] = dp[n-1] + dp[n-2]

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 20.
• textsms

[백준/Python] 21314번. 민겸 수

문제 https://www.acmicpc.net/problem/21314   풀이우선 "민겸 수"와 "민겸 숫자"는 다른 개념이다. 민겸 숫자가 모이면 민겸 수가 되는것에 주의하자최소 최대값 모두 MK / K / MMK와 같이 K가 나올때까지 M의 갯수를 센다 최대값을 찾는법: K가 나올 경우 K까지 포함하여 끊어서 해당하는 민겸숫자를 문제에 제시된 변환 표 대로 변환하여 이어준다.끊어낸 마지막 덩어리가 M으로 끝날 경우 M의 갯수만큼 1로 채운 값을 이어준다.  최소값을 찾는법:K가 나올 경우 K를 포함하지 않고 끊어서 해당하는 민겸숫자를 문제에 제시된 변환 표 대로 변환하여 이어준다.(MMK와 같이 끊어진 경우 K를 포함하지 않고 MM까지만 변환)그 이후 K를 포함하지 않고 끊었으므로 K의 민겸숫자에..

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 17.
• textsms

[백준/Python] 20300번. 서강근육맨

문제https://www.acmicpc.net/problem/20300   풀이가장 큰 값과 가장 작은 값을 취하면 되는 그리디 문제이다.정렬한다최대 근손실을 홀수면 가장 큰수를 pop해서 초기화하고 짝수면 0으로 초기화한다남은 수중 가장 큰 값, 가장 작은 값을 을 pop해서 더한 값이 최대 근손실보다 크면 교체한다남은 수가 없어질 때까지 3번을 반복한뒤 최대 근손실을 출력한다참 쉽죠?  정답 코드from collections import dequeN = int(input())M = list(map(int, input().split()))M.sort()M = deque(M)maxM = 0if len(M) % 2 != 0: maxM = M.pop()while len(M) > 0: m = M.p..

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 17.
• textsms

[백준/Python] 1027번. 고층 건물

문제https://www.acmicpc.net/problem/1027  사고 과정처음에는 서로 보이는지 판단할 두 빌딩 사이의 모든 빌딩이 두 빌딩의 높이보다  낮은 경우를 구하면 되지 않을까 싶었다.하지만 이 그림과 같이 1, 3 두 빌딩 사이의 빌딩 2번은 3번보다 높은데도 불구하고 1과 3 빌딩은 서로를 볼 수 있어서 정답이 아니었다.두번째로 사이의 빌딩들의 제한높이를 두 빌딩 의 높이의 차이를 이용해 수동으로 구하는 방법을 생각했는데1과 4 사이의 높이 차이는 6이며 사이의 빌딩은 2개이므로 아래와 같이높이의 차이를 2개로 쪼개 3등분한 값을 더해가며 제한 높이를 수동으로 구하여 풀어보았는데이론상 정답인것 같으나 부동소숫점 연산의 부정확성 문제 추측되는 이유로 틀렸다.  풀이따라서 아래와 같이 두..

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 17.
• textsms

[백준/Python] 9935번. 문자열 폭발

문제https://www.acmicpc.net/problem/9935  풀이문자열에서 폭발 문자열이 없어질때까지 반복해서 찾아 지워나간다면 이론적으로 풀리기야 하겠지만 시간이 초과된다. 스택을 이용하면 전체 문자열에서 폭발 문자열을 찾는데 소요되는 시간, 문자열에서 폭발문자열을 반복하며 도려내어 새로운 문자열을 만드는 시간을 단축하여 빠르게 해결이 가능하다. 문자열을 앞에서부터 한글자씩 끝까지 순회하며 스택에 push하면서 스택의 윗부분과 폭발 문자열이 일치한다면 폭발 문자열의 길이만큼 pop해주기만 하면 한번의 순회로 쉽게 해결이 가능하다.    정답 코드msg = input()bomb = list(input())answerStack = []for letter in msg: answerStack...

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 15.
• textsms