[Gold I] 멀티탭 스케줄링 - 1700문제 링크성능 요약메모리: 31120 KB, 시간: 32 ms분류그리디 알고리즘제출 일자2024년 11월 14일 11:34:12문제 설명기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 ..

[Gold V] 빗물 - 14719문제 링크성능 요약메모리: 34052 KB, 시간: 116 ms분류구현, 시뮬레이션제출 일자2024년 11월 12일 22:28:08문제 설명2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?입력첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.출력2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을..

[Gold V] 괄호의 값 - 2504문제 링크성능 요약메모리: 31120 KB, 시간: 36 ms분류자료 구조, 구현, 스택제출 일자2024년 11월 12일 02:22:50문제 설명4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 ..

[Silver I] 연산자 끼워넣기 - 14888문제 링크성능 요약메모리: 31120 KB, 시간: 60 ms분류백트래킹, 브루트포스 알고리즘제출 일자2024년 11월 10일 18:43:58문제 설명N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총..

[Silver I] 십자가 찾기 - 16924문제 링크성능 요약메모리: 48100 KB, 시간: 592 ms분류브루트포스 알고리즘, 구현, 시뮬레이션제출 일자2024년 11월 10일 01:34:56문제 설명십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크거나 같아야 한다.아래 그림은 크기가 1, 2, 3인 십자가이고, 빈 칸은 '.'이다. ...*... ..*.. ...*....*. ..*.. ...*...*** ***** *******.*. ..*.. ...*... ..*.. ...*....

[Silver I] NM과 K (1) - 18290문제 링크성능 요약메모리: 31120 KB, 시간: 2996 ms분류백트래킹, 브루트포스 알고리즘제출 일자2024년 11월 5일 14:53:46문제 설명크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.입력첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.출력선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출..

[Silver I] 숫자 재배치 - 16943문제 링크성능 요약메모리: 100324 KB, 시간: 360 ms분류백트래킹, 브루트포스 알고리즘, 조합론, 수학제출 일자2024년 11월 2일 22:22:49문제 설명두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다.가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.입력첫째 줄에 두 정수 A와 B가 주어진다.출력B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.풀이 나의 잘못된 접근 (Greedy 이용)import sysA , B = map(str , sys.stdin.readline()...

[Gold V] 토마토 - 7576문제 링크성능 요약메모리: 117776 KB, 시간: 1300 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2024년 11월 2일 12:44:54문제 설명철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며..

최대 힙의 성질최대 힙은 완전히 크기 순서대로 정렬되어 있지는 않다. 따라서 탐색 연산은 지원하지 않는다.루트 노드가 항상 최댓값을 가진다.완전 이진 트리이다.최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.배열을 이용한 이진트리의 표현왜 트리와는 다르게 heap은 배열을 사용하여 표현할까?Tree를 구현할 때 흔히 사용하는 linked list 방식으로 하면 마지막 인덱스에 데이터 추가하는 일이 쉽지 않다.마지막 리스트를 찾기위한 연산의 복잡도는 트리의 높이만큼 탐색해야하기 때문에 O(h)임.힙은 완전 이진트리라는 것이 보장된 형태이 기 때문에, 마지막 레벨을 제외한 모든 레벨의 노드가 가득 채워져있다. 따라서 완전 이진트리의 삽입은 배열 끝 인덱스에 append해주는 것과 같으며,..