신장 트리 (Spanning Tree) 무방향 그래프의 최소 연결 부분 그래프를 말한다. 즉, N개의 정점을 가지는 그래프 중 모든 정점을 포함하면서 최소 간선의 수인 N-1개의 간선으로 연결된 부분 그래프를 뜻한다. 특정 그래프에서 최소 간선 수인 N-1개의 간선을 가지고 있는 그래프는 트리 형태를 이룰 수 밖에 없어 신장 "트리"라고 한다. 🔹정점 수: N 🔹간선 수: N-1 🔹즉, 그래프 내 모든 정점을 포함하는 트리 (사이클 존재 X) 위의 그림과 같이 하나의 그래프에서 신장 트리는 여러개가 존재할 수 있다. 이때 하나의 그래프에서 생성될 수 있는 신장 트리 중 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 한다. MST를 구할 수 있는 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다...
28354번: 링크 컷 토마토 첫째 줄에 토마토의 개수 $N$, $0$일에 연결되어 있는 토마토 쌍의 수 $M$, $0$일에 익은 토마토의 수 $K$, 연결 상태가 변하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200\,000;$ $0 \leq www.acmicpc.net 문제 풀이 내 첫 플래티넘 문제였다. 알고리즘은 제대로 구성해서 작성한 것 같은데, 계속 시간 초과가 나서 애먹었던 기억이 있다. 시간을 단축시키고자 BFS 방문 시 필요 없는 방문이 발생하지 않도록 조건도 체크했는데 시간 초과가 나서 며칠 동안 붙잡고 있었다. 결론적으로 탐색이 더 효율적인 자료구조로 변경하니 통과되었다. 처음엔 그래프를 ArrayList로 구현했었는데, 그래프 안에 특정 ..
8월 11일에 소프티어 역량 진단 시험에 응시했다. 이번이 두 번째 응시였는데, 지난 6차 시험보다 난이도가 쉬워진 것 같았다. 1시간 정도 여유시간이 생겨 제출 전에 시간복잡도를 생각해 보거나 엣지 케이스 넣어보며 체크하고 제출할 수 있었다. 일단 Softeer 정기 역량 진단 HSAT(Hyundai SW Aptitude Test)는 현대차그룹의 SW 플랫폼인 Softeer에서 주최하는 시험으로, 이 시험에서 인증서를 취득하면 "현대자동차, 기아, 현대모비스, 현대오토에버, 현대차증권, 현대엔지비" 기업의 SW 분야 지원 시 코딩테스트 면제 혜택을 받을 수 있다. 💡 지원시 유의사항 - 현대자동차 : 우대사항이 명시된 공고에 자격증을 입력한 경우에 한하여 면제 가능 - 현대모비스 : 지원자 이력서 작성..
가비지 컬렉션 (Garbage Collection) java의 Garbage Collection(GC) 이란 메모리 관리를 자동화하는 메커니즘으로, 프로그래머가 명시적으로 메모리 할당과 해제를 다루지 않고도 효율적으로 메모리를 관리할 수 있도록 JVM의 GC가 동작한다. C와 C++에선 free()나 delete()와 같은 함수를 통해 명시적으로 직접 메모리를 해제해주어야 하지만, 자바에선 GC가 메모리 관리를 대신 수행해 주기 때문에 한정된 메모리를 효율적으로 사용할 수 있고, 메모리 누수가 발생하는 것을 방지해 준다. ◽한정된 메모리를 효율적으로 사용할 수 있게 해 줌 ◽개발자가 메모리 관리에 신경 쓰지 않고 개발에만 집중할 수 있음 ◾개발자가 메모리 해제 시점을 정확히 알 수 없음 ◾GC가 동작하는..
AVL 트리 AVL 트리 (Adelson-Velsky and Landis tree)는 이진 탐색 트리가 데이터 삽입 순서로 인해 선형적인 형태의 트리가 되는 것을 방지하고자 스스로 균형을 잡는 이진 탐색 트리를 말한다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다. (균형 이진 트리의 일종) 데이터 삽입, 삭제시 균형이 항상 맞도록 트리 일부를 왼쪽 혹은 오른쪽으로 회전시킨다 (리밸런싱). 🔹가장 처음 나온 자가 균형 이진 트리 🔹red-black tree보다 균형은 훨씬 잘 잡힘 🔹red-black tree보다 삽입, 삭제가 느림 🔹서브 트리 높이 차이가 1보다 커지면 회전(리밸런싱) 통해 차이 줄임 💡탐색, 삽입, 삭제 시간 복잡도: O(logN) Balance Factor..
그래프 (Graph) 그래프는 정점과 간선으로 이루어진 비선형 자료 구조를 말한다. 🔹정점(V) (vertex) - 그래프 내의 하나의 개별적 요소 🔹간선(E) (edge) - 정점과 정점 사이를 연결하는 선 (흐름, 관계 표현) 🔹가중치(W) (weight) - 간선과 정점 사이에 드는 비용 🔹차수 (degree) - 정 정점에 연결된 간선의 수 ◽out-degree: 다른 정점으로 나가는 간선 (수) ◽in-degree: 특정 정점으로 들어오는 간선 (수) ◽무방향 그래프에선 하나의 간선이 두 정점에 인접하므로 간선 수의 두 배 💡 비선형 자료 구조 비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다. 일반적으로 트리나 그래프를 말한다. 방향 그래프(Diredted Gr..
조인 두 개 이상의 테이블을 묶어 하나의 결과물을 만드는 것을 말한다. 비관계형 데이터베이스(MongoDB)에서도 lookup이란 쿼리로 이를 처리할 수 있는데, 관계형 데이터베이스보다 성능이 떨어지기 때문에 되도록 사용하지 않는다. 조인(논리적 조인)의 종류 논리적 조인이란 사용자가 SQL문을 이용해 원하는 데이터 결합 방식을 기술하는 것을 의미한다. Inner Join (내부 조인): 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기 Outer Join Left Join (왼쪽 조인): 왼쪽 테이블의 모든 행이 결과 테이블에 표기 Right Join (오른쪽 조인): 오른쪽 테이블의 모든 행이 결과 테이블에 표기 Full Outer Join (전체 외부 조인): 조인 조건에..
함수적 종속(Functional Dependency) 관계형 데이터베이스에서의 정규화 과정을 살펴보기 전, 함수적 종속 개념에 대해 먼저 알아보자. 릴레이션 R(테이블)에서 X와 Y를 R의 속성의 부분집합이라고 할 때, X의 값 각각에 대해 Y의 값이 오직 하나로 결정 될 때 Y는 X에 종속된다고 한다. 즉, 테이블의 한 필드값 집합(X)이 다른 필드값 집합(Y)을 결정하는 관계를 말한다. 여기서 "결정한다"는 의미는 무엇일까? "알 수 있다", "영향을 미친다" 라고 받아들이면 쉽다. "X가 Y을 결정한다"라는 뜻은 X의 값을 알면 Y의 값을 알 수 있고, X와 Y는 관계가 있어 X의 값에 의해 Y의 값이 달라진다는 것을 의미한다. 이런 함수적 종속 관계를 화살표를 통해 X→Y라고 표현하고 X를 결정자..
HTTP HTTP(Hyper Text Transfer Protocol)는 클라이언트와 서버 간 정보를 주고받기 위한 통신 규약이다. 애플리케이션 계층에서 동작하고 웹 서비스 통신에 사용된다. HTTP/1.0부터 HTTP/3까지 발전해 왔다. 무상태성(stateless) - HTTP는 요청에 대한 상태를 가지지 않음 - 각 요청은 독립적 → 요청 간의 서로 영향 주고받지 않음 - 상태(로그인 정보 등)를 사용하기 위해선 세선이나 쿠키 사용 비연결성(Connectionless) - 요청을 주고받을 때만 연결을 유지하고 전송이 끝나면 연결 끊김 서버-클라이언트 구조 - 일반적으로 클라이언트는 웹브라우저 - 서버는 요청 대상인 서버 컴퓨터 의미 📜HTTP/1.0 한 연결당 하나의 요청을 처리한다. 서버로부터 정..
16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 문제 풀이 처음엔 단어목록(A)에 있는 단어들을 긴 단어부터 하나씩 문자열의 앞부분과 비교해서 일치하면 단어 길이만큼 삭제하고 다시 탐색하는 방식으로 접근했었는데, 단어목록에 software, soft 같이 단어 사이에 서브 스트링이 존재하는 경우 반례가 생기는 것 같다..(사실 정확한 문제점 발견 못함) 단어를 찾았다고 문자열에서 삭제한 후 다시 고려하지 않는 방식은 미처 고려하지 못하는 경우가 발생하는 것 같다. 따라서 DP 테이블을 이용..
