prefer2 Log

Union Find? Union-Find(혹은 Disjoint Set)은 교집합이 공집합인 집합(서로소 집합)들을 효율적으로 표현하기 위해 만들어진 자료구조이다. 서로 다른 집합을 하나의 집합으로 합치는 Union 연산과 원소가 어떤 집합에 포함되어있는지를 찾는 Find연산으로 이루어져있다. 노드간의 연결관계가 주어졌을 때 그룹 관계를 파악할때 주로 사용한다. 코드 (c++) 초기화 각 노드들이 자기 자신을 부모(parent)로 가지도록 초기화해준다. for (int i = 1; i

문제 수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다. 각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다. 수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 ..

인덱스 트리란? 포화 이진 트리 형태의 자료구조로 부모 노드가 자식 노드의 대표값을 가지는 트리이다. 리프 노드에 사용할 값들을 적어놓고, 부모 노드에 값들의 합을 모아놓은 형태이다. 글보다 아래 그림 예제를 보면 쉽게 이해할 수 있다. 언제 사용? 배열 A가 있고 아래 두 연산을 M번 수행해야 하는 문제가 있다고 하자. 1️⃣ 구간 l, r이 주어졌을 때 A[l]+A[l+1]+...+A[r-1]+A[r]을 구해라 2️⃣ i번째 수 A[i]를 X로 바꾸어라 N개의 수가 있다고 할 때 일반적인 방법으로는 1번 연산을 수행하는데는 O(N), 2번 연산을 수행하는 데에는 O(1)이 걸려 결과적으로 시간 복잡도는 O(NM)이 된다. 누적합 배열을 사용해서 풀게 되어도 1번 연산 O(1), 2번연산 O(N)으로 ..

문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을..

준비기간 프리코스가 수요일에 끝나고 시험이 토요일이라 약 3일간의 시간이 있었다. 사실 마지막 미션이 생각보다 어려웠어서 미션 수요일은 영화를 보며 쉬었다. 마지막 미션에서 배운점이 많아서 다른 분들 코드도 보고 내 코드도 리팩토링하며 보냈다. 전날은 작년 2차 테스트를 풀어보았다. 작년 테스트는 마지막 미션보다는 구현할 내용도 적고 간단한 편이라 덕분에 자신감을 얻고 시험을 맞이했던 것 같다. 최종 테스트 시험은 1시부터 6시까지 총 5시간동안 치뤄졌다. 온라인으로 진행이 되었고 매우 프리한 환경에서 시험이 이루어졌다. 음료와 간식 섭취가 가능하고 화장실도 갈 수 있어서 전날 사놓은 과자들과 커피를 들고 시험을 준비했다. 테스트는 기존의 미션과 진행 방식이 동일했다. 테스트 내용은 아래 깃헙에서 확인 ..

문제 집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다. 양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가..

문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, ..

프리코스에 들어가기에 앞서 우테코를 합격하고 5일이라는 시간이 있었다. 우아한테크코스는 기존의 과제들을 모두 github에서 확인이 가능하다. 막 미리 해보는 것보다는 어떤 식으로 과제가 진행되는지만 알아보았다. 기존 과제들을 모두 공유하다니! 너무나도 친절하다 여러 블로그들에서 클린코드라는 책을 많이 추천해주셔서 도서관에서 빌려서 읽어보았다. 역시 유명한 책은 이유가 있었다. 딱딱한 기술 서적인줄 알았는데 번역이 잘 되어있어서 그런지 소설책처럼 술술 읽혔다. 맘에 들어서 그냥 사버렸다. 미션을 진행하다보니 책에서 하지 말라는 대로 코딩하고 있는 내 자신을 발견할 수 있었다. [1주차] 숫자 야구 게임 ⚾ 1주차 과제는 지난 해와 동일한 숫자 야구 게임이었다. https://github.com/woowa..

문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 이 도시에 있는 치킨집은 모..

나도 모르게 export와 export default를 섞어 쓰고 있음을 발견했다. 이 둘의 차이를 명확하게 알아보면서 좀 더 일정한 코드 작성을 해보고자 한다. export export 문은 JavaScript 모듈에서 함수, 객체, 원시 값을 내보낼 때 사용한다. export 키워드는 선언문 앞에 사용한다. // 변수의 export export const name = 'Ann'; // 함수의 export export function sayHello() { console.log('Hello World!'); } // 클래스의 export export class Person { constructor(name){ this.name = name; } } 선언문 앞에 매번 export 키워드를 붙이는 것이 번..