전체 글

들어가기 전에 2021/02/24 - [Algorithm/자료구조] - [자료구조] 그래프 [자료구조] 그래프 그래프(Graph) : 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조 ex) 지하철 노선도, 지도, tree(선형자료구조들이나 트리를 그래프의 한 종류로 볼 수 있다.) 그래프 구성 그래프 hohodu.tistory.com 그래프 탐색 - 그래프의 가장 기본적인 연산 시작 정점부터 차례대로 모든 정점들을 한 번씩 방문 많은 문제들이 단순히 탐색만으로 해결됨 ex) 도로망(특정 도시에서 다른 도시로 갈 수 있는지 여부 , 전자회로(특정 단자와 다른 단자의 연결 여부 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) - 한 방향으로 갈 수 있을 때까지 가다가..

그래프(Graph) : 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조 ex) 지하철 노선도, 지도, tree(선형자료구조들이나 트리를 그래프의 한 종류로 볼 수 있다.) 그래프 구성 그래프는 G(V,E)로 표시 - 정점(vertices) 또는 노드(node) 여러가지 특성을 가질 수 있는 객체 의미 V(G) : 그래프 G의 정점들의 집합 - 간선(edge) 또는 링크(link) 정점들 간의 관계 의미 E(G) : 그래프 G간의 간선들의 집합 그래프의 종류 - 무방향 그래프 간선을 통해서 양방향으로 갈 수 있음 (A,B)로 표현 (A,B)=(B,A) - 방향 그래프 간선을 통해서 한쪽 방향으로만 갈 수 있음 일방통행 길 로 표현 ≠ - 가중치 그래프 네트워크(network)라고도 함 간선에..

들어가기 전에 분할 정복식 알고리즘 : 하향식 해결법으로서, 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다. ( ex)피보나치 알고리즘의 재귀) 동적계획 상향식 해결법을 사용하여 알고리즘을 설계하는 방법이다. 이 방법은 분할정복식 방법과 마찬가지로 문제를 나눈 후에 나누어진 부분들을 먼저 푼다. 그러나 이미 풀어서 답을 알고 있는 부분의 결고가 다시 필요한 경우에는 반복하여 계산하는 대신에 이미 계산된 결과를 그냥 사용한다. -> 작은 문제의 답을 저장했다가 사용 개발 절차 1. 문제의 사례에 대해서 해답을 주는 재귀 관계식(recursive property)을 정립한다. 2. 작은 사례를 먼저 해결하는 상향식 방법으로 문제의 사례를 해결한다. 예제1) 피보나치 수 구하기 -분할..

문제 설명 : 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 스카피는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야 ..

문제 설명 : IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다. 해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다. 단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연..

문제 : 출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.) 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자. 위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다. 입력 형식 : 입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다. 1..

문제 : 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧..

문제 : 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124나라 10진법 124나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 제한사항 : n은 500,000,000이하의 자연수 입니다. 코드 : #include #include using namespace std; string ..

1. sort 헤더파일 : sort(start,end)를 이용하여 [start,end)의 범위에 있는 요소를 오름차순(default)으로 정렬해주는 함수이다. 퀵 정렬을 기반으로 합수가 구현되어 있고, 평균 시간 복잡도는 O(nlogn)이다. sort(arr, arr+n); //배열 sort(v.begin(), v.end()); //벡터 sort(v.begin(), v.end(), compare); //사용자 정의 함수 사용 sort(v.begin(), v.end(), greater()); //내림차순 (Descending order) sort(v.begin(), v.end(), less()); //오름차순 (default = Ascending order) 출처: https://blockdmask.tis..

정렬이란? 물건을 크기순으로 오름/내림차순으로 나열하는 것 정렬 알고리즘 종류 삽입 정렬(Insertion Sort) 선택정렬(Selection Sort) 버블 정렬 셀 정렬 합병 정렬(Merge Sort) 퀵 정렬(Qiuck Sort) 힙 정렬(Heap Sort) ->우선순위 큐 기수 정렬 계수 정렬 1. 삽입 정렬(Insertion Sort) 정렬되어 있는 부분에 새로운 레코드(정렬의 대상)를 올바른 위치에 삽입하는 과정 반복 구현 //오름차순으로 정렬 void insertionSort(int A[], int n) { for (int i = 1; i = 0 && A[j] > key; j--) A[j + 1..