신장 트리 (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가 동작하는..
강화학습 코드 짜면서 함수 하나 쓰고 싶은데 사용하고 싶은 모듈이 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..
파일 시스템의 정의는 아래와 같다. "운영체제가 파일,디렉토리를 효율적/구조적으로 관리하기 위한 트리구조 시스템을 총칭"_ 정보통신기술용어해설 즉, 컴퓨터에서 자료들을 쉽게 발견하고 관리할 수 있게 하는 구조적인 시스템을 말하는데 Linux의 파일시스템 구조에 대해서 살펴보자. 사실 이 게시물을 작성하게 된 이유는 루트 디렉토리와 홈 디렉토리의 차이를 알아보다가 공부한 내용을 정리한건데 이 차이만 궁금한 사람은 여기로! Linux의 파일 시스템과 구조 - 트리구조 - FSSTND(linux File System STaNDard: 리눅스 파일 시스템 표준안) 준수하는 것 권장 - 보통 FHS(Filesystem Hierarchy Standard) 표준 파일 시스템 계층 사용 (FHS가 리눅스의 주 디렉토리..
오류 메시지 MySQL을 설치하는 중에 네트워크 설정시 port 설정에서 오류가 발생했다. 오류 메세지는 아래와 같았다. "the specified port already in use" 원인 MySQL은 기본 설정으로 127.0.0.1주소의 3306번의 포트로 접속하게 되어있는데, 이전에 사용하던 MySQL이 남아있어서 그렇다. 해결 이전 MySQL이 사용하고 있는 3306포트 삭제! 해결 과정 💡3306 포트 확인 포트 확인하는 방법은 2가지가 있는데 하나는 CMD에서 명령어로 확인할 수 있고 두 번째는 리소스 모니터로 확인할 수 있다. 두 가지 방법 모두 해보겠다. 1. CMD에서 natstat 명령어 netstat -ano //네트워크 관련 정보 확인 netstat는 network state의 약어..
뷰 라우터란? 페이지 간에 이동하는 기능을 구현할 때 사용하는 뷰 라이브러리이다. 클라이언트가 요청하는 URI에 따라 특정 컴포넌트를 동적으로 불러와 페이지를 구성한다. 이번 포스트에서는 뷰 라우터를 설치하고, 라우터 설계, 사용하는 방법을 설명할거다. Vue3 버전 프로젝트라는 것을 명시한다! [version] vue: 3.2.33 / vue-cli: 5.0.4 뷰라우터 설치 npm i vue-router@next --save vue-cli를 통해 뷰 프로젝트를 생성한 후, 위의 코드대로 npm을 통해서 뷰라우터를 설치해준다. 뷰라우터 설치 확인 설치가 완료되면 뷰 프로젝트 최상단에 경로에 있는 package.json 파일에서 dependencies에 vue-router가 추가된 것을 확인한다. 현재 ..
책: wikibook.co.kr/rlrev/ 파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능 강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 wikibook.co.kr 참고: dnddnjs.gitbooks.io/rl/content/ ※본문 내용은 위의 자료들을 요약·정리한 것이 포함되어있습니다. 벨만 기대 방정식 벨만 기대 방정식은 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 식으로 나타낸 것이다. 벨만 기대 방정식은 가치함수식에서 유도된 것인데 과정은 다음과 같다. 우선, 가치함수의 정의에서 반환값 Gt를 풀어서 표기한 것..
wikibook.co.kr/rlrev/ 파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능 강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 wikibook.co.kr ※본문 내용은 위의 책들을 요약·정리한 것이 포함되어있습니다. 저번 포스팅에서 MDP를 통해 순차적 행동 결정 문제를 수학적으로 정의했다. 이제 에이전트가 최적 정책을 찾아 문제를 해결하면 되는데, 에이전트가 특정 상태에서 행동을 선택하는 기준이 되는 것이 가치함수이다. 가치함수(상태 가치함수) 강화 학습에서 학습의 기준이 되는 것이 보상이라고 전 포스팅에서 언급했었다. 보상을 ..
