해시 테이블 먼저 배열에 대해 생각해보자. 배열은 컴퓨터 프로그래밍에 있어서 가장 근본이 되는 자료구조이다. 레지스터가 메모리 어드레싱을 통해 특정 번지의 값을 바로 참조해올 수 있는 것처럼, 배열도 특정 주소의 공간을 바로 참조해올 수 있다. 사실 이 특성은 굉장히 유용하게 활용될 수 있다. 특정 위치를 탐색비용 없이 참조해 올 수 있다는 것은, 어떤 데이터들을 저장할 때, 각 데이터가 저장될 위치를 결정할 수 있다고 가정했을 때, 아무런 탐색비용 없이 그 데이터를 저장하고 참조해올 수 있는 자료구조를 설계할 수 있다는 의미이다. 리스트와 같은 일반적인 컨테이너가 저장비용으로 O(1), 데이터 참조 비용으로 O(N) 인 것을 감안했을 때, 저장비용 O(1), 참조비용 O(1)은 자료구조로서 엄청나게 효..
이진 탐색 트리 (Binary Search Tree) 이진탐색트리는 키(Key)를 기반으로 한 데이터들을 트리 구조로 관리하는 노드기반 자료구조이다. 루트 데이터의 키를 기준으로 더 작은 키 값을 갖는 데이터들은 왼쪽 하위 서브트리에 위치시키고, 더 큰 키 값을 갖는 데이터들은 오른쪽 하위 서브트리로 위치시킨다. 그리고 각 서브트리들은 재귀적으로 같은 전략을 통해 새로운 데이터들을 위치시킨다. 일반적인 리스트 형태로 구조화된 자료구조에서는 데이터를 탐색하기 위한 비용이 O(N) 정도인 반면, 이진 트리 형태로 자료를 구조화시키고 나면, 이진탐색을 통해 원하는 데이터를 찾기 위한 탐색비용을 O(logN)까지 줄일 수 있다. 예를 들어 7을 키로 갖는 데이터를 찾고자 한다면, 다음과 같은 순서로 찾을 수 있..
소수 소수판별 어떤 자연수 N을 입력으로 받았을 때, 그 자연수가 소수인지 아닌지 판단하는 알고리즘을 작성해보자. 어떤 자연수 N이 소수라고 한다면, 그 수는 1과 자기자신 외의 약수를 가지지 않는다. 그러므로 가장 간단하게 알고리즘을 작성한다면 2부터 N-1까지의 모든 자연수로 나누어 보고, 한번이라도 나누어진다면, 소수가 아니고, 단 한번도 나누어지지 않았다면 소수라고 할 수 있을 것이다. 하지만, 합성수의 대한 개념을 이용하면, 이 알고리즘을 조금 더 최적화시킬 수 있다. 합성수란, 1과 자기자신 외의 다른 약수를 갖고있는 수를 의미한다. 예를 들어 6은 2*3으로 표현될 수 있으므로 합성수이다. 소수와 완전 반대되는 개념을 갖으므로, 어떤 수가 합성수라면, 소수가 아니다. 어떤 자연수 N이 입력으..
기본 개념 정렬은 컨테이너에 저장된 데이터를 크기 순으로 나열하는 알고리즘을 말한다. 정렬 알고리즘은 굉장히 많은 알고리즘들의 기초 토대가 되기 때문에, 잘 알고 있어야한다. 다음과 같은 수열이 있다고 가정해보자. 3, 500, 2, 600, 5, 150, 800, 1, 2500, 800 수열을 작은 수에서부터 큰 수로 나열하는것을 오름차순 정렬이라 한다. 1, 2, 3, 5, 150, 500, 600, 800, 800, 2500 수열을 큰 수에서부터 작은 수로 나열하는것을 내림차순 정렬이라 한다. 2500, 800, 800, 600, 500, 150, 5, 3, 2, 1 어떤 정렬 알고리즘으로 수열을 정렬하였을 때 같은 크기의 원소가 정렬 후에도 순서가 유지된다면, 그 정렬을 Stable Sort라 부..
별찍기 - 7 www.acmicpc.net/problem/2444 2444번: 별 찍기 - 7 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 소스코드 #include #include using namespace std; int main() { // 별찍기 - 7 int n; cin >> n; // scanf // 5가 들어왔을 경우 -4 ~ 4 for (int y = -(n - 1); y to; reverse(v, from, to); } print(v); return 0; } 미로 탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 ..
코딩테스트 연습 > 해시 > 완주하지 못한 선수 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Hash/Solutions/Programmers/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%20%EB%AA%BB%ED%95%9C%20%EC%84%A0..
코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT 신규 아이디 추천 programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 시행착오 6단계에서 연산 후 . 문자열을 제거해야하는데, 문제를 꼼꼼히 읽지 않아서 시간을 좀 소모함. 소스코드 github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/String/Solutions/Progr..
