Dior2ky의 it's IT

백준 18258번 큐2 문제이다. 문제를 보면 명령어를 계속해서 받고 명령어에 따라 큐를 처리해주면 되는 문제이다. 코드를 짜는 것은 쉽다, 하지만 리스트로 구현을 하는 경우 O(n)의 복잡도를 갖기 때문에 시간 초과가 발생한다. O(1)의 복잡도를 갖는다는 Queue를 사용하여 구현을 하려 했으나 어디서 큰 복잡도를 갖는것인지 시간초과가 나왔다... 결국엔 deque를 사용하여 풀었다. deque가 속도나, 사용하기에 훨씬 편한것 같다. 코드는 다음과 같다. import sys from collections import deque n = int(sys.stdin.readline().strip()) deq = deque() for i in range(n): ins = sys.stdin.readline()..

백준 2164번 카드2 문제이다. 문제를 보면 문제만 보면 리스트를 반복문을 통해 요소를 삭제하고 맨뒤로 돌리고 반복해주면 쉽게 풀릴 것으로 보였다. 코드를 작성하고 제출을 했지만... 시간초과가 나왔다. 크게 시간복잡도가 큰게 없다고 생각해서 찾아보니 리스트의 del, insert와 같은 함수들은 시간 복잡도가 O(n)이라고 한다. deque를 이용하면 시간복잡도를 O(1)로 줄일 수 있다고 한다. 코드를 보면 import sys from collections import deque deq = deque() n = int(sys.stdin.readline().strip()) for i in range(n): deq.append(i) while True: if len(deq) == 1: break deq..

백준 1021번 회전하는 큐 문제입니다. 처음에 문제 이해하기가 약간 까다로웠다. 설명에는 큐의 원소 갯수 n과 위치가 나온다고 설명이 되어있지만 입출력을 보면 둘째줄의 숫자들이 위치를 나타내는 숫자들이다. 입력의 첫째줄은 큐의 크기, 뽑아내려 하는 요소 갯수 이고 둘째줄은 요소의 초기 위치이다. 세가지 연산이 주어진다. 1번은 맨 첫번째 요소를 뽑아내는 연산 2번은 왼쪽으로 하나씩 밀고 첫번째는 맨뒤로 보내는 연산 3번은 오른쪽으로 하나씩 밀고 맨 뒤의 요소를 맨 처음으로 보내는 연산 출력 값은 사용되는 2, 3번 연산의 최소 횟수이다. 원하는 요소를 뽑아낼때 왼쪽으로 밀어낼지 오른쪽으로 밀어낼지를 결정하고 최소로 만들어야 할것이다. 추가로 입력을 줄 때 굳이 뽑아내려 하는 요소 갯수가 필요했을까? 둘..

백준 10866번 덱 문제이다. 덱은 큐가 한쪽으로 들어와 반대쪽으로 나가는 것과 다르게 양쪽으로 자유롭게 들어오고 나가고 가능한 구조이다. 문제를 보면 총 몇번의 명령을 할지 입력 받고 명령에 따라 수행하면 될 것으로 보인다. push 명령의 경우에는 뒤에 숫자를 따로 받기 때문에 각 명령어에 따라 처리를 다르게 해 주면 될것으로 보인다. 해결한 코드는 다음과 같다. import sys cycle = int(input()) deq = [] for i in range(cycle): ins = sys.stdin.readline().strip() if ins == 'pop_front': if len(deq) == 0: print(-1) else: print(deq[0]) del deq[0] elif ins ..

백준 1966번 문제 제목에서도 알 수 있듯이 큐와 관련된 문제이다. 기본적인 큐의 push와 pop을 구현하면 되지만 이 문제에서는 중요도를 두어 중요도가 높은 문서가 큐에 있으면 맨 뒤로 보내기 때문에 pop을 한 뒤 다시 push를 해주면 될 것으로 보인다. 구현한 코드이다. obj = int(input()) for i in range(obj): count = 0 n, x = input().split() n = int(n) x = int(x) arr = input().split() for j in range(n): arr[j] = int(arr[j]) while True: flag = 0 for j in range(len(arr)): if arr[0] < arr[j]: flag = 1 if flag..

백준 14889번 스타트와 링크 문제이다. 이번 문제는 설명이 매우 길다. 사람을 두 그룹으로 나누어 묶고 시너지 표를 보고 각 그룹의 시너지의 차이를 구하면 된다. 이해가 잘 안된다면 입출력 예시를 본다. 이번 문제도 백트래킹 문제이기 때문에 한 그룹에 사람을 한명씩 넣어가도록 한다. 한 그룹에 사람이 반절 차게 되면 다른 한 그룹도 정해지게 된다. 그룹이 정해지는 순간 시너지 표에서 각 그룹의 시너지 합을 구해 차를 비교해준다. 차가 최솟값이 되어야 하기 때문에 최솟값으로 구해진 값과 비교하여 갱신해준다. 여기서 생각해줘야 할 점은 solve 함수에 들어간 k값이다. k 값을 넣음으로써 그룹에 한 사람이 들어갔다면 다시 처음사람부터 확인하는 것이 아니라 k번째 다음 사람부터 확인이 가능하다. def ..

백준 14888번 연산자 끼워넣기 문제이다. 연산자 끼워넣기 문제이다. 역시 백트래킹 문제이고 이전에 N과 M 문제는 숫자를 하나씩 넣어가면서 수열을 만드는 것이었다면 이번에는 연산자를 하나씩 넣어서 확인하는 방식이다. 숫자와 연산자 갯수를 배열에 넣어주고 연산자를 하나씩 골라가면서 연산을 해주면 될 것으로 보인다. 최댓값, 최솟값을 구해야 하기 때문에 연산자를 모두 쓰는 순간, 나온 값을 최댓값 최솟값과 비교하여 갱신해주면 될 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStream..

백준 2580번 스도쿠 문제이다. 스도쿠에 대한 규칙은 일반 스도쿠와 동일한 것으로 보인다. 빈칸을 0으로 표시하고 있다. 빈칸에 숫자를 하나씩 넣어가면서 확인해주는 백트래킹 방식이다. 이번에도 하나씩 넣어가는 solve 함수와 다음 빈칸에 숫자를 넣으러 넘어갈지를 판단해주는 promise 함수로 이루어져 있다. promise 함수에서는 가로 세로, 포함된 3x3 칸에 숫자가 있는지 확인하여 있다면 false를 리턴하여 다음으로 넘어가지 않도록 하였다. 여기서 3x3칸을 확인할 때에는 가로 세로 값인 i 와 j를 3으로 나눈 몫을 확인하여 0, 1, 2 값으로 3구역으로 나뉘기 때문에 어느 3x3 구역인지 확인하도록 하였다. import sys def promise(i, j, k): for m in ra..

백준 9663번 N-Queen 문제이다. 백트래킹으로 가장 유명한 문제라고 할 수 있는 체스판에 퀸을 놓는 문제이다. 이번 문제에서는 하나씩 놓아가면서 놓았을때 퀸이 놓일 수 있는 조건을 확인해서 놓도록 해주었다. func 함수를 통해 재귀 방식으로 하나씩 놓아가도록 하였고 promising 함수를 통해 놓는것이 가능한지 파악하였다. 언어는 C++을 사용하였다. #include using namespace std; int n; int result = 0; int arr[15] = {0,}; bool promising(int i){ for(int j = 0; j < i; j++){ if(arr[i] == arr[j] || abs(arr[i] - arr[j]) == (i - j)){ return false;..

백준 15652번 N과 M (4) 문제이다. 역시 N과 M 문제이다. 단계별로 풀어보기 백트래킹 항목에 있는 마지막 N과 M 문제이다. (다른 N과 M 문제들은 더 있다...) 이번에는 비 내림차순이라고 한다. 다른말로 하면 오름차순에 중복까지 가능하다고 생각하면 된다. 역시 백트래킹 문제이므로 비슷하게 풀어준다. N과 M (2) 문제와 비교하면 편할 것 같다. (2) 문제에서는 숫자 하나를 사용하면 그 숫자까지의 check 배열을 증가 시켰지만, 이번에는 그 숫자가 중복이 가능하므로 그 숫자 하나 아래 값 까지만 check 배열의 값을 증가시킨다. 이번 문제는 ruby 언어를 사용하였다. def func(cnt) if cnt == $m for i in 0...$m print $arr1[$arr2[i]]..