프린세스 다이어리

1. 이진 트리 노드 구현 이진 트리는 부모가 왼쪽 자식, 오른쪽 자식을 가지고 있다는 점에서 포인터를 이용해서 구현하면 효과적인 데이터 관리가 가능하다. 노드 구조체는 다음과 같다. #include #include typedef struct Node { int data; struct Node *leftChild; struct Node *rightChild; } Node; 하나의 노드는 내부적으로 하나의 data를 가지고 있다. 여기 예시 코드에서는 정수형 데이터 하나만 들어가는 걸로 설정했지만, 실제로는 다양한 데이터가 data에 들어갈 수 있다. 특정 노드를 초기화하는 함수는 다음과 같다. Node* initNode(int data, Node* leftChild, Node* rightChild) { ..

깃헙에 잔디를 심으면서 공부를 하는데 가끔가다가 깃헙 들어가보면 열심히 커밋한 내역이 안 보일 때가 있다. 대부분의 경우 커밋한 작성자의 이메일이 해당 깃헙의 이메일과 일치하지 않아서 발생하는 문제다. 이미 다른 계정으로 커밋을 해 왔으니, 해당 레파지토리에 반영된 이전 커밋들의 작성자와 커밋한 사람을 전부 교체해 주고 force push 하면 된다. 터미널에서 깃 레포 루트에서 다음 2단계를 진행해주면 된다. 단 나 혼자 관리하는 개인 레포인 경우에만 권장되는 방식이다. 1. 작성자, 커밋한 사람 바꾸기 git filter-branch -f --env-filter "GIT_AUTHOR_NAME='원하는 작성자 이름'; GIT_AUTHOR_EMAIL='원하는 작성자 이메일'; GIT_COMMITTER_N..

1. 트리란 트리는 나무를 뒤집어 놓은 형태의 자료구조다. 일반적으로 트리의 최상단 노드를 루트 노드라고 하고, 루트 노드에서 가지를 이용해서 각각의 노드로 연결되며, 가장 마지막에 해당하는 원소들을 리프 노드라고 부른다. 또한 트리는 기본적으로 부모와 자식 간의 관계로 이루어져 있다. 가지로 연결된 관계에서 루트 노드에 가까운 노드를 부모 노드, 리프 노드에 가까운 노드를 자식 노드라고 한다. 트리 구조에서 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다. 가지를 2번 거쳐서 1번 노드에서 35번 노드까지 간다면, 길이가 2가 되는 것이다. 깊이란 루트 노드에서 특정 노드까지의 길이를 의미한다. 높이는 가장 높은 노드부터 가장 깊은 노드까지의 길이를 의미한다. 2. 이진 트리란 이진..

1. 퀵 정렬이란 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로, 평균적으로 0(NlogN)의 시간 복잡도를 가진다. 퀵 정렬은 편향된 분할이 발생할 때 연산의 양이 최악의 경우 O(N2) 이다. 따라서 실제로 정렬할 때는 퀵 정렬을 굳이 직접 구현하지는 않는다. C++에 Algorithm 라이브러리에 포함된 sort() 함수는 퀵 정렬을 기반으로 하면서 O(NlogN)을 보장한다. 피벗 값이 가장 왼쪽이라고 가정한다. 5 4 3 8 9 6 7 1 10 2 (1) 5의 왼쪽부터 시작해서 5보다 큰 값을 찾는다. 또 오른쪽부터 시작해..

> 문제 바로가기 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 1. 접근 방법 - [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] 이런 그래프고 각 노드의 [0]이 출발, [1]이 도착임 - 문제에서 항상 ICN 공항에서 출발한다고 했으므로 출발지는 'ICN' - 주어진 tickets(array), 시작노드 'ICN'(string), 탐색중인 경로 path(array), 결과 담을 routes(array) (1) 만약 tickets가..

문제 nums는 숫자로 이루어진 배열입니다. 가장 자주 등장한 숫자를 k 개수만큼 return해주세요. 예시 nums = [1,1,1,2,2,3], k = 2 return [1,2] nums = [1], k = 1 return [1] 접근방향 문제에 최대 nums의 길이나 k의 범위가 제시되어 있지 않아 key를 이용해 상수 시간 복잡도로 접근할 수 있도록 object을 활용하여 풀었다. 마지막에 Object.keys를 활용하여 정렬을 할 때, string 자료형으로 배열에 들어가기 때문에 map함수로 number 형으로 바꿔주는 것에 유의한다. 해답 function topK(nums, k) { let obj = {}; for (let i = 0; i < nums.length; i++) { if (num..

1. 선택 정렬 1-1. 선택 정렬의 원리 선택 정렬이란, 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산을 하기 때문에 O(N2)의 시간 복잡도를 가진다. 이렇게 초기 원소가 있다고 했을 때, 2 4 3 1 9 6 7 8 10 5 가장 작은 원소는 1이므로 맨 앞으로 보내준다. 기존의 맨 앞에 있었던 원소와 자리를 바꿔준다. 1 4 3 2 9 6 7 8 10 5 나머지 원소 중 가장 작은 값인 2를 1 다음으로 넣어 주고 마찬가지로 그 자리에 있었던 원소와 자리를 바꿔준다. 1 2 3 4 9 6 7 8 10 5 이렇게 해서 결과적으로 올림차순으로 정렬할 수 있는 것이다. 1 2 3 4 5 6 7 8 9 10 1-2. 선택 정렬..

> 문제 바로가기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 백준 맞왜틀 극한이다. 4시간 붙들고 있었음 1. 접근 방향 (1) 집이 표시된 그래프와, 내가 확인했음을 기록한 그래프가 필요하다. 초기화시켜준다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split('\n'); const n = +input.shift(); // 집이 있는지 기록된 그래프 input = input.map((arr) => arr.tr..