코테 준비하면서 다른 사람들의 분들의 풀이를 보면 `dict` 대신 `defaultdict`를 사용하는 경우를 종종 보았다. 그래서 `defaultdict` 라이브러리에 대해 알아보고자 정리하였다.defualtdict 라이브러리란?`collections` 모듈에서 제공되는 딕셔너리(dict)의 서브 클래스존재하지 않는 키에 접근했을 때, 미리 지정한 기본 값으로 키값 초기화키를 추가하려 할 때 키가 존재하지 않아 발생하는 `KeyError` 방지할 수 있음 일반 `dict`의 경우 d = {}d["a"] += 1 # KeyError`defualtdict`의 경우from collections import defaultdictd = defaultdict(int)d["a"] += 1print(d["a"]) ..

bisert 라이브러리란?`bisect`는 정렬된 리스트에서 이진 탐색(binary seach)을 쉽게 구현하게 해주는 파이썬 라이브러리정렬된 상태를 유지하면서 데이터를 삽입하거나 위치를 찾을 때 사용import bisect 그렇다면 `bisect` 라이브러리를 왜 사용할까?일반적으로 리스트에서 특정 위치를 찾을려면 시간 복잡도는 선형 탐색(O(n))를 가진다.하지만 이진탐색을 수행하는 `bisect`를 사용하면 탐색: O(log n) 삽입: 위치 찾기 O(log n) + 실제 삽입 O(n)다음과 같은 시간 복잡도로 정렬된 리스트를 효율적으로 관리할 수 있다.bisect 라이브러리 주요 함수bisect_left(lst, x)정렬된 리스트 `lst`에서 `x`를 삽입할 왼쪽 위치 반환같은 값이 여러 개 있..

문제 링크성능 요약메모리: 32412 KB, 시간: 120 ms분류구현, 브루트포스 알고리즘, 시뮬레이션, 백트래킹 # 1.입력/변수 정의N=int(input())board=[list(map(int,input().split())) for _ in range(N)]ans=0 # 2.알고리즘"""DFS를 이용한다.1. 한쪽 방향으로 보드를 민다(왼쪽 방향으로)2. 민 보드를 계산한다3. 계산된 보드는 다음 DFS로 넘긴다4. 보드를 회전한다-> 4방향으로 계속 돌려야하므로 총 모든 경우의 수는 4^5=1024"""def rotate(b): return list(zip(*b[::-1]))def move_left(b): new_board=[] for row in b: tmp=[x f..

문제 링크성능 요약메모리: 32412 KB, 시간: 1456 ms분류구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 격자 그래프 처음에 풀 때 자꾸 틀리길래 그 이유를 계속 못 찾다가 dfs 함수의 종료 순서 때문에 틀렸다는 것을 알게 되었다. 처음 짠 코드는 `#범위를 넘어서면`→ `#만약 벽을 3개 세웠다면` 해당 순서로 종료 조건을 주었는데 이렇게 되면 벽을 3개 다 세운 경우에도 `n >= len(loc0)`이면 BFS를 아예 안 돌고 종료돼서 ans가 갱신될 기회 자체가 없게 된다는 것을 알게 되었다.`#만약 벽을 3개 세웠다면` → `#범위를 넘어서면`순서로 종료 조건을 주어서 무사히 통과할 수 있었다.이번 풀이를 통해 종료 조건의 순서 또한 중요하다는 것을 알 수 ..

문제 링크성능 요약메모리: 32412 KB, 시간: 36 ms분류구현 첫 제출은 하드코딩으로 구현하여 보았다.더보기#1.입력matrix=[list(map(int,input().split())) for _ in range(8)]cmd=input()#2.자료형 정의#3.동작 알고리즘'''한줄씩 가져온다 U: row -> matrix[0][c]~matrix[7][c]D: row -> matrix[7][c]~matrix[0][c]L: col -> matrix[r][0]~matrix[r][7]R: col -> matrix[r][7]~matrix[r][0]시작은 1부터 -> 그 다음 칸을 한칸씩 땡기기visited를 통해 현재 칸이 합쳐졌다면 합치지 않는다'''def move(cmd): visited=[[Fa..

문제 링크성능 요약메모리: 35176 KB, 시간: 60 ms분류구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 from collections import dequedir=((-1,0),(1,0),(0,-1),(0,1))#1.입력N,M=map(int,input().split())matrix=[list(input()) for _ in range(N)]#2.자료형 정의#빨간,파란 구슬 각각의 위치를 생각해야하므로 visited는 4차원이여야함visited=[[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]#빨간구슬,파란구슬 위치 저장for y in range(N): for x in ..

문제 링크성능 요약메모리: 223272 KB, 시간: 2508 ms분류덱, 파싱, 구현, 문자열, 자료 구조T=int(input())for _ in range(T): flag=False P=list(input()) n=int(input()) lst=input()[1:-1] if len(lst): lst=list(map(int,lst.split(','))) odd=0 start,end=0,n for p in P: if p=='R': odd+=1 elif p=='D': # 에러가 발생한 경우 if end 계속 틀렸던 이유1. 단순 print(list)로 리스트 출력 시 ..

https://www.acmicpc.net/problem/11438

문제 링크 성능 요약메모리: 115,304 KB, 시간: 9,187 ms, 코드길이: 1,210 Bytes from collections import deque # 큐 순서 정하기def bfs(x): lst=[x] queue=deque() queue.append(x) while queue: q=queue.popleft() for nq in child[q]: lst.append(nq) queue.append(nq) return lst def cal_depth(): queue=deque() queue.append(1) d[1]=0 while queue: x=queu..