기록하고 싶은 것들

최소 공통 조상: 기초 문제BOJ ‘LCA’ 문제 최소 공통 조상최소 공통 조상 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 기본적인 최소 공통 조상 알고리즘모든 노드에 대한 깊이를 계산최소 공통 조상을 찾을 두 노드 확인 먼저 두 노드의 깊이가 동일하도록 거슬러 올라가기이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라가기모든 LCA(a,b) 연산에 대하여 2번의 과정 반복 LCA 알고리즘import sys sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정 n = int(input()) parent = [0] * (n + 1) # 부모 노드 정보 d = [0] * (n + 1) # 각 노드까지의 ..

데이터가 업데이트가 가능한 상황에서의 구간 합 문제BOJ 구간 합 구하기 문제 바이너리 인덱스 트리(Binary Indexed Tree)바이너리 인덱스 트리는 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있는 자료구조펜윅 트리(fenwick tree)라고도 함 0이 아닌 마지막 비트를 찾는 방법특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K&-K를 계산하면 됌 b = 8 for i in range(n+1): print(i, "의 마지막 비트:", (i & -i)) 바이너리 인덱스 트리: 트리 구조 만들기트리 구조 만들기: 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수 바이너리 인덱스 트리: 업데이트(Update)특정 값을 변경할 때: 0이 아닌 마지막 비트만큼..

음수 간선이 포함된 상황에서의 최단 거리 문제 BOJ ‘타임머신’문제음수 간선이 순환이 포함된다면 최단 거리가 음의 무한인 노드 발생 벨만 포드 최단 경로 알고리즘음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류1) 모든 간선이 양수인 경우2) 음수 간선이 있는 경우1) 음수 간선 순환은 없는 경우2) 음수 간선 순환이 있는 경우벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용또한 음수 간선의 순환을 감지 가능벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느림 동작 원리출발 노드 설정최단 거리 테이블 초기화다음의 과정을 N-1번 반복전체 간선 E개를 하나씩 확인각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신만약 음수 간선 순환이 발..

트리트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조[트리 관련 용어]루트 노드: 부모가 없는 최상위 노드단말 노드: 자식이 없는 노드크기: 트리에 포함된 모든 노드의 개수깊이: 루트 노드부터의 거리높이: 깊이 중 최대값차수: 각 노드의 간선 개수기본적으로 트리의 크기가 N일 때, 전체 간선의 개수 N-1개 이진 탐색 트리(Binary Search Tree)이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조 일종이진 탐색 트리의 특징: 왼쪽 자식 노드< 부모 노드 < 오른쪽 자식 노드부모 노드보다 왼쪽 자식 노드가 작음부모 노드보다 오른쪽 자식 노드가 큼 트리의 순회(Tree Traversal)트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을..

우선순위 큐우선순위 큐는 데이터를 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우자료구조추출되는 데이터스택가장 나중에 삽입 데이터큐가장 먼저 삽입 데이터우선순위 큐가장 우선순위가 높은 데이터우선순위 큐를 구현하는 방법1) 단순히 리스트를 이용하여 구현2) 힙(heap)을 이용하여 구현데이터의 개수가 N일때, 구현 방식에 따라서 시간 복잡도를 비교한 내용우선순위 큐 구현 방식삽입 시간삭제 시간리스트O(1)O(N)힙(Heap)O(logN)O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬)이 경우 시간 복잡도..

개발형 코딩 테스트정해진 목적에 따라서 동작하는 완성된 프로그램 개발을 요구하는 코딩 테스트 유형일부 기업은 해커톤을 통해 채용 진행해커톤이란 단기간에 아이디어를 제품화하는 프로젝트 이벤트대개 1-2일 진행, 대회 형식을 빌려 해커톤이 끝나면 만든 프로그램을 시연하고 발표한 다음 채점 진행 개발형 코딩 테스트는 분야에 따라 상세 요구사항이 다를 수 있음하지만 분야에 상관없이 꼭 알아야 하는 개념과 도구에 대하여 학습할 필요가 있음서버, 클라이언트,JSON, REST API… 서버와 클라이언트클라이언트가 요청을 보내면 서버가 응답 클라이언트(Client) = 고객서버로 요청(Request)을 보내고 응답(Response)이 도착할 때까지 기다립니다서버로부터 응답을 받은 뒤에는 서버의 응답을 화면에 출력ex..

소수(Prime Number)소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판벼래야하는 문제 자주 출제 약수의 성질모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸예를 들어 16의 약수는 1,2,4,8,16 이 때 2 X 8 =16은 8 X 2 =16과 대칭따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수까지만 확인하면 됌ex) 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것을 의미 소수판별: 개선된 알고리즘import math # 소수 판별 함수 def is_prime_number(x): # 2부터 x의 제곱근까지의 모든 수를 확인하며 for i in range..

서로소 집합서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미 서로소 집합 자료구조서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조서로소 집합 자료구조는 두 종류의 연산 지원합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 함 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정합집합 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인1) A와 B의 루트 노드 A’, B’를 각각 찾기2) A’를 B’의 부모 노드로 설정모든 합집합 연산을 처리할 때까지 1번의 과..

최단 경로 문제최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘 다양한 문제 상황한 지점에서 다른 한 지점 까지의 최단 경로한 지점에서 다른 모든 지점 까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현지점 간 연결 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하기다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 알고리즘 동작과정출발 노드 설정최단 거리 테이블을 초기화방문하지 않은 노드 ..

다이나믹 프로그래밍메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 방법이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함다이나믹 프로그램잉의 구현은 탑다운 & 보텀업으로 구성다이나믹 프로그래밍은 동적계획법이라고도 부름 다이나믹 프로그래밍의 조건최적 부분 구조(Optimal Substructure)큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 더 큰 문제 해결 가능 중복되는 부분 문제(Overlapping Subproblem)동일한 작은 문제를 반복적으로 해결 가능 피보나치 수열피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산 가능1,1,2,3,5,8,13,21,34,55,89, …점화식: 인접한 항들 사이의 관계식배열이나 리스트를 이용해 수열 표현 ..