개발 (안드로이드 외)/📚 코딩 테스트 합격자 되기 스터디

상호배타적 집합교집합이 없는 집합관계.집합 표현하기어떤 집합의 원소가 하나의 집합의 원소라는 것을 알 수 있어야 한다.각 집합 간 다른 집합이라는 것을 알 수 있어야 하고,특정 원소가 어느 집합에 속하는지 알 수 있어야 함.두 집합을 하나로 합칠 수 있어야 함 => 대표 원소를 설정한다면?: 각 집합에서 가장 작은 원소를 대표 원소로 설정한다.집합의 연산find특정 노드의 루트 노드를 확인.필요한 경로 깊어질 경우 연산 늘어남. 경로 압축으로..find연산을 하는 노드가 루트 노드라면 루트 노드 반환.find연산을 하는 노드가 루트 노드가 아니라면, 자신의 부모 노드를 find로 설정거쳐가지 않으면 시간복잡도가 O(1)이 되지는 않음 ...union두 집합을 하나의 잡합으로 합친다.작은 루트 노드 쪽으로..

트리의 개념노드와 간선으로 이루어진 계층적 자료 구조 (부모 자식 관계가 있음)순환 X코테에서는 이진 트리만 알면 된다이진 트리 표현배열로 표현루트 노드 인덱스 1왼쪽 자식 노드 : 부모 노드 인덱스 * 2오른쪽 자식 노드 : 부모 노드 인덱스 * 2 + 1문제점 : 빈 공간이 많다 (버려지는 공간이 많아 효율이 별로), 그러나 구현은 쉽다인접 리스트 (이게 더 좋을 수도?_각 리스트의 인덱스는 부모 노드자식 노드는 부모 노드에 해당되는 인덱스에 추가트리 노드 갯수와 인접 리스트 아이템 갯수가 거의 같음.배열보다 공간 호율은 좋은데, 자식 노드를 찾는데 오래 걸림 (순차 탐색 필요). 그러나 이진 트리는 자식 2개라 크게 단점은 아닌..이진 트리 순회트리의 노드를 모두 방문하는 방법현재 노드를 언제 방문..

해시의 개념배열로 연락처 구현하면 이름 -> 이름 테이블에 선형 탐색 -> 그 위치에 해당되는 전화번호 테이블 참조인덱스에 이름 정보를 넣을 수 있게 하려면.해시 적용하면해시 함수를 사용해서 변환한 값을 인덱스로. -> 키를 해시 함수로 돌리면 인덱스가 나온다.O(N) -> O(1)해시 함수임이의 키를 해시 테이블의 인덱스로 변경.-> 테이블 크기가 N이라면 함수는 [0, N-1) 사이 값을 내야 함. 충돌이 적을수록 (동일한 인덱스) 좋은 해시 함수나눗셈법h(x) = x mod k (k는 소수!) -> 테이블 크기가 커지면 큰 소수가 필요함 (구하기 어렵다)곱셈법h(x) = (((x * A) mod 1) * mx는 키, A는 황금비. m은 최대 버킷의 갯수a / b = a / (a + b): 1.618..

스택Last In First Out, 나중에 넣은 애가 먼저 나오는 자료 구조.특정 문제에서 스택을 필요로 하는 경우 스택을 선택하면 된다.이 문제가 스택 문제인지 알아야 함 ->가장 최근에 들어온 원소를 알 수 있다.가장 최근에 들어온 원소순으로 나온다. (가장 최근에 들어온 원소에 대해 작업해야 할 때)ADT란?Abstract Data Type.세부 사항 (내부 자료구조, 언어, 공간 크기) 숨기고 필요한 기능만 명시 (연산, 입력, 출력)스택의 ADT구분정의역할연산boolean isFull()데이터 개수가 maxSize면 t, 아니면 f boolean isEmpty()비었으면 t, 아니면 f void push(ItemType item)데이터 푸시 ItemType pop()데이터 팝, 이후 반환상태i..

취업을 할지 안 할지 모르겠지만, 어쨌든 코딩 테스트가 취약점이긴 하니까 스터디에 들어가 보았다.스터디에서 매주 내용을 블로그에 정리하기를 권장하고 있다.알고리즘정밀성 - 변하지 않는 명확한 작업 단계유일성 - 명확한 다음 단계를 가져야 함타당성 - 구현 가능해야 하고, 사용 가능해야 함입력, 출력 - 입력을 받아들이고 출력을 내보내야 함유한성 - 무한 루프 X, 특정 수의 작업 이후 정지일반성 - 일반적으로 적용할 수 있어야 함 (테스트 케이스만 되는 거 말고..)알고리즘의 성능입력 -> 출력 간구현된 코드 동작절대 시간 측정연산 횟수 측정절대 시간 측정입력값의 입력부터 출력값의 출력까지의 시간 측정.PC마다 그 결과가 다르게 나올 확률이 높음연산 횟수 측정코드가 동일하면 연산 횟수는 모두 동일하므로 ..