흙금이네 블로그

지난 12월 20일 수료식이 있었고, 12월 30일 부로 SSAFY 7기의 모든 일정이 끝났습니다. 이번에는 싸피 2학기까지 모두 마치고 수료한 후기를 작성해보려 합니다. 성과 1일 1알고리즘 프로젝트를 진행하며 바쁜 와중에도 매일 한 문제씩은 알고리즘 문제를 풀려고 노력했습니다. 바쁘다는 핑계로 쉬운 실버 문제를 위주로 풀었더니 감이 많이 떨어진 것 같습니다. 요즘에는 다시 골드 이상 난이도의 문제에 도전해보고 있습니다. 1일 1커밋 깃허브에 매일 푼 알고리즘 문제 코드를 올렸습니다. 이제는 잔디 강박이 생길 정도입니다. BOJ, 프로그래머스 각각 600문제, 100문제 이상 해결 주로 BOJ는 파이썬, 프로그래머스는 자바스크립트로 문제를 풀고 있습니다. 프로젝트 우수 2학기에는 공통, 특화, 자율 이..

아이디어 희소 배열을 이용하여 쿼리 수행 시간을 단축한다. 풀이 희소 배열 f의 첫 행에 입력 받은 값들을 저장하고, for문을 돌면서 동적 계획법으로 희소 배열의 행을 추가해 나간다. 희소 배열의 행 크기는 n이 범위를 넘지 않도록 19로 설정했다(2^19 = 524,288 > 500,000). 차례로 n을 1과 AND 비트 연산하여 각 자리값에 따라 희소 배열 f에서 계산된 값을 찾아 나가도록 한다. import sys input = sys.stdin.readline m = int(input()) f = [[0]+list(map(int, input().split()))] for i in range(1, 19): f.append([]) for j in range(m+1): f[-1].append(f[-..

아이디어 최소 공통 조상 알고리즘을 이용해 가장 가까운 공통 조상을 알아낸다. 풀이 너비 우선 탐색 함수 bfs에서는 트리를 탐색하며 현재 노드의 깊이, 부모 노드를 저장하도록 한다. 최소 공통 조상을 찾는 함수 find는 두 노드의 깊이를 일정하게 맞춘 뒤, 공통 조상을 찾아 반환한다. 딕셔너리 memo에는 이미 조상을 찾았던 두 노드의 최소 공통 조상을 저장해두어 find 함수를 재호출하지 않도록 한다. 입력 받은 간선들을 2차원 리스트 graph에 추가한 후, 함수 bfs를 호출하여 노드 깊이와 부모 노드 정보를 저장한다. M개의 두 노드에 대한 최소 공통 조상을 찾아 출력하고, 메모이제이션을 통해 실행 시간을 단축한다. import sys input = sys.stdin.readline def b..