DolphinDash

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 뭔가 그래프 문제를 풀어보고 싶었는데 딱 그래프같아서 한번 풀어봤다. 아래 코드는 코드를 다듬지 않고 풀었을 때 나온 코드다. def get_surroundPos(field, pos, MW, MH): rPos = [] if pos[0] - 1 >= 0: if field[pos[0]-1][pos[1]] == 0: rPos.append((pos[0]-1, pos[1])) field[pos[0]-1][pos[1]] = 1 if pos[0] + 1 < ..

1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 처음엔 linked list로 순환 구조를 만들어서 풀려다가 아직 class를 잘 못다루다 보니 선언부분에서 막혔다. class node: def __init__(self, data) -> None: self.data = data self.next = None def nextNode(self): return self.next def setNext(self, next): self.next = next head = Node(1) head.next = Node(2) heads = head.next for i in range(3, N+1): heads = he..

처음에 봤을 때 막막했는데 경우의 수를 나열했을 때 익숙한 숫자 배열이여서 조합인걸 알았다. 그래서 조합을 사용해서 코드를 짜 봤는데, import itertools N = int(input()) for i in range(N): a, b = map(int, input().split()) nCr = itertools.combinations([f"{i}" for i in range(b)], a) print(len(list(nCr))) 오른쪽 다리의 최대 갯수가 30개인걸 생각하면 조합을 사용해서는 시간 초과가 나올 것이 분명해서 그냥 식을 써봤다. import sys sys.getrecursionlimit = 1000000 N = int(input()) def nCr(n, r): return (fac(n)..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리의 순회 방식 3가지를 알면 쉽게 풀 수 있는 문제다. Preorder (전위 순회) 루트부터 먼저 방문한 다음 왼쪽 하위 트리, 오른쪽 하위 트리 순으로 방문하는 방식 Inorder (중위 순회) 왼쪽 하위 트리 먼저 방문하고 이후 루트 트리, 오른쪽 하위 트리 순으로 방문하는 방식 Postorder (후위 순회) 왼쪽 하위 트리 먼저 방문한 후 이후 오른쪽 하위 트리, 마지막으로 루트 트리를 방문하는 방식 딕셔너리로 노트 이름을 저장해 set으..

간단한 dp문제인 줄 알고 덤볐다가 조금 오래걸렸다. 처음엔 def dp(que, target, tries): nq = [] if que[0] > target: return -1 for value in que: if value * 2 == target or value * 10 + 1 == target: return tries+1 else: nq.append(value*2) nq.append(value*10 + 1) return dp(nq, target, tries+1) a, b = map(int, input().split()) print(dp([a], b, 1)) 재귀 함수를 만들어서 돌렸더니 메모리 초과가 났다. 일단 tries 횟수가 높아지면 높아질수록 필요 메모리양이 늘어나고 que[-1]의 메모리..