IT 꿈나무 참다랑어

[Gold IV] 이중 우선순위 큐 - 7662 문제 링크 성능 요약 메모리: 439256 KB, 시간: 2580 ms 분류 자료 구조, 우선순위 큐, 트리를 사용한 집합과 맵 제출 일자 2023년 12월 14일 23:24:54 문제 문제 설명 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분..

[Gold III] 세 용액 - 2473 문제 링크 성능 요약 메모리: 14224 KB, 시간: 164 ms 분류 이분 탐색, 정렬, 두 포인터 제출 일자 2023년 12월 13일 00:51:05 문제 문제 설명 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가..

[Gold III] 괄호 추가하기 - 16637 문제 링크 성능 요약 메모리: 11640 KB, 시간: 76 ms 분류 브루트포스 알고리즘, 구현 제출 일자 2023년 10월 17일 14:31:24 문제 문제 설명 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 4..

1. 문제 요약 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 하나의 소수에서 한자리씩 바꿔가면서 다른 소수를 만들어야 한다. 몇 단계를 거쳐야 지금의 소수에서 목표 소수를 만들 수 있을까? 2. 입/출력 3. 접근 아이디어 일단 먼저 해야할 일을 정리해야한다. 1. 하나의 소수에서 한자리씩 바꾼다. 2. 바꾼 숫자가 소수인지 아닌지 확인한다. 3. 소수라면 해당 숫자에서 또 다른 숫자로 갈 수 있도록 1, 2번을 반복한다. -> 그렇다면 이 과정에서..

1. 문제 요약 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 골드인..이유가 있었ㄷ... 초, 중등 수학에서 많이 하던 일인데 코딩으로 막상 옮기려니까 생각이 잘 안났음. 알파벳에 숫자를 대입하는데 어떤 수를 대입해야 모든 단어의 합이 최대가 될까? 미리 얘기하자면 문자 길이나 등장 횟수만 고려해서는 답이 안나왔다..(여러번의 시도가 여기 담겨있음) 2. 입/출력 입출력이 정말 짧다. 시간 신경쓰지말고 구현 아이디어에 집중해야 한다....

1. 문제요약 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 나도 미래를 알면 좋겠다.. 암튼 최대의 이익을 얻기 위해서는 각각의 날짜에 주식을 사야하는지, 팔아야하는지, 아니면 가만히 있어야하는지 판단해야 한다. 2. 입/출력 주가는 작지만 N도 크고 특히 출력에서 부호있는 64bit 정수형으로 표현 가능하다고 했다. int는 32bit이다.. 크기에 주의하자(이거때문에 틀렸습니다 받음..) 3. 접근 방식 앞에서부터 나가면서 ..

1. 문제 요약 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 어떤 알파벳 문자가 정확히 K개가 포함된 문자열에 대하여... 그 길이가 최소인 것과 최대인 것을 찾는 것이다. 문제에서 4번 단계에서는 시작과 끝이 해당 문자이면서 K개를 포함하는 경우를 찾는데, 3번 단계에서는 따로 그런 설명이 없다. 근데 똑같은 문제임.. 길이가 최소인 것을 찾으려면 어쨌든 시작과 끝이 해당 문자이면서 K개를 포함하고 있을것! 그렇다면 우리는 문자가 언제..

1. 문제 요약 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net N개의 집 중에서 공유기를 설치할 C개의 집을 찾는다고 이해하면 제일 편한데 근데 이렇게 생각하면 조합이 떠오른다. 그치만 200,000개의 집 중에서 100,000개의 공유기를 설치할 집을 고른다? 말이 안된다.. 다른 방법을 찾아야 함 2. 입/출력 앞에서도 말했듯 조합으로 생각하기에는 숫자가 너무 크다.. 그렇다면 어떻게 해..

문제 요약 https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 문제를 이해하는 것은 어렵지 않았다. 다만 대소문자 처리가 복잡했을 뿐.. 문제에서 지정한 규칙에 따르면 이미 지정된 알파벳과 겹치지 않게 단축키를 지정해야했다. 일단 단어의 시작을 먼저 살펴보고 그 다음에는 단어의 중간글자들도 앞에서부터 차례대로 살펴본다. 등록할 수 있는 단어가 없다면 원형 그대로를 출력 입/출력 단축키로 지정된 알파벳 좌우에 대괄호! 접근 아이디어 일..

문제 요약 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 어렵다.. 행렬 곱셈도 이해하고 있고.. 순서에 따라서 필요한 연산 수가 달라진다는 것도 이해했으나.. 이걸 어떻게 최소의 연산을 생각하는가.. 이해가 가지 않았다... 입/출력 다행스럽게도 문제에서 결합법칙만 신경쓰면 된다. 행렬의 순서를 다시 배치하지는 않아도 된다. 입출력이 크지 않다고 생각할 수 있으나 행렬의 개수가 500개이고 어떤걸 먼저 계산할건지 하나하나 다 해..