Jay Tech-FE

정보처리기사 필기 학습을 시작하였는데, 서적을 구매해 공부를 하다보니 요약정리가 필요해서 블로깅으로 남기게 되었다. 구글링으로 찾아볼 수 있는 요약본을 살펴보면 이런식으로 되어있다. 예를들어 IT의 중요한 항목 3가지 접근성, 효율성, 가시성 이라고 가정한다면 '접효가' 같은 형태로 외우라고 되어있는데 이렇게 암기해야 할 부분이 한 두 가지가 아니다. 설계 항목에만 30개는 되는거 같은데 모든 내용을 이런식으로 외울 수 없으니 요약을 따로하여 핵심만 외워보도록 하겠다. 1. 폭포수 모형(Waterfall Model) - 고전적 생명 주기 모형 - 선형 순차적 모형 - 요구사항의 변경이 용이하지 않음 - 타당성검토 → 계획 → 요구 분석 → 설계 → 구현(코딩) → 테스트(검사) → 유지보수 폭포수 - 계..

오늘은 최소신장 트리와 알고리즘에 대해 수강하였다. 최소 신장 트리란? 신장트리란 그래프 내 모든정점을 포함하는 최소연결부분 그래프이다. 최소한의 간선으로 모두 연결된 그래프라고 생각하면 된다. 최소신장트리는 최소한의 간선으로 모든정점이 연결되어있어야 하고, 모든 신장 트리 중 가중치값이 최소이며 사이클이 발생해서는 안된다. 크루스칼 알고리즘은 그리디 개념으로 구현할 수 있고, 모든 그래프를 부분 집합으로 분리한다. 가장 가중치가 낮은 간선을 선택하고 부분 집합을 연결한다. Union-Find 알고리즘을 통해 사이클을 방지할 수 있다. Union-Find 알고리즘 이란 서로 다른 두 집합을 합쳐주는 Union이라는 로직과 집합의 원소가 어떤 집합에 속해있는지 판단하는 Find로직을 통해 판단해주는 데이터..

오늘은 최단 경로 알고리즘에 대해 수강하였다. 평소 운전을 하며 최단경로에 대한 알고리즘 방식에 궁금증이 많았는데 해결 할 수 있는 시간이었던것 같다. 최단 경로 알고리즘 이란? 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘으로써, 종류가 굉장히 다양하지만 목적에 따라 알고리즘을 선택할 수 있다. 먼저 이전에 배운 BFS,DFS는 그래프의 간선 가중치가 모두 같을 때 적합한 알고리즘이다. 다익스트라 알고리즘은 간선에 모두 가중치가 있고, 이 가중치가 모두 양수일 때 사용하기 적합한 알고리즘이다. 유명한 컴퓨터과학자 다익스트라가 고안한 알고리즘으로 국내에선 다익스트라 라고 불리운다. 이는 우선순위 큐에 기반하여 만들어지므로, 우선순위 구현체인 heap에 대해 알고있다면 더 구현하기 쉬워진..

오늘은 알고리즘은 아니지만 재귀함수 에대해 수강하였다. 재귀 함수란? 자기 자신을 호출하는 함수를 말한다. 스택을 이용하는 알고리즘에서 재귀함수를 사용하는 경우가 많으며, 함수형 프로그래밍에선 루프 구현을 재귀로 구현한다. 자바스크립트에서는 재귀함수에서 몇가지 제한이 있는데, 첫번째로 콜 스택에 제한이 있다. 또한 꼬리 재귀 기능이 제공되지않는다. 그래서 이를 통한 성능 구현이 힘들며 성능이 좋지 않다. 재귀를 알아두어야 하는 이유는 재귀로 구현해야 편한 알고리즘이 있기 때문이다. 재귀로 구현하는것이 편하긴하나, 성능이 좋지 않기때문에 코딩테스트에서는 좋은 방법은 아니다. 재귀 함수의 단점으로 무한루프에 걸릴 수 있다는 점 때문에 항상 재귀함수에는 if등으로 중단점을 생성 해준다. 피보나치 수열은 재귀를..

오늘은 소수를 구하는 알고리즘에 대해 수강하였다. 소수 란? 수학시간 배웠던것 과 마찬가지의 의미로 1또는 자기 자신만을 약수로 가지는 수를 의미한다. 이러한 소수를 구하는 알고리즘은 크게 3가지 정도로 구분된다. 첫번째 가장 직관적인 방법으로 2부터 N-1까지 루프를 돌기 때문에 시간복잡도 O(n)이 소요된다. 필자는 이 방법으로 코딩테스트를 진행하였는데, 시간복잡도 면에서 효율성이 떨어진다는 사실을 해당 강의를 통해 알게되었다. 두번째 효율성을 개선하여 그 어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 점을 이용하는 방법이다. 이는 숫자가 클 수록 효율성이 증가하는데, 1000의 소수여부를 판단할 때, 위의 방법으로는 1000번의 루프를 통해 돌아야 했다면, 이 알고리즘은 31번 정도의 루프..

오늘은 그리디 알고리즘에 대해 수강하였다. 오늘 내용은 그리 길지 않다. 그리디 알고리즘 이란? 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘으로써 최적해를 보장하진 않지만 선형시간이 소요되는 알고리즘이다. 최적해를 고려하지않으므로 알고리즘이 굉장히 빠르고, 직관적인 문제 풀이에 적합하다.\ 작동방식은 양자택일 or 다자택일 상황에서 가장 빠른 알고리즘만을 찾아서 진행한다. 그렇기 때문에 최종시간은 최적해를 구하는 알고리즘보다는 오래 걸리게 된다. 예시로는 동전반환문제가 있는데, 이 동전반환 문제가 그리디 알고리즘을 이해하기 가장 쉽다고한다. 가장 큰 액수부터 차감하여 작은 액수까지 진행된다. 그리디 알고리즘은 특정 개념이라고 알고있는 것이 좋다. 이미지 출처: https://school..

오늘은 탐색법인 너비 우선탐색, 깊이 우선탐색에 대해 수강하였다. BFS(너비 우선탐색), DFS(깊이 우선탐색) 이란? 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘, 최대한 깊은 정점부터 탐색하는 알고리즘이다. BFS의 특징은 Queue를 이용하여 구현되며, 시작부터 가장 가까운 정점부터 탐색한다. 나머지 특징은 아래와 같다. BFS(너비 우선탐색)의 방법은 우선 시작지점인 최초정점인 A를 Queue에 넣는다. 그 후 A를 Dequeue 하며 A로부터 이동가능한 간선을 Queue에 넣는다. 그 후 추가된 간선들의 시작 정점을 Deque한 뒤 Dequeue된 정점의 이동가능 간선을 다시 넣는다. 이런식의 추가와 소거를 통해 탐색을 진행한다. 깊이 우선탐색에 대한 정의는 상단에..

오늘은 자료구조가 아닌 요소를 열거하는 알고리즘인 정렬에 대해 수강하였다. 정렬이란 ? 요소들을 일정한 순서대로 열거하는 알고리즘이다. 정렬의 특징은 오름차순일지, 내림차순일지 사용자가 정할 수 있다. 또한 비교식과 분산식 정렬로 구분할 수 있으며 대부분의 언어가 빌트인으로 제공되고 삽입, 선택, 버블, 머지 ,힙, 퀵 정렬등 다양한 정렬방식이 존재한다. 정렬의 사용은 상황에 따라 다르기 때문에, 어떤 정렬이 가장 빠르고 느린지 구분짓기 힘들다. 먼저 비교식 정렬에 대해 알아보자. 비교식 정렬 중 하나로 버블정렬이 있다. 먼저 정렬 되지않은 배열에서 인접한 요소를 검사하여 더 높은 순위를 교환하여 앞쪽에 배치한다. 이를 모든 요소에 적용하여 순회하고, 1번 순회가 마무리된다. 그 후 순회를 2회,3회,4..

오늘은 이진탐색의 기초에 대해 수강하였다. 이진탐색 이란? 아래에 나와있는 선형 탐색과는 다른방법의 탐색으로써, 순서대로 하나씩 찾아 선형 시간복잡도가 소요되는 선형탐색과는 달리 이진 탐색은 요소들의 반씩 제외하며(업,다운 게임) 찾는 알고리즘으로써 정렬이 되어있어야 사용할 수 있지만 시간복잡도는 로그시간이 걸리기 때문에 선형탐색보다 훨씬 빠른 탐색이 가능하다. 이진 탐색의 특징은 반드시 정렬이 되어있어야 사용할 수 있다. 정렬 후 탐색한다면 선형탐색보다 느릴 수 있다. 배열과 이진트리를 이용하여 구현할 수 있다. 시간복잡도가 log n인만큼 굉장히 빠르며, 정렬이 되어있다면 이진탐색을 사용하는것이 매우 좋다. 이렇게 빠른 알고리즘은 거의 없다. 예시로 아래와 같은 45를 찾는과정을 표현해보자 배열을 이..

오늘은 비선형 자료구조인 트라이에 대해 수강하였다. 트라이(Trie) 란? 문자열을 트리구조로 저장하고 효율적으로 탐색하기 위한 자료구조이다. 보통 자동완성이나, 사전에서 사용된다. Root 정점은 빈값으로 주어지며, 간선은 이전 정점으로부터 새롭게 추가되는 문자열을 가지고있다. 정점은 이전정점으로 부터 더해진 문자열을 가지고있다. 이런식으로 자동완성까지 구현된다. 트라이의 특징으로는 자동완성, 사전에 응용되는 경우가많으며 문자열을 탐색할 때 효율적인 탐색이 가능하다. 시간복잡도 또한 O만큼을 가지므로 상당히 빠른편이다. 하지만 각 정점이 자식에 대한 링크를 전부 담고있기 때문에 저장공간이 많이 사용된다는 단점도 존재한다. 트라이 구조는 상단에 언급했던 사실들을 기반으로 짜여진다. 이는 아래와 같다. 먼..