IBOK

거의 모든 문제에 defaultdict를 사용하는 나 이유는 일단 너무 편하다 그리고 처음에 모든 case에 대해 다 메모리를 할당하는 것보다 메모리를 아끼는 느낌을 받을 수 있다. 근데 이전에 올린 백준 14425번에 이어서 이번에도 계속 시간초과가 발생한 원인이 defaultdict였다.. 🌼 문제 링크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 티어: 골드 III 분류: 구현, 자료구조, 시뮬레이션 문제 자체는 그냥 ..

Trie를 연습해볼 수 있는 대표적인 문제이다. 사실 python으로 푸는 경우 Trie를 이용하는 것보다 set을 이용하는게 더 빠르다 (이유는 set은 HashTable로 구현되어 있어, 원소 탐색에 선형시간이 걸리기 때문이라고 함). 심지어 python으로 하면 통과를 못하고, Pypy3으로 제출해야 한다. 나는 trie 연습을 위해 trie로 풀어 보았다. Node의 children을 dictionary로 구현하는 것보다는 defaultdict로 구현하는 게 search에서 더 유리할 것 같다고 생각했는데,오히려 시간이 더 걸려서 그 이유를 알아보았다. 🌼 문제 링크 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (..

그리디로 못푸는 문제이길래 DP인줄 알고 짰다가 DP도 아니구나 싶어서 DFS 비슷하게 풀었다가 시간초과가 떠서 DFS + DP로 성공 🌼 문제 링크 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 티어: 골드 V 분류: 다이나믹 프로그래밍 ❗ TRIAL 1. 더보기 코드 def solution(N, coins, target): c = coins.pop() #largest if N == 1: if target % c == 0: ..

DFS로 풀었다가 실패하고 DP로 성공 실버 3 절대아님 🌼 문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 티어: 실버 III 분류: 다이나믹 프로그래밍 ❗ TRIAL 1. 더보기 코드 import sys input = sys.stdin.readline def dfs(stairs, val, ctr): if not stairs: return val next_val = stairs.pop() if ctr != 2: dfs1 = dfs(stairs,..

분노의 테트리스.. 머리가 나쁘면 몸이 고생한다 🌼 문제 링크 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 티어: 골드 IV 분류: 구현, 브루트포스 알고리즘 ❗ TRIAL 1. 더보기 코드 import sys input = sys.stdin.readline from collections import deque N, M = list(map(int, input().split())) paper = [] totalmax = 0 for _ in r..

분노의 토마토...🍅 접근방법이 틀려서 알고리즘을 몇번씩 수정했다 🌼 문제 링크 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 티어: 골드 V 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ❗ TRIAL 1. 더보기 코드 import sys input = sys.stdin.readline from collections import deque M, N, H = map(int, input().split()) #fill..

$O(n^2)$ 실행시간을 갖는 정렬 알고리즘 세 가지와 $O(n\log n)$ 실행시간을 갖는 정렬 알고리즘 두 가지, 그리고 각 정렬 알고리즘의 파이썬 코드를 정리했다. 목차 $O(n^2)$ 정렬 알고리즘 Bubble sort Selection sort Insertion sort $O(n\log n)$ 정렬 알고리즘 Merge sort Quick sort 다음 사이트에서 각 정렬 알고리즘의 시각화를 한눈에 확인할 수 있다. Comparison Sorting Visualization www.cs.usfca.edu $O(n^2)$ 정렬 알고리즘 다음의 세 정렬 알고리즘은 swap 함수를 사용한다. def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = ..

문제 설명을 그대로 구현했더니 시간초과가 떠서, 좀더 효율적인 방법을 고안해야 했음. 🌼 문제 링크 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 티어: 실버 I 분류: 구현 ❗ TRIAL 1. 더보기 코드 def move(v1, v2, direction, arr, ans): if direction == 'l': x = v1[0] for y in r..

조건을 엄청 추가해서 푼 구현 문제. 코드가 너무 더러운데 더 좋은 풀이 방법이 있을 듯 🌼 문제 링크 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 티어: 실버 I 분류: 구현, 자료구조, 스택, 재귀 ❗ TRIAL 1. 더보기 코드 inputs = list(input()) couple = {'(': ')', '[': ']'} value = {'(': 2, '[': 3} while len(inputs) != 1: ctr = 0 new_in..

그래프 탐색 문제인데 수학적으로 머리를 잘 굴려서 최대한 효율적으로 탐색해야 하는 문제였다. 계속 시간초과가 떠서 이것저것 규칙을 추가하다가 문제를 발견하고 성공했다. 🌼 문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 티어: 실버 I 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ❗ TRIAL 1. 더보기 코드 from collections import deque walk_left = lambda x..