신장 트리 (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가 동작하는..
함수적 종속(Functional Dependency) 관계형 데이터베이스에서의 정규화 과정을 살펴보기 전, 함수적 종속 개념에 대해 먼저 알아보자. 릴레이션 R(테이블)에서 X와 Y를 R의 속성의 부분집합이라고 할 때, X의 값 각각에 대해 Y의 값이 오직 하나로 결정 될 때 Y는 X에 종속된다고 한다. 즉, 테이블의 한 필드값 집합(X)이 다른 필드값 집합(Y)을 결정하는 관계를 말한다. 여기서 "결정한다"는 의미는 무엇일까? "알 수 있다", "영향을 미친다" 라고 받아들이면 쉽다. "X가 Y을 결정한다"라는 뜻은 X의 값을 알면 Y의 값을 알 수 있고, X와 Y는 관계가 있어 X의 값에 의해 Y의 값이 달라진다는 것을 의미한다. 이런 함수적 종속 관계를 화살표를 통해 X→Y라고 표현하고 X를 결정자..
책: wikibook.co.kr/rlrev/ 파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능 강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 wikibook.co.kr 참고: dnddnjs.gitbooks.io/rl/content/ ※본문 내용은 위의 자료들을 요약·정리한 것이 포함되어있습니다. 벨만 기대 방정식 벨만 기대 방정식은 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 식으로 나타낸 것이다. 벨만 기대 방정식은 가치함수식에서 유도된 것인데 과정은 다음과 같다. 우선, 가치함수의 정의에서 반환값 Gt를 풀어서 표기한 것..
wikibook.co.kr/rlrev/ 파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능 강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 wikibook.co.kr ※본문 내용은 위의 책들을 요약·정리한 것이 포함되어있습니다. 저번 포스팅에서 MDP를 통해 순차적 행동 결정 문제를 수학적으로 정의했다. 이제 에이전트가 최적 정책을 찾아 문제를 해결하면 되는데, 에이전트가 특정 상태에서 행동을 선택하는 기준이 되는 것이 가치함수이다. 가치함수(상태 가치함수) 강화 학습에서 학습의 기준이 되는 것이 보상이라고 전 포스팅에서 언급했었다. 보상을 ..
파일 시스템의 정의는 아래와 같다. "운영체제가 파일,디렉토리를 효율적/구조적으로 관리하기 위한 트리구조 시스템을 총칭"_ 정보통신기술용어해설 즉, 컴퓨터에서 자료들을 쉽게 발견하고 관리할 수 있게 하는 구조적인 시스템을 말하는데 Linux의 파일시스템 구조에 대해서 살펴보자. 사실 이 게시물을 작성하게 된 이유는 루트 디렉토리와 홈 디렉토리의 차이를 알아보다가 공부한 내용을 정리한건데 이 차이만 궁금한 사람은 여기로! Linux의 파일 시스템과 구조 - 트리구조 - FSSTND(linux File System STaNDard: 리눅스 파일 시스템 표준안) 준수하는 것 권장 - 보통 FHS(Filesystem Hierarchy Standard) 표준 파일 시스템 계층 사용 (FHS가 리눅스의 주 디렉토리..
리눅스 명령어 형식 명령어는 소문자 명령어와 옵션, 인수 사이에는 한 개 이상의 공백 있어야 함 옵션 두개 이상 사용시 '-la' 처럼 순서상관없이 글자 붙여서 추가 입력 내가 보려고 만든 인덱스식 리눅스 명령어 모음 새로운 명령어 사용할 때마다 추가할 예정 * 특정 명령어의 어떤 옵션있는지 궁금하면 '명령어 --help'로 옵션 검색 인덱스 (링크 걸어 놓았음) 터미널창 관련 clear exit 디렉토리 확인 및 생성, 삭제 pwd ls mkdir rmdir 디렉토리 이동 cd 파일 관련 cat mv cp rm ./ 터미널창 관련 clear 터미널 창의 내용을 모두 지움 exit 터미널 창을 종료 디렉토리 확인 및 생성, 삭제 pwd (Print Working Directory) 현재 작업 중인 디렉토..
