Berom's Blog

백준 7662 이중 우선 큐문제이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라. 풀이12345678 ...

백준 9375 패션왕 신해빈문제해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다. 출력각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오. 풀이123456789101112131 ...

그리디 알고리즘 정의 현재 상황에서 지금 당장 조은 것만 고르는 방법 정당성 분석이 중요함 단순히 반복하는게 아닌 결과 값을 보장하는가 해가 정당한지 점검할 수 있어야한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다 구현 구현이란, 머릿 속에 있는 알고리즘을 소스 코드로 바꾸는 과정 풀이를 떠올리는 것은 쉽지만, 소스 코드로 옮기기 어려운 문제를 지칭 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제 문자열을 특저안 기준에 따라서 끊어 처리해야하는 문제 적절한 라이브러리를 찾아서 사용해야하는 문제 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

백준 1316 - 그룹 단어 체커문제주어진 N 개의 단어들 중 그룹 단어는 몇 개인가? 그룹 단어란단어에 존재하는 모든 문자에 대하여 각 문제가 연속적으로 나타나는 단어를 말한다. aaabb는 그룹 단어이지만, aabba는 그룹 단어가 아니다 문제 풀이주요 아이디어단어에 존재하는 문자의 연속되는 최대 길이와 단어 내에 해당 문자가 몇 개있는지 비교한다. 두 값이 같을 경우에만 그룹 단어이다 풀이 순서 단어에 존재하는 문자의 연속되는 최대 길이를 Value, 해당 문자를 Key로 딕셔너리에 저장한다. 딕셔너리의 Value와 단어 내 문자의 갯수가 일치하는지 확인 일치하는 경우 checkPoint를 참으로 반환하고, count를 올린다. count 출력 Code1234567891011121314151617181920212223242526272829import sys num = int(sys.stdin.readline())strArr=[]count = 0for i in range(n ...

백준 1406 에디터문제한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. 명령어 기능 L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) P $ $라는 문자를 커서 왼쪽에 추가함 초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 ...

백준 1654 랜선 자르기문제박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오. 입력첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개 ...

백준 1918 후위 표기식문제입력된 중위 표기식을 후위 표기식으로 바꾸어 출력할 것 문제 풀이주어진 문자열의 첫 글자부터 문자열인지 파악한다. 문자열일 경우 바로 result에 추가한다. * 또는 / 가 올 경우 * 와 __/__가 연산의 우선순위에 있기 때문에 먼저 값을 뺀다 + 또는 - 가 올 경우* 스택의 끝에 ( 가 올 때까지 스택의 값을 result에 추가한다* 출력이 끝나면 (를 스택에서 빼낸다 ) 가 올 경우 스택의 끝에 (가 올 때까지 스택의 값을 result에 추가한다 * 나 - 가 괄호 안에 있을 경우 괄호 안의 값을 출력하기 위함 Code1234567891011121314151617181920212223242526import sysstack = []expression = list(sys.stdin.readline().rstrip())res = ''for s in expression: if 'A&#x ...

백준 2275 - 부녀회장이 될테야문제주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주하려면 a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 조건 아파트에 비어있는 집은 없고, 모든 주민들은 계약 조건을 지킨다. 아파트엔 0층이 존재, 0층의 i호에는 i명이 산다. 문제풀이주요 아이디어재귀 함수를 사용해서 문제를 풀었더니, 시간을 초과해버렸다. 재귀 함수의 경우 반복되는 연산이 많아 속도가 느려지는 단점이 있다. 이를 해결하기 위해 메모제이션(Memoization) 기법을 사용한다. 메모제이션이란 반복되지만 변하지 않는 값을 저장해, 해당 값이 필요할 때 다시 연산하는 것이 아니라 저장한 값을 가져오는 것이다. 이 문제의 경우 변수가 2 개여서 리스트를 이용해 메모제이 ...

백준 4673 - 셀프 넘버문제10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하라 셀프 넘버란양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.이 때 n을 d(n)의 생성자라한다. 즉 75는 87이다. 셀프 넘버는 생성자가 없는 수이다. 문제 풀이셀프 넘버를 어떻게 찾을 것인가?셀프 넘버는 전체 정수에서 생성자가 있는 숫자들의 차집합이다.셀프 넘버를 직접 구하기 보단 생성자가 있는 숫자들을 구해서 제거하는게 더 빠를거라 생각했다. 풀이 순서 0으로 초기화된 index 10000개 배열 arr을 생성 입력 값 n에 따라 생성자를 반환하는 함수 checkD 선언 인덱스 1~10000을 checkD()에 넣어 arr에 생성자를 체크한다 arr 내에 체크되지 않은 인덱스(셀프 넘버)를 출력한다 Code123456789101112131415161718192021222324 ...

선택 정렬‘가장 작은 것을 선택해서 제일 앞으로 보낸다.’ 생각에 기인한 알고리즘이다.배열 내에 인덱스는 이미 정해져 있고 그 위치에 어떤 값을 넣을지 고른다. 배열 내에 원소가 들어갈 인덱스(자리)는 이미 정해져 있고, 그 위치에 어떤 값을 넣을지 고르는 알고리즘이다. 10개의 원소 중 크기가 작은 원소부터 차례대로 배열에 넣어야 하는 상황을 생각해보자.이때 최솟값이 들어갈 자리는 배열의 제일 왼쪽으로 정해져 있다.10개의 원소 중 가장 작은 값을 찾기 위해 9번 비교해야 한다.2번째 최솟값은 8번, 3번째 최솟값은 7번 해야 한다. 즉 각각 (n-1) (n-2)… n번 비교하게 되고, 총 n(n-1)/2번 반복하면 정렬이 끝난다.그렇다면 선택 정렬의 시간 복잡도는 O(N^2)임을 알 수 있다(선택 정렬의 최선, 최악, 평균 시간 복잡도는 동일하다) 1234567891011121314151617181920let i, j, min, index, temp;let array ...