🧪Computer Science

2024 2회 정보처리기사 실기 합격 독학 후기

처음으로 자격증 취득 후기를 올려보려고 합니다 저는 항상 시험을 준비할 때 성공한 사람들의 사례를 참고하는 편인데 '대단하다 나도 이렇게 되고싶다', '이렇게 하면 되는구나' 생각하면서 동기부여도 되고, 방향을 잡을 수 있어서 좋은 습관이라고 생각합니다. 자격증 인증으로 글을 시작하죠!    베이스 지식이 어떻게 돼?라는 질문에 먼저 답변드리겠습니다. 서울 4년제 대학 소프트웨어 전공, 경영 복수전공으로 졸업하였습니다.즉 베이스가 없지 않고 처음 기본서를 보았을 때 완벽하게 알진 못하지만 어디선가 본적있다! 정도의 수준에서 시작하였습니다. 대학 정규 과정 성실히 들은 보통의 졸업생 정도라고 보시면 될 것같습니다.  얼마나 공부했어?빡세지 않게 4주 잡고 공부했습니다.이틀, 일주일 공부했다는 천재분들도 가..

[알고리즘] 최소 스패닝 트리 알고리즘 | 크루스칼/프림 알고리즘

~목차~ 스패닝 트리란? 크루스칼 알고리즘 프림 알고리즘 (최소) 스패닝 트리란? 최소 스패닝 트리 알고리즘을 설명하기 이전에 스패닝 트리(Spanning Tree)란 무엇인가 알아보도록 하겠습니다. 스패닝 트리는 어떤 그래프에서 모든 노드를 연결하며 사이클이 없는 부분 그래프를 의미합니다 그림으로 이해해보겠습니다 왼쪽과 같은 초기 그래프가 있을 때 오른쪽 그래프는 스패닝 트리입니다. 그럼 아래 그래프는 스패팅 트리 일까요? 아닙니다. 오른쪽 그래프는 사이클이 발생했고, 오른쪽 그래프는 모든 노드를 연결하지 않고 있습니다. 그렇다면 아래 그래프는 신장(스패닝) 트리일까요? 그렇습니다. 신장 트리 중 최소 신장 트리입니다. 최소 신장(스패닝) 트리는 신장 트리 중 가장 적은 비용을 갖는 그래프입니다. 모든..

[알고리즘] 최단 경로 알고리즘 | 다익스트라 | 플로이드 워셜

~목차~ 최단 경로 문제 다익스트라 알고리즘 플로이드워셜 알고리즘 최단 경로 문제 최단 경로 문제는 그래프 문제로 우테캠 6기 코딩테스트에도 나왔었다 최단 경로 알고리즘은 크게 두 가지로 다익스트라(Dijkstra, 데이크스트라) 알고리즘과 플로이드 워셜 알고리즘이 있다 기본적으로 그래프에 대한 이해를 바탕으로 알고리즘이 진행된다 노드에서 다른 노드로 접근 방법이 없다면 무한수(int(1e9) in Python)로 표시한다. 다익스트라 알고리즘 시작 노드로부터 각 노드까지 최단 경로를 구할 수 있는 알고리즘이다. 문제 해결을 위한 방법은 2가지가 있다. 리스트(배열)을 사용하거나 우선순위 큐 사용하는 것이다. 리스트를 사용하는 것이 우선순위 큐를 사용하는 것보다 쉽지만 시간 복잡도에서 차이가 많이 나므로..

[알고리즘] 시간복잡도 구하기

처음 알고리즘 분류 글을 작성하게 되었습니다(두근) 작년(2022) 이맘때쯤 학교에서 학습했던 알고리즘의 시간복잡도에 관한 내용입니다. 코딩테스트가 익숙해지면서 효율성을 요구하는 문제들과 맞딱뜨리게 되었는데, 이때 알아야 할 기초 개념이 바로 시간복잡도입니다. 내가 짠 코드가 입력 대비 얼마큼의 시간이 필요한가를 계산하여 효율성을 판단하고, 비효율적이라면 어떤 부분을 수정할지 생각해 볼 수 있기 때문입니다. 목차 1. 정의 & 표기법 2. O(1) 2. O(N) 3. O(N²) 4. O(NlogN) 1. 정의 & 표기법 위키 백과에서 인용해 온 컴퓨터과학에서 시간복잡도의 정의 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것 다음은 시간복잡도의 3가지 표현법입니다. 최..