신장 트리 (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가 동작하는..
파일 시스템의 정의는 아래와 같다. "운영체제가 파일,디렉토리를 효율적/구조적으로 관리하기 위한 트리구조 시스템을 총칭"_ 정보통신기술용어해설 즉, 컴퓨터에서 자료들을 쉽게 발견하고 관리할 수 있게 하는 구조적인 시스템을 말하는데 Linux의 파일시스템 구조에 대해서 살펴보자. 사실 이 게시물을 작성하게 된 이유는 루트 디렉토리와 홈 디렉토리의 차이를 알아보다가 공부한 내용을 정리한건데 이 차이만 궁금한 사람은 여기로! Linux의 파일 시스템과 구조 - 트리구조 - FSSTND(linux File System STaNDard: 리눅스 파일 시스템 표준안) 준수하는 것 권장 - 보통 FHS(Filesystem Hierarchy Standard) 표준 파일 시스템 계층 사용 (FHS가 리눅스의 주 디렉토리..
책: wikibook.co.kr/rlrev/ 파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능 강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 wikibook.co.kr 참고: dnddnjs.gitbooks.io/rl/content/ ※본문 내용은 위의 자료들을 요약·정리한 것이 포함되어있습니다. 벨만 기대 방정식 벨만 기대 방정식은 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 식으로 나타낸 것이다. 벨만 기대 방정식은 가치함수식에서 유도된 것인데 과정은 다음과 같다. 우선, 가치함수의 정의에서 반환값 Gt를 풀어서 표기한 것..
책: wikibook.co.kr/rlrev/ 파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능 강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 wikibook.co.kr 참고: dnddnjs.gitbooks.io/rl/content/ ※본문 내용은 위의 자료들을 요약·정리한 것이 포함되어있습니다. 강화학습의 예측과 제어 이전 포스팅에서 DP에 대해 설명했는데 DP는 벨만 방정식을 통해 가치함수와 정책을 업데이트시켜 최적의 정책을 찾아가는 방식이었다. 이 방법은 MDP의 모든 정보를 알고 있어야 풀 수 있다. 특히 환경의 모델이라고 부르는 "..
강화학습 코드 짜면서 함수 하나 쓰고 싶은데 사용하고 싶은 모듈이 pytorch에 있고, pytorch가 tensorflow 버전 낮추라 하고, 낮춘 tensorflow가 python 버전 낮추라 하고... 환경 잡기의 무한 굴레.... 어쨌든 python을 다운그레이드해야 한다. 나는 python3.8에서 python3.7로 다운그레이드했다. 찾아보니 사실 매우 간단하게 다운그레이드할 수 있었다. conda install python='원하는버전' # 3.7로 변경할 때 # conda install python=3.7 *혹시 failed with initial frozen solve. Retrying with flexible solve. 라는 문구가 뜨면서 진행이 안된다면 https://dana-stu..
wikibook.co.kr/rlrev/ 파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능 강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 wikibook.co.kr ※본문 내용은 위의 책들을 요약·정리한 것이 포함되어있습니다. 저번 포스팅에서 MDP를 통해 순차적 행동 결정 문제를 수학적으로 정의했다. 이제 에이전트가 최적 정책을 찾아 문제를 해결하면 되는데, 에이전트가 특정 상태에서 행동을 선택하는 기준이 되는 것이 가치함수이다. 가치함수(상태 가치함수) 강화 학습에서 학습의 기준이 되는 것이 보상이라고 전 포스팅에서 언급했었다. 보상을 ..
