Whatever floats your boat

21.11.14일 추가함. 문제를 보고 인공지능 시간에 배운 게임이론이라는 것을 알았다. min max 트리를 그려서 풀려고 했는데 역시 이론만 아는것이랑 실제 코드를 짜는것은 다르다는것을 느꼈다.. 그리고 재귀 호출시에 vector를 복사해주었는데 이부분에서도 시간초과가 발생하였다. 사소한 것이라 생각했지만 문제풀이에 크게 차이난다는 것을 느꼈다. 이번 문제에서 알게된 것 재귀함수 호출시에 배열, 벡터 등의 값을 복사할 떄는 시간과 메모리 공간이 많이 소모되기 때문에 레페런스로 호출해주도록 한다. 이론을 아는것과 구현은 다르다. min max 알고리즘(게임이론)에서 나를 기준으로 보고 상대의 점수가 min이 되도록 선택하도록 해야한다. dp[left][right]는 내가 얻을 수 있는 점수이기 때문에 ..

유클리드 호제법 유클리드 호제법은 유클리드가 발견한 두 수의 최대공약수를 구하는 방법이다. 원래 우리가 초등학교때 배운 방법은 컴퓨터에서 실행하려고 할 때, 두 수가 커지면 비효율적으로 동작하게 된다. 따라서 유클리드 호제법을 이용해 최대공약수를 구하고 그 다음 최소공배수를 구해야한다. 최대공약수 반복문을 이용해 구현한 유클리드 호제법은 다음과 같다. int GCD(int a, int b) { while(b!=0) { int c = a % b; a = b; b = c; } return a; } 최소공배수 두 수의 곱은 두 수의 최대공약수와 최소공배수와 같다는 수학적 성질을 이용해 최소공배수를 구한다. 예를 들어 10와 15의 최대공약수는 5이다. 따라서 최소공배수를 구하기 위해서 다음과 같은 식을 만족한..

풀이 먼저 문제에서 이해한것을 바탕으로 구현하였더니 시간초과가 났다. 그 이유는 for문을 2부터 증가시키면서 매번 lcm을 찾아 계산해주었기 때문이다. 이제 생각을 바꿔 반복문의 수를 줄여야 한다. 다음의 값을 x1에 대해 정리해 왼쪽으로 이동시킨다. (x1 >= b / a) 이러면 x1은 다음값을 만족시키는 가장 작은 정수가 된다. 따라서 x1 = b / a + 1의 값이 분자가 1이면서 가장 큰 단위분수를 구한것이다. 이 과정을 a가 1이 될때까지 반복한다. 코드 #include #include #include int gcd(int a, int b) { while(b!=0) { int c = a % b; a = b; b = c; } return a; } int lcm(int a, int b) { r..

문제 설명 문제를 이해하는데 조금 걸렸다. k번 이상 인용된 논문이 k편 이상이고 나머지 n − k 편의 논문들 인용회수가 각각 k 번 이하라면, 해당 학생의 q-인덱스는 k이다. 위의 말은 논문 인용 횟수를 오름차순으로 정렬하고(밑의 코드의 vector v), k가 인용횟수의 어느 위치에 있는지 찾아준다(내부 for문). 이 부분은 k를 기준으로 인용횟수의 왼쪽과 오른쪽이 나누어서 조건을 파악하기 위해서이다. 이부분을 만족하는 최대의 k값을 구한다. 코드 #include #include #include #include using namespace std; int main() { int n; scanf("%d", &n); vector v; v.resize(n); for(int i = 0; i < n ; ..

이 문제는 다이나믹 프로그래밍으로 분류되어있지만 문제의 이해와 원리를 파악하면 풀 수 있는 문제입니다. 이진포화트리는 Perfect binary tree로 불리며 꽉꽉채워진 이진트리 입니다. 자세한 설명은 다음링크로 남겨놓도록 하겠습니다. https://yaboong.github.io/data-structures/2018/02/10/1_binary-tree-1/ Binary Tree 종류 - Heap 구현 사전지식 개요 Heap 구현을 위한 Binary Tree 의 기초적인 개념에 대해 알아본다. yaboong.github.io 풀이 저는 weight와 node 두가지 vector를 int형으로 선언해 사용하였습니다. 먼저 weight에 각 edge들의 가중치를 입력받았고 node는 각 edge들의 we..

알고리즘 문제를 풀다보면 정렬을 해야할 때가 많으며 대부분 c++ 라이브러리를 사용하여 정렬을 하는 경우가 많다. 이번엔 sort함수를 간단하게 알아보고 정렬하기 위해 sort의 세번째 인자로 전달해 주는 함수 사용법을 알아보도록 하겠다. sort() 란 먼저 sort()를 사용하기 위해 algorithm 헤더파일을 include 해야한다. sort 함수는 내부적으로 IntroSort라는 정렬 방법으로 구현되어있다. 이 방법은 QuickSort와 HeapSort와 InsertionSort를 합쳐놓은 방식으로 평균 nlogn, 최악의 경우 n^2의 시간 복잡도를 가지는 QuickSort와는 달리, 최악의 경우에도 nlogn을 복잡도를 보장한다. https://en.wikipedia.org/wiki/Intr..

그리디 알고리즘 그리디 알고리즘은 탐욕 알고리즘이라고도 불리며 어떤 순간에 가장 최선의 선택을 하는것을 말한다. 특징은 local하게 최적의 선택을 하는것이 결국 global하게 최적의 해를 도출해준다. Activity-selection-problem이란? 그리디 알고리즘을 보여주는 한 예시이며 문제는 다음과 같다. 한개의 강의실에 n개의 수업들이 있다. 이때 각 수업은 시작시간 끝나는 시간이 주어진다. 이때, 한개의 강의실에서 수업이 최대 개수가 될 수 있도록 하는 수업 수를 찾으시오. 이때 문제를 해결하기 위해서는 끝나는 시간을 기준으로 오름차순 정렬한다. 그리고 겹치지 않는 선에서 수업을 선택하여준다. 다음은 위의 문제풀이 방식의 증명이다. 1 < x < y 이면서 수업의 최대 개수 집합이 A = ..

오늘은 터미널의 가독성을 높이기 위해서 새로운 테마를 적용해보도록 하겠습니다. 쉽게 이야기하면 맥북에서 제공하는 기본 terminal이 아니라 iTerm2이라는 새로운 Terminal을 다운받고 여기에 여러가지 테마를 적용할 수 있는것입니다. iTerm2 설치다음 사이트에 들어가서 다운로드 받으시면됩니다. (다른 기본적인 프로그램을 다운받는것과 동일)https://iterm2.com/ iTerm2 - macOS Terminal ReplacementiTerm2 by George Nachman. Website by Matthew Freeman, George Nachman, and James A. Rosen. Website updated and optimized by HexBrainiterm2.com Oh M..

Javascript의 Function에 대해서 알아보려고 한다. Javascript 함수는 일급 시민이기 때문에 변수에 함수를 대입 해줄 수 있다. 2021.09.12 - [IOS] - [Swift] 1급시민, 1급객체, 1급함수와 Closure란? [Swift] 1급시민, 1급객체, 1급함수와 Closure란? 1급시민 1급시민이란 다음과 같은 조건을 만족하는 것을 말한다. 혹시나 다음의 조건이 이해가 되지않는다고 해도 글을 읽으면 아래에 예시로 설명되어있으니 걱정하지 않아도 된다. 1급시민은 roadtosuccess.tistory.com 함수 선언하기 우리가 알고 있는 기본적인 C 함수의 함수 선언과 비슷하다. 하지만 차이점이라면 함수 header 부분에 return 값을 정의해 주지 않는다는 것이다..

1급시민 1급시민이란 다음과 같은 조건을 만족하는 것을 말한다. 혹시나 다음의 조건이 이해가 되지않는다고 해도 글을 읽으면 아래에 예시로 설명되어있으니 걱정하지 않아도 된다. 1급시민은 변수에 담아 사용할 수 있다. 1급 시민은 함수(혹은 메소드)의 매개변수로 전달할 수 있어야 한다. 1급시민은 함수(혹은 메소드)의 반환값(return)으로 전달할 수 있다. 1급객체 1급 객체는 위에서 언급한 1급 시민의 조건을 충족하는 객체이다. 예를 들어 javascript에서 객체(Object)는 1급시민의 조건을 만족하는 1급 객체이다. 1급함수 Swift는 1급시민의 조건을 만족하는 1급 함수이다. 따라서 Swift의 함수는 변수에 할당할 수 있다. func firstCitizenFunction(paramete..