신장 트리 (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가 동작하는..
신장 트리 (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..
