목록Programming/Algorithm (86)
fffo
그래프 그래프정의 그래프탐색 위상정렬 최소신장트리 최단경로검색 그래프의 정의 정점의 모음과 이 정점을 잇는 간선의 모음 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때, G = (V, E)이다 사이클 : 정점 하나를 두 번 이상 거치는 경로 인접 : 간선으로 연결 되어있는 두 정점의 관계 (이웃) 연결성(connectivity) : 그래프의 연결성 : 그래프 내 각 정점들이 모두 연결되어 있을 때 정점의 연결성 : 두 정점간 경로가 존재 할 때 그래프 표현 정점 간의 인접 관계를 어떻게 나타낼 것인가? → 2차원 배열 혹은 리스트 인접 행렬(Adjacency Matrix) N개의 정점이 있을 때, N x N 행렬에서 각 원소가 인접해있는 경우 1로, 아니면 0으로 표기 그래프가 무방향성을..
문제 문제 설명 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다. 개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 "카카오 신입 개발자 공채" 관련 기사를 검색해보았다. 카카오 첫 공채..'블라인드' 방식 채용 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용 카카오, 블라인드 전형으로 신입 개발자 공채 카카오 공채, 신입 개발자 코딩 능력만 본다 카카오, 신입 공채.. "코딩 실력만 본다" 카카오 "코딩 능력만으로 2018 신입 개발자 뽑는다" 기사..
문제 문제 설명 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제한사항 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다. 입출력 예 s answer "()()" true "(())()" true ")()(" false "(()(" false 입출력 ..
해시 테이블 해시 해시 : 데이터를 새로운 형태의 데이터로 바꿈 해시 테이블 : 데이터의 해시 값을 테이블 내의 주소로 이용 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있음 나눗셈법 해시 함수가 테이블 크기로 키값을 나눈 나머지를 반환 나눗셈법으로 구현된 해시 함수가 테이블 내의 공간을 효율적으로 사용하기 위해서는 테이블의 크기를 2의 제곱수와 거리가 먼 소수로 지정 하는 것이 좋음 자릿수 접기 숫자 자릴를 충돌과 클러스터 (Collision, Cluster) 충돌 : 키 값이 다른 두 자료에 대해 해시 함수가 같은 해시 값을 낼 때 클러스터 : 해시 테이블 내의 일부 지역에 데이터가 모이는 문제 충돌 해결법 체이닝 충돌이 일어날 때 데이터를 해당 주소에 있는 링크드 리스트에 삽..
문제 문제 설명 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요. 제한 사항 n은 1,000,000 이하의 자연수 입니다. 입출력 예 n result 78 83 15 23 입출력 예 설명 입출력 예#1 문제 예시와 같습니다. 입출력 예#2 15(1111)의 다음 큰..
문제 문제 설명 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5,6] 4 [7] [..
우선순위 큐와 힙 힙 힙 순서 속성(Heap Order Property)를 만족하는 완전 이진 트리 힙을 이용해 우선순위 큐를 구현할 수 있음 힙 삽입 힙의 최고 깊이, 최 우측에 새 노드 추가, 완전 이진 트리를 만족 시켜야 함 삽입한 노드를 부모 노드와 비교 후 부모 노드보다 우선순위가 높으면 부모 노드와 교환 (반복) 힙 제거 루트 노드가 우선순위가 가장 높기 때문에 루트 노드를 제거 최하위 최우측 노드를 루트에 넣고 자식과 우선순위 비교하면서 내려가기(반복) 힙 구현 보통 트리를 구현하는 링크드 리스트는 트리 최하위 최우측을 바로 알아내기가 어려움 배열을 이용, 자식 노드로의 링크는 인덱스값 * 2로 구현
탐색 순차 탐색 자기 구성 순차 탐색 자주 사용되는 요소를 앞에 배치함으로써 순차 탐색의 효율을 높임 전진 이동법 : 한 번 탐색된 요소를 집합의 가장 앞에 위치 전위법 : 탐색된 요소를 바로 이전 요소와 교환 계수법 : 각 요소가 탐색된 수를 저장해 해당 수의 내림차순으로 요소를 재정렬 이진 탐색 정렬된 집합의 중앙값과 탐색값을 비교해 작다면 나머지 왼쪽을 대상으로 다시 이진탐색, 크다면 반대 이진 탐색 트리 왼쪽 자식 트리는 자신보다 작고 오른쪽 자식 트리는 자신보다 큰 이진 트리 이진 탐색을 위한 자료구조 트리의 각 노드는 중앙 요소임 삽입 시 이진 탐색을 수행, 조건에 맞는 리프 노드에 삽입 삭제 시 리프 노드가 아닌 경우 자식 노드를 적절하게 부모 노드에게 연결 삭제될 노드의 오른쪽 자식 노드의..