Dior2ky의 it's IT

백준 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..

백준 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..

백준 15650번 N과 M (2) 이다. 이전 N과 M (1)과 문제가 비슷하다. 이번에는 오름차순이어야 한다는 조건이 추가되었다. 이번에도 역시 백트래킹 문제이다. 이번에는 한 숫자를 골랐다면 다음자리에는 그보다 작은 숫자가 올 수 없기 때문에 check 배열에서 고른 숫자 이하의 자리는 모두 +1 해주고 빠져나오면 -1을 해 주었다. 물론 고를때에는 1이 아닌것으로가 아닌 0인지로 판단해주었다. 언어는 python을 사용하였다. def func(cnt): if cnt == m: for i in range(m): print(list1[list2[i]], end = ' ') print() for i in range(n): if check[i] == 0: for j in range(i+1): check[j..

백준 2231번 분해합 문제이다. 브루트포스 유형의 문제이다. 분해합에 대한 설명이 주어졌다. 해당 숫자와 각 자리의 숫자를 모두 더한 값을 분해합이라 정의하고 있고 원하는 문제의 답은 분해합을 구하는 것이 아닌 해당 분해합을 가지는 가장 작은 숫자를 구하는 것이 문제이다. 역시 브루트포스 문제이기 때문에 하나하나 확인하면 될것이다. 0부터 해당 숫자까지의 숫자들을 하나하나 분해합을 구해 해당 숫자가 되면 멈추고 출력하도록 만들어 주었다. 코드는 python 언어를 사용하였다. def bunhehap(n): tmp = n i = 1 result = n while True: tmp = tmp // 10 if tmp == 0: break i += 1 for j in range(i): result += (n ..