Hello Ocean! 🌼

탐색문제? 저장된 데이터들 중에 원하는 값을 찾는 문제이다. 1. 선형 탐색 알고리즘 (Linear Search Algorithm) 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘이다. 가장 단순하고 간단한 탐색 알고리즘이다. 맨 끝부터 하나하나 원하는 값을 찾아본다. 원하는 값을 찾으면, 탐색을 종료한다. 예시 5를 찾을 때, 맨 왼쪽에 있는 1부터 시작해서 하나씩 탐색한다. 시간 복잡도 길이 n짜리의 리스트를 탐색할 때, 최선의 경우 리스트의 첫 번째 원소가 정답인 경우 : 1번 최악의 경우 리스트의 맨 마지막 원소가 정답이거나, 리스트에 정답이 없을 때 : n번 따라서 O(n)의 시간복잡도를 가진다. 2. 이진 탐색 알고리즘 (Binary Search Algorithm) 중간지점을 기준으..

H-index 출처 : https://programmers.co.kr/learn/courses/30/lessons/42747 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1..

정렬 (Sort) n개의 숫자가 주어졌을 때, 이를 특정한 기준(오름차순, 내림차순 등)에 맞게 정렬하여 출력하는 알고리즘 매우 다양한 정렬 알고리즘이 존재하고, 각 알고리즘마다 수행시간이 다르다. 삽입정렬 k번째 원소를 1부터 k-1까지의 숫자와 비교해 적절한 위치에 끼워 넣고, 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식. 자료구조에 따라서 뒤로 밀어내는데 걸리는 시간이 클 수 있다. 그리고 역순으로 정렬되어있을 경우에 매우 오래걸린다. 반면에 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/삭제하는 경우에는 최고의 정렬 알고리즘이 된다. 구현이 매우 쉽다. 이미지 출처 - 나무위키 이진 삽입 정렬 이진 탐색을 활용해서 새로운 원소가 위치할 곳을 미리 찾아서 정렬하는 방식 원소 크기 비교하는 부분을..

비트 조작 비트 연산자 AND 둘 다 1이면 1, 둘 중 하나라도 0이면 0이다. 1010 AND 1110 = 1010 연산자 : & OR 둘 중 하나라도 1이면 1, 둘다 0이면 0이다. 1010 OR 1110 = 1110 연산자 : | NOT 모든 bit값을 반대로 바꾼다 NOT ( 1010 ) = 0101 연산자 : ~ XOR 값이 같으면 0, 다르면 1이다. 1010 XOR 1110 = 0100 연산자 : ^ 비트 시프트 산술 우측 시프트 값을 2로 나눈 것과 같다. 연산자 : >> 부호 비트는 바뀌지 않음. 논리 우측 시프트 일반적으로 비트를 옮길 때 처럼 동작한다. 연산자 : >>> 비트를 우측으로옮긴 후에, 최상위 비트에 0을 넣는다. 추가 정보 0s : 모든 bit가 0 1s : 모든 bi..

1.트리, 그래프 비선형 구조 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 트리 트리의 구성 요소 Root Node : 트리 구조에서 최상위에 존재하는 노드 (A) Node : 트리의 구성요소에 해당하는 요소 (A,B,C,D,E,F,G) Edge : 노드와 노드를 연결하는 선 Terminal Node(Leaf Node) : 트리의 맨 밑에 있는 자식을 가지지 않는 노드 Sub-Tree : 전체 트리에 속하는 작은 트리 Level : 트리에서 각 층별로 숫자를 매김 (root node = level 0) Height : 트리의 최고 레벨 트리의 종류 이진트리 (binary tree) 어떤 한 노드가 2개 이하의 자식만을 가지는 트리 포화이진트리 ..

배열 정적배열 우리가 생각하는 일반적인 배열. 크기가 고정되어 있다. 동적배열 (vector) 중간에 값을 추가하거나 삭제할 수 있다. https://blockdmask.tistory.com/70 이 링크에서 배열의 사용법을 자세하게 배울 수 있다. 문자열 배열 여러 글자로 이루어진 문자 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식. https://blockdmask.tistory.com/338 연결리스트 연결 자료구조는 순차 자료구조 (ex배열)과 달리 원소의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다. 연속한 물리주소에 의해 원소 순서를 표현하는 것이 아니라, 각 원소에 저장되어 있는 다음 원소의 주소(링크)에 의해 순서가 연결되는 구현 방식이기 때문이다. 노드 단..