내직업은 IT종사자/알고리즘.자료구조 (4) 썸네일형 리스트형 [algorithm] 시간복잡도란? 시간복잡도 계산하는법 ( O(1), O(n), O(log n)) - 시간복잡도의 정의(바로가기) - 시간복잡도 계산법(바로가기) 1. 시간복잡도란? (Time complexity) 알고리즘 문제를 풀 때 예상 입출력 케이스를 코드 실행을 통해 통과 했음을 확인했어도 정작 코드 제출을 하면 효율성에서 시간초과로 통과하지 못하는 경우가 있다. 우리가 작성한 코드는 실행시간이 얼마나 걸릴까? 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다. 2. 시간복잡도 표현방법 점근적 표기법(3가지)로 시간복잡도를 나타내는데 사용된다. 최상의 경우 : 오메가 표기법 (Big-Ω Notation) 평균의 경우 : 세타 표기법 (Big-θ Notation) 최악의 경우 : 빅오 표기법 (Big-O Notation) 평균인 세타 표기법을 사용한다고 생각할 수 도 .. [algorithm] stack(스택)이란? 사용 예제/방법 (javascript 코드) 스택(Stack) 이란? 메모리의 스택 영역은 함수의 호출과 관계되는 지역변수, 매개변수, 리턴 값 등의 임시데이터를 저장되는 영역. LIFO(Last In First Out, 후입선출) 구조 (데이터는 넣은 순서에 따라 아래서부터 위로 쌓이고, 제일 최상위(최근에 저장된 데이터) 부터 빠지는 구조입니다. 스택의 TOP & BOTTOM TOP/BOTTOM은 스택의 특정위치를 가르킨다. TOP은 가장 최근에 스택에 저장된 값, BOTTOM은 가장 처음 스택에 저장된 값을 가르킨다. 현재 TOP은 최상의 (B)이고 BOTTOM은 최하위 (A) 이다. 여기서 새로운 요소(C)가 추가 된다면! 가장 최근에 추가된 요소가 최상위로 가기때문에 TOP은 (C), BOTTOM은 최하위 (A)를 가르킨다. 예제 java.. [algorithm] 해시테이블 자료구조 란? 해시테이블이란? 키와 값을 받아 키를 해싱 하고, index에 값을 저장하는 선형 자료 구조. 시간복잡도 면에서 삽입(add)은 O(1) 상수시간이 소요되며, 키를 알고 있다면 삭제, 탐색도 O(1)이 소요된다. 해쉬테이블이 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장합니다. 값이 저장되는 방법은 key,value 값을 해쉬 함수 연산을 통해 index값으로 계산하고 buckets에 해당인덱스에 저장한다. 해시는 언제 사용하면 좋을까 ? 예. 학생정보, 회원정보, 환자정보 등등 key value 쌍을 이루는 값들을 다뤄야할때 연결리스트를 사용한다면 학생정보를 탐색할때 O(n)시간복잡도가 걸린다. 배열을 사용한다면 인덱스를 모를 경우 탐색에 O(n)이 걸린다. 해시테이.. [알고리즘 코딩테스트 꿀팁] 코딩테스트 잘보는 법 TIP 예상 할 수 있듯이 특별한 꼼수가 있는 것은 아니다. 그리고 다 아는 얘기, 당연하지만 쉽게 간과할 수도 있는 내용이라고 생각한다. 코딩 테스트 사이트: 백준코딩: https://www.acmicpc.net/ 프로그래머스: https://programmers.co.kr/ 해커랭크 : https://www.hackerrank.com/ 린트코드 : https://www.lintcode.com/ 리트코드 : https://leetcode.com/ [문제를 풀 때 TIP] 여러가지 풀이방법이 있을 수 있다는 것을 생각하기. (생각이 고착화 되어 막힌다면 풀이시간이 길어질 수도, 풀지 못할 수도 있다.) 항상 예외가 있을 수 있다는 것을 생각하기. (예측케이스를 고려하지 못하면 틀릴 수 도 있다.) 더 효율적인 .. 이전 1 다음
