이것도 알아야 하네?

순서가 정해져 있는 여러 일들을 순서에 맞게 나열할 떄 사용할 수 있는 알고리즘이다. 즉, 선후 관계가 정의된 Graph에서 선후 관계에 따라 정렬 하기위해 위상 정렬을 이용한다. 이 때, Graph는 반드시 비순환 방향 그래프여야 한다. 선수 과목이 대표적인 예시다. 특정 수강과목에 먼저 수강해야하는 과목이 있다면 해당 과목부터 수강해야 한다. 이 경우, 위상 정렬을 통해 올바른 수강 순서 중 하나를 찾아낼 수 있다. 위상 정렬 동작 진입 간선 수는 Node에 들어오는 간선 수로, 해당 Node 전에 방문해야하는 다른 Node의 수를 의미한다. 진입 간선 수가 0인 Node와 이와 연결된 모든 (진입, 진출)간선 삭제 남아있는 그래프의 진입 간선 수를 갱신 그래프에 모든 Node가 없어질 때까지 1,2..

처음에 문제를 봤을 때, 선수과목 문제처럼 일의 순서가 존재할 때 순서에 맞게 정렬하는 문제해결법인 '위상정렬'이 가장 먼저 떠올랐다. 때문에 그래프를 생성하고 순서에 대한 정보를 같이 저장해주면서 해당 node 보다 먼저 방문해야하는 수를 indegree에 저장해주었다. 실제로 문제상 indegree는 1이상의 값을 가질 수 없지만, 일반적으로 다 적용할 수 있게 하고 싶어서 나머지 부분도 맞춰서 코딩해주었다. 처음 시작점인 0을 queue에 넣어주고 graph에 저장된 값을 이용하여 연결되어 갈 수 있는 node를 찾아 queue에 다시 집어넣는다. queue에 들어갈 수 있는 node는 우선 방문 조건이 없는 node로 즉, 해당 node의 indegree값이 0이면 queue에 넣는다. queue..

처음에는 최적화로 DP를 활용하는 문제인가 고민해봤지만, DP를 이용하여 구간을 구하는 쉬운 방법이 떠오르지 않아 노선을 변경했다. 한 번 훑으면서 조건에 맞는 구간을 출력한다. 우선 코드 상으로 left는 구간의 시작점을 right는 구간의 끝점을 나타낸다. while()을 통해 right는 한 번 훑으면서 새로운 보석을 발견했을 때, contains라는 dict에 값을 저장한다. contain이 기존에 구한 unique 보석의 개수를 모두 충족했을 때부터 left를 변경한다. 만약 이미 한 개 이상 보석이 존재할 때 해당 구간은 여벌의 보석을 소유한 것이므로 오른쪽으로 이동하며 구간에서 제외한다. def solution(gems): left = 0; right = 0 targets = set(gems..

다익스트라 알고리즘 개념 다익스트라 알고리즘 또는 데이크스트라 알고리즘은 그래프에서 노드(Node) 간의 최단 경로를 찾는 알고리즘 중 하나로, 시작 노드(Node)가 주어졌을 때 해당 시작점으로부터 다른 모든 노드(Node)까지의 최단 경로 찾습니다. 해당 알고리즘은 도로 교통망 및 라우팅 프로토콜 등에서 많이 활용되고 있습니다. 예를 들어, 그래프의 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 다익스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있습니다. 다익스트라 동작 소스(Source)는 시작 노드(Node)이며, dist[]를 시작 노드(Node)와 시작 노드(Node)를 포함한 모든 노드까지의 거리로 정의합니다. dist[]에서는 시작..

csv 파일이란? csv 파일이란 comma separated values 의 약자로 데이터를 저장하는 파일 형식 중 하나입니다. 이름에서 예측할 수 있듯이 record에 저장되는 값들이 ',(comma)'를 이용하여 나열되어 있습니다. csv파일 읽기 csv파일도 파일형식이기 때문에 (1) open() 구문을 사용하여 일반 파일처럼 읽고 쓸 수 있고, 추가로 Python에서는 (2) csv 파일을 처리할 수 있는 기능을 가진 모듈을 built-in으로 제공하기 때문에 해당 모듈을 사용하여 더욱 쉽고 직관적으로 csv 파일을 조작할 수 있습니다. // test.csv 내용 a,b,c 1,2,3 4,5,6 (1) open() 사용하기 f = open(file_name) ... f.close() 파일을 읽을..

취업했을 당시에 회사를 다니더라도 나 == 회사가 되지 않도록 1년에 1자격증을 다짐했었고, 올해의 도전은 회사에서 하는 일과 관련있는 정보처리기사를 도전하였습니다. '코로나 시대'라는 불확실한 상황에서 시험을 아예 못칠 뻔도 했지만, 운이 좋게도 잠깐 좋았졌던 때를 틈타 취득할 수 있었습니다. 늦었지만, 2020년도에 시험을 본 경험으로, 정보처리기사에 대한 소개 및 사용한 교재를 포함한 공부 방법과 준비 기간을 공유하고자 후기를 작성합니다 정보처리기사 정보처리기사는 코로나 전에는 일년에 4번의 시험이 존재하며 다른 기사 시험과 동일하게 필기와 실기를 모두 합격해야지만 자격증을 취득할 수 있습니다. 동일 회차를 가정했을 떄 필기와 실기는 1달 정도의 term이 존재하고, 실기를 보기 위해서는 응시 자격..