개발새발

최소 스패닝 트리(Minimum Spanning Tree, MST)를 찾는 문제는 크루스칼(Kruskal) 알고리즘이나 프림(Prim) 알고리즘을 사용하여 해결할 수 있습니다. 크루스칼 알고리즘과 다익스트라 알고리즘 모두 그래프의 모든 정점들을 연결하는 최소 비용의 트리를 찾는 데 사용됩니다.크루스칼 알고리즘은 간선을 가중치에 따라 정렬하고, 가장 작은 간선부터 시작하여 사이클을 만들지 않는 한 트리에 추가하는 방식으로 동작합니다.모든 간선을 가중치 순으로 정렬합니다.각 간선을 순서대로 확인하면서, 해당 간선을 추가해도 사이클이 생기지 않으면 트리에 추가합니다.사이클이 생기지 않는다는 것을 확인하기 위해서 Union-Find 자료구조를 사용합니다.*Union-Find 자료구조는 서로소 집합(Disjoin..

다익스트라 알고리즘은 그래프 이론에서 주어진 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘으로, 가중치가 있는 그래프에서 최단 경로를 찾는 문제를 해결하는 데 사용됩니다. (그래프 이론 + dp)다익스트라 알고리즘 개요다익스트라 알고리즘은 다음과 같은 단계로 동작합니다:출발 노드 선택: 시작 노드를 선택하고, 시작 노드의 최단 경로를 0으로 초기화합니다.우선순위 큐 활용: 출발 노드부터 갈 수 있는 모든 경로를 우선순위 큐(힙)에 넣습니다. 시작 노드의 최단 경로가 0이므로 시작 노드를 우선순위 큐에 넣습니다.최단 경로 갱신: 우선순위 큐에서 최소 비용의 노드를 꺼내서 해당 노드에서 갈 수 있는 모든 노드들의 최단 경로를 갱신합니다. 이 때, 기존 경로보다 더 짧은 경로를 발견하면 해당 ..

코딩 테스트에서 자주 출제되는 주요 알고리즘 종류와 각 알고리즘의 특징, 그리고 어떤 문제 유형에 어떤 알고리즘이 적합한지에 대해 알아보겠습니다.1. 그리디 알고리즘 (Greedy Algorithm)특징: 각 단계에서 가장 좋아 보이는 선택을 하며 최종적인 해답에 도달하는 방법.적용 예시: 최적의 해를 구하는 것이 중요하고, 각 선택이 서로 간섭이 없을 때 (즉, 한 선택이 다른 선택에 영향을 미치지 않을 때).2. 분할 정복 (Divide and Conquer)특징: 문제를 더 작은 문제로 나누어 해결한 후, 결과를 합쳐서 전체 문제의 해를 구함.적용 예시: 큰 문제를 작은 문제로 분할하여 해결할 수 있는 경우, 주로 재귀적으로 구현됨.3. 동적 계획법 (Dynamic Programming)특징: 이전..

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 특정 조건을 만족하는 부분 배열이나 부분 집합을 찾기 위해 두 개의 포인터를 사용하는 기법입니다. 이 기법은 주로 배열을 효율적으로 탐색하면서 O(N^2) 이상의 시간 복잡도를 O(N)으로 줄일 때 사용됩니다.투 포인터 기법의 기본 원리포인터 초기화:배열의 시작 위치에 두 개의 포인터를 설정합니다. 일반적으로 하나는 start 포인터, 다른 하나는 end 포인터입니다.포인터 이동:조건을 만족할 때까지 두 포인터를 이동시킵니다.각 포인터의 이동은 문제의 조건에 따라 다릅니다. 예를 들어, 부분합이 일정 값을 넘는 경우 start 포인터를 이동시키고, 그렇지 않으면 end 포인터를 이동시킵니다.조건 만족 확인:두 포인터가 가리키는 구간이나 값..

자주 헷갈리는 SQL 문법들을 정리해봤다. (내가 기억하기 위해 쓰는 글ㅎㅎ)소숫점 반올림 함수 Round()group by에서 where 조건을 사용하기 위해서는 having count(*)date의 경우 date_format(칼럼, ‘%y-%m-%d) 또는 year(칼럼) = ‘2024’ order by 후 상위 n 개 출력 limit n문자열자르기 left(칼럼, 숫자)중복제거 distinct 중복의 경우 select distinct 칼럼1, 칼럼2, .. 을 모두 만족해야 함 예시) Post 라는 테이블에 Comment를 남긴 사람의 수를 구하는 문제다.여기에서 Post별 Comment를 남긴 distinct User Id의 갯수를 구하는 문제라서 우선 Post_id로 조인한 후,해당 Post마다..

1. sort() vs sorted()list = [2, 3, 1]list.sort()print(list) #[1,2,3]list2 = [2, 3, 1]b = sorted(list)print(b) #[1, 2, 3]리스트.sort() :: 원본의 값 직접 수정 VS sorted(리스트) :: 새로운 리스트 값 반환역순 정렬을 위해서는 sort(reverse=True) / sorted(reverese=True)튜플 정렬첫번째 원소 오름차순 a.sort(key=lambda x:x[0])첫번째 원소 내림차순 a.sort(key=lambda x:-x[0]) or a.sort(key=lambda x:x[0], reverse=true)두번째 원소 오름차순 a.sort(key=lambda x:x[1])두번째 원소..

여러 사이트와 블로그, 카페, 백준 추천 문제를 참고하여 코테에 최적화된 문제 리스트를 정리해봤다기본 문제는 문제를 보자마자 풀수 있어야 하고, 그 외 문제들은 고민 시간이 1시간을 넘어간다면 해설을 보길 추천한다너무 축약된 코드는 제외하고 설명이 있는 코드를 보면서 문제 풀이 로직을 익혀야한다. ex) 이 문제에서는 왜 이런 공식(알고리즘)을 써서 풀었는지 등등 풀었던 문제도 여러 가지 풀이가 있을 수 있기 때문에 다른 풀이를 확인해보는 것도 좋다@.@ 1. 기본문제2501, 3460, 10818, 2460, 10870, 2309, 2693, 1978, 1292, 2581입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 1..

내가 계속 까먹어서 기록해 놓는 파이썬 소숫점 표현방법!알고리즘 문제를 풀다보면 대부분 반올림을 써야하는데 익히 알고 있는 round를 쉽게 쓴다.하지만 round에는 큰 허점이 있어서 다른 방법을 사용해야 하는데 아직은 사용할 때마다 긴가민가 하다... 1. 반올림, 올림, 내림일반적인 반올림에는 round를 사용한다.올림과 내림의 경우 ceil(올림), floor(내림)을 사용한다.round(1.234, 2) # 반올림, 소숫점 2번째 자리까지 표시(1.23)import mathmath.ceil # 올림math.floor # 내림 2. round 함수의 문제점하지만 round 함수의 경우 자릿수를 표시해주는 '0'에 대해서는 문제가 발생한다.print(round(1.000, 2)) # 1.00이..