동까의 코딩

브론즈 1 문제이지만 메모리 초과가 많이 나오는 문제라서 작성하여본다. https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net append / sort를 사용하면 메모리를 다시 재설정해줘서 추가하기 때문에 메모리 초과가 난다. 메모리를 미리 할당 시켜주고, 해당 인덱스에 1씩 더해줘서 처음부터 추가된 숫자 인덱스만큼만 출력해주면 답이 나온다. import sys n = int(sys.stdin.readline()) num_list = [0] * 10001 for _ in..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 브루드 포스 기본문제인 일곱 난쟁이를 풀어보았다. 이 문제를 풀어보면서 브루드포스에 대한 내용도 인지하였고, dfs를 사용하여 풀이했다. short_men = [int(input()) for _ in range(9)] search_short_men = [] def dfs(depth, start): if depth == 7: if sum(search_short_men) == 100: for j in sort..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 브루드 포스 기본문제인 일곱 난쟁이를 풀어보았다. 이 문제를 풀어보면서 브루드포스에 대한 내용도 인지하였고, dfs를 사용하여 풀이했다. short_men = [int(input()) for _ in range(9)] search_short_men = [] def dfs(depth, start): if depth == 7: if sum(search_short_men) == 100: for j in sort..

기본적인 구현문제인 카드1 문제를 풀어보았다. https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 간단한 구현으로 풀이하였다. from collections import deque N = int(input()) num_lst = deque([i for i in range(1, N + 1)]) num_lst.reverse() while num_lst: cut_num = num_lst.pop() print(cut_num, end=' ') if num_..

스택 문제 중 하나인 막대기를 풀어보았다. https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 스택에 다 넣어주고 빼면서 높은 건물이 나올때 기준 높이를 바꿔주면 될 것 같다. 오른쪽부터 시작하니 맨 오른쪽을 기준 높이로 잡고 왼쪽으로 하나씩 확인해 나간다. import sys input = sys.stdin.readline N = int(input()) stack = [] cnt = 1 for _ in range(N): num = int(input()..

스택과 큐 문제 중 하나인 키로거 문제를 풀어보았습니다. 난이도는 중정도로 될 것 같습니다. https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 풀이 방식은 스택을 두 개로 사용하는 방법을 선택하였습니다. 처음에는 시뮬레이션 그대로 코딩을 짜주다가 시간 제한이 뜨게 되어 스택을 사용하는 방법을 찾아보았더니 간단한 해답이 나왔습니다. 왼쪽 스택과 오른쪽 스택으로 나눠주어 그 사이에 커서를 두고 진행하면 간단합니다. 단어를 넣거나 뺄 때는 왼쪽..

오늘은 프린터 큐 문제를 풀어보았습니다. 문제는 구조는 기본 Queue의 자료구조인 FIFO - First In First Out를 문제로 만들었습니다. https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 풀이 방법으로는 deque를 사용해서 최대한 queue에 중점을 주고 문제를 풀었습니다. 1. 먼저 m의 위치를 기억해 주고, 위치를 옮겨줄 때마다 위치를 업데이트해 준다. 2. 가장 큰 값이 먼저 나가므로 맨 앞에 가장 큰 값이 오면 pop을..

기본 스택 문제 중 하나인 스택 수열 문제를 풀어보았습니다. https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제를 처음 보았을 땐 이해가 되지 않았지만 아래 힌트를 보고 풀이를 하였습니다. 제일 먼저 입력된 숫자만큼 count를 해줘서 push를 진행해 주고, 해당 숫자가 나오면 반복문을 탈출하여 pop을 진행하고 숫자를 빼내어 줍니다. 예제 1을 예로 들어보면..