전체 글

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 풀이 과정일단 문제를 풀기에 앞서 몇가지 주의사항을 생각해봤다.1. center의 수익은 계산하지 않는다.2. 자신의 추천인에게 수익금의 10%를 주고 그 추천인의 추천인에게도 10%를 준다.(없을 때까지)3. 10% 한 값이 소수면 소수부분을 버리고 추천인에게 준다.4. 10%가 1보다 작으면 분배하지 않는다. 그리고 이 문제를 풀기위해 두 가지 해시맵을 생각했다.1. 판매원 - 추천인 해시맵2. 판매원 - 수익 해시맵 일단 해시맵을 사용한 까닭은 조회를 O(1)로 할 수 있기 때문이다. 이 문..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 풀이 과정A와 B가 다음라운드로 이동했을 때 몇 번으로 번호가 바뀌는지를 파악하고 그 둘의 번호가 같은지를 체크해야한다. 번호가 몇번으로 바뀌는지 체크하는 것은 간단하다.1과 2의 승자는 다음 라운드에서 1이 되고 3과 4의 승자는 다음 라운드에서 2가 된다. 일반화하면 N-1과 N이 만나면 그 라운드의 승자는 N/2가 된다.이를 조금 다르게 생각하면 각 번호에서 1을 더한 값을 2로 나눈 몫이 다음 라운드에서의 번호가 된다.  이렇게 해서 A, B 다음 라운드에서의 번호를 구하고 그 두 번호가 ..

이진 탐색 트리(Binary Search Tree)이진 탐색 트리란?이진 탐색 트리는 다음의 두 가지 조건을 만족하는 이진 트리이다.1. 왼쪽 자식노드들은 자신의 부모 노드보다 작다.2. 오른쪽 자식노드들은 자신의 부모 노드보다 크다(같을 때도 오른쪽). 이러한 배치는 트리에서 특정 데이터를 찾거나 삭제할 때 매우 유용하다. 탐색예를 들어 4라는 값을 찾는다고 가정해보자 4는 8보다 작으므로 왼쪽으로 이동한다.4는 3보다 크므로 오른쪽으로 이동한다.4는 6보다 작으므로 왼쪽으로 이동한다4를 찾았다.이진 탐색트리에서 특정 값을 탐색할 때 아래 노드로 내려갈 때마다 그 반대쪽 노드들은 무시해도 되게 된다.이는 시간복잡도가 O(logN)이 됨을 의미한다.배열에서는 인덱스 순서대로 비교해가며 탐색을 했기 때문에..

트리(Tree)란? 트리의 개념트리는 노드와 간선으로 이루어진 계층형 자료구조이다.나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놨다해서 트리라는 이름이 붙여졌다.계층 구조로 이루어져있기 때문에 데이터를 저장하고 탐색하기에 유용하다. 트리의 구성요소노드트리를 구성하는 요소 루트 노드노드 중 가장 위에 있는 노드 엣지(간선)노드와 노드를 연결해주는 선단방향이며 루트 노드에서 각 노드까지의 경로는 유일하다. 노드 간의 관계엣지로 연결된 노드들은 부모-자식 관계를 가지는데 상위에 있는 노드를 부모 노드, 하위에 있는 노드를 자식 노드라고 한다.같은 부모 노드를 가지는 노드를 형제 노드라고 한다. 리프 노드자식 노드가 없는 노드 차수특정 노드에서 아래로 향하는 엣지의 갯수 이진트리 순회하기 이진 트리란?..