Red-Black 트리란 - 이진 탐색 트리(BST)의 한 종류로 스스로 균형을 잡는 트리로써 BST의 worst case(한쪽으로 편향이 되어있는 상태에서 삽입 삭제 검색의 시간 복잡도는 O(N)으로 오래걸린다.)의 단점을 개선했다. 모든 노드는 red혹은 black으로 표현 Red-Black트리의 5가지 속성 1. 모든 노드는 red 혹은 black 2. 루트 노드는 black 3. 모든 nil(leaf) 노드는 black * 중요nil 노드란? - 존재하지 않음을 의미하는 노드, 자녀가 없을 때 자녀를 nil 노드로 표기, 값이 있는 노드와 동등하게 취급, RB트리에서 leaf 노드는 nil 노드(파란색 동그라미) 4. red의 자녀들은 black 즉 red가 연속적으로 존재할 수 없다. 5. 임..
ls: 내 위치의 모든 파일을 보여준다. pwd: 내 위치(폴더의 경로)를 알려준다. mkdir: 내 위치 아래에 폴더를 하나 만든다. cd [갈 곳]: 나를 [갈 곳] 폴더로 이동시킨다. cd .. : 나를 상위 폴더로 이동시킨다. cp -r [복사할 것] [붙여넣기 할 것]: 복사 붙여넣기 rm -rf [지울 것]: 지우기 sudo [실행 할 명령어]: 명령어를 관리자 권한으로 실행한다. sudo su: 관리가 권한으로 들어간다. (나올때는 exit으로 나옴) 관리자 모드로 진입하기 sudo su vi에디터를 이용해 코딩을 하면 된다 Vi [만들파일명].c : c파일 만들기 코드 작성창 나옴 vi 명령어 다른건 몰라도 반드시 command + z의 기능을 하는 u는 외우자 다 작성하면 esc 눌러서 ..
1-1 정보는 비트와 컨텍스트로 이루어진다. 프로그램은 프로그래머가 에디터로 작성한 소스 파일(0,1로 표시되는 비트의 연속 바이트라는 8비트 단위이다)로 생명을 시작하며 텍스트 파일로 저장된다. 소스 프로그램에서 각 바이트는 프로그램의 텍스트 문자를 나타낸다. 대부분의 컴퓨터 시스템은 텍스트 파일을 아스키(ASCII)표준을 사용하여 표시한다.(각 문자를 바이트 길이의 특정 정수값으로 나타냄) 연속된 바이트로 파일에 저장되는데 이것을 텍스트 파일이라 부른다. 다른 모든 파일들은 바이너리 파일이다 * 모든 시스템 내부의 정보, 디스크파일, 메모리상의 프로그램, 데이터는 비트들로 표시된다. 서로 다른 객체들을 구분하는 유일한 방법은 이들을 구분하는 유일한 방법은 컨텍스트에 의해서다. ex) 동일한 일련의 바..
3주차를 마무리했다. 이번 주에서 다뤘던 주제는 그래프 탐색과 BFS, DFS이다. 코딩 테스트에서 자주 출제되는 유형이기 때문에 이전 주제들보다 더 신경을 많이 썼다고 생각했지만 3 주차 시험 3문제 중 1개밖에 못 풀었다. 이유는 단순히 내 학습량이 부족해서인 것 같다. 추가적으로 부족한 점을 채우기위해 따로 문제를 찾아서 풀어본 적이 없는데 NHN 아카데미 때 매일 주어지는 과제를 따라가기 급급해 내 개인학습 시간이 없었을 때와는 상황이 다름에도 똑같은 태도로 정글에 임하고 있는 거 아닌가 라는 생각이 들었다. 뒤에서 따라가는 수준에서 만족하자고 들어온 곳이 아니기때문에 마음을 다잡고 더 열심히 해야겠다. 이번주 키워드 DFS(Depth First Search) - 말 그대로 깊이 우선 탐색 그래프..
문제링크:https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 다루는 주제: 그리디 import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) # 지원자 수 apply = [0] * (n + 1) # 미리 0부터 n+1까지 배열 만들어놓기 for _ in range(n): a, b = map(int, input().split()) app..
2주차를 마무리했다. 본격적으로 알고리즘 주차가 시작된거같다. 백준 플레티넘 문제는 처음보는데 문제를 이해하는데 3시간 구현 할 엄두 조차 안나서 풀이를 보고도 이해하는데 5시간 거의 하루종일 한 문제만 잡고 있었다. 1주차에 붙혔던 재미가 다 나가떨어지는 이렇게까지 알고리즘 하나 풀어보겠다고 몰두해본 경험이 없는거같은데 이렇게 몰입하고 고민했던 문제들은 정말 글을 쓰는 지금도 기억이 남을정도로 강렬한 맛이다. 좋은거 같아요 👍 이번주 키워드 이분탐색 - 이분 탐색이란 데이터가 정렬되있는 배열에서 특정한값을 찾아내는 알고리즘이다. 중간에 있는 임의의 중간값을 찾고자하는 값 X와 비교하여 X가 중간값보다 작을땐 중간을 기준으로 좌측의 데이터를 탐색 중간값보다 클땐 우측의 데이터를 탐색 반복한다.(종료조건은..
문제링크:https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 다루는 주제: 그리디 import sys # 첫줄 가지고 있는 동전 종류 n개 만들고자하는 k # 둘쨰 줄 부터 동전의 가치 오름차순으로 나타남 # coin(i)는 coin(i-1)의 배수라는 조건이 중요하다 # 따라서 코인중 가장 큰놈부터 나눈만큼 카운팅하며 나머지를 k에 저장 반복 n, k = map(int, sys.st..
문제링크:https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 다루는 주제: 그리디 import sys # N개의 회의 # meeting # 각 회의의 시작 시간 start, 끝난 시간 end 같을수있다 # 겹치지않게 회의 최대 개수 찾아보자 N = int(sys.stdin.readline()) # 회의 개수 meetings = [] # 회의 리스트 for _ in range(N): start, end = map(int, sys.stdin.readline().split()) meetings.append([start, end]) meetings = sorted(mee..
