문제 설명 : 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 : 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 comput..
Algorithm
문제 설명: 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 : 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 : triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 풀이 :..
Disjoint Set DisJoint Set이란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 - 즉, 공통 원소가 없는 "상호 배타적"인 부분집합들로 나눠진 원소들에 대한 자료구조 - Disjoint Set=서로소 집합 자료구조 Union-Find Union-Find란? Disjoint Set을 표현할 때 사용하는 알고리즘 -집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현 -아래의 세가지 연산을 이용하여 Disjoint Set을 표현 Union-Find의 연산 - make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. - union(x,y) x가 속한 집합과 y가..
탐색이란? 여러개의 가죠 중에서 원하는 자료를 찾는 작업 -탐색을 효율적으로 수행하는 것은 매우 중요 -탐색키(search key) 항목과 항목을 구별해주는 키(key) -탐색을 위하여 사용되는 자료구조 배열, 연결리스트, 트리, 그래프 등 순차탐색 -탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법 : 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사 -평균 비교 횟수 탐색 성공 : (n+1)/2번 비교 탐색 실패 : n번 비교 -구현 int sequentialSearch(int list[], int key, int low, int high) { for (int i = low; i 원소들을 모두 이동시켜야 함. 이진 탐색 트리는 매우 빠르게 삽입/삭제 수행 삽입,삭제가 빈번히 이루어진다면 이진탐색..
들어가기 전에 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..
