나무 숲

https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 �� programmers.co.kr 예술적인 풀이를 봤음 https://leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-in-python [프로그래머스] 멀쩡한 사..

이진 트리 (Binary Tree) - 구현 배열 구현 이진 트리를 배열로 구성할 시 연결 리스트에 비해 탐색이 빠르고 쉽습니다. 위와 같은 이진 트리를 배열로 구현한다고 했을 때, 루트 노드를 배열 인덱스 0으로 설정 후 완전 이진 트리를 채워나가는 방식으로 인덱스를 부여합니다. (=다시 말하면 이진 트리에 노드가 추가될 때 그 순서를 뜻하는 것과 같습니다.) 따로 구현은 하지 않았는데 어떻게 생각해보면 트리라고 이해하기는 힘들 것 같습니다 ㅠ;; 연결 리스트 구현 연결 리스트를 통한 구현이 훨씬 더 트리의 모양을 잘 이해할 수 있는?? 구조라고 생각됩니다. 왼쪽에서 뻗어나오는 파란 팔은 양방향 연결 리스트를 생각했을 때 왼쪽 팔, 주황색 팔은 오른쪽 팔을 뜻합니다. 그냥 봐도 모양이 트리와 똑같기 때..

회문 Palindrome, 回文 회문(回文) 또는 팰린드롬(palindrome)은 앞에서 읽으나 거꾸로 읽으나 같은 문장이나 낱말을 뜻합니다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다..고 하지만 알고리즘 문제를 풀 때에는 고려하는 경우도 있으므로 문제 조건을 잘 읽어보는 것이 좋습니다. 한국어에서의 예 - 기러기 - 다 간다 이 일요일 일요일이 다 간다 영어에서의 예 - race car - A man, a plan, a caret, a ban, a myriad, a sum, a lac, a liar, a hoop, a pint, a catalpa, a gas, an oil, a bird, a yell, a vat, a caw, a pax, a wag, a tax, a nay, a ram,..

중국인의 나머지정리 Chinese remainder theorem 수론과 환론에서, 중국인의 나머지 정리(中國人-定理, 영어: Chinese remainder theorem)는 쌍마다 서로소 아이디얼들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 쌍마다 서로소 자연수들에 대한 연립 합동식의 해의 유일한 존재에 대한 정리이다. 역사이 정리는 원래 5세기 남북조 시대의 중국 수학서 《손자산경》(孫子算經)에 최초로 등장하였다. 《손자산경》 하권(下卷) 문제 26번은 다음과 같은 연립 합동 방정식에 관한 문제이다. 今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？ 개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센..

파도반 수열 Padovan sequence 1, 1, 1, 2, 2, 3, 4, 5, 7, 9... 위 그림과 수열로 구성된 문제가 국내 ACM 문제 중 하나로 나왔었습니다. 그림, 수열을 참고하여 정수 n을 입력했을 때 n번째 값을 출력하는 내용입니다. 수열의 초기값과 점화식을 알고 있으면 아아아주 쉽게 풀 수 있지만 그림과 수열로 유추하실 수 있으면 더 좋겠습니다! 파도반 수열이란?? Richard Padovan에 의해 이름붙었습니다. 위 그림은 파도반 수열을 표현하는 그림 중 하나입니다. 각 삼각형은 한 변을 두 개의 다른 삼각형과 공유하는데요, 초기값 P(0)~P(2)를 제외하고 P(n) = P(n-2) + P(n-3)임을 알 수 있습니다. * 초기값이 P(0) = P(1) = P(2) = 1인 ..

피보나치 수 Fibonacci Numbers수학에서 아래의 점화식으로 정의되는 수열이다. 피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다. * 피보나치 수열은 서로 인접한 항끼리 서로 소이다. 이것은 귀납법으로 간단히 증명할 수 있다. * 피보나치 수열의 인접한 두항의 비(fn +1 / fn)는 황금비(1:1.6180339887...)에 수렴하는 성질이 있다. 피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책이다. 유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다. n 번째 달의 토끼 수는 : 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다. 두 달 이상이 ..

카탈란 수 Catalan number 정의 조합론에서, 이진 트리의 수 따위를 셀 때 등장하는 수열입니다. 음이 아닌 정수 n에 대해서, n 번째 카탈란 수 Cn은 다음과 같습니다. 역사 18세기에 몽골의 수학자 명안도(c. 1692-c. 1763)가 최초로 발견하였습니다. 유럽 수학에서는 레온하르트 오일러가 "(n+2)-각형을 n개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났고, 벨기에의 수학자 외젠 샤를 카탈랑이 하노이의 탑 문제를 고려하면서 1838년에 재발견하였습니다. 응용 카탈란 수는 자연수열이며, n=0…37까지의 값들은 아래와 같다. (OEIS의 수열 A000108)1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 5878..

조오오오오오오오금이라도 시간을 단축할 수 있는 팁 모음입니다. 사실 이런 것들을 다 신경쓰는것보다 최적의 알고리즘을 짜는 것이 가장 효율적인 방법일 수 있지만.. 제가 생각하기에는 이런 것들도 어느정도 습관이 되어있는 것도 좋다고 생각해서 작성해 봅니다.. 일부는 저 스스로에게, 늘 쓰는 한가지 방법이 아니라 여러 방법으로도 같은 문제를 풀어낼 수 있음을 상기시키기 위해서입니다. 저와 같은 문제점이 있다고 생각하시는 분들께 도움이 되었으면 합니다. 새롭게 알아갈 때마다 추가 예정입니다. - 1. 2 또는 2의 배수로 나누기, 곱하기 연산을 할 때는 /, * 보다 shift 연산자 >>,

셀프 넘버 * 넥슨 입사 문제 중 가장 쉬운 문제라고도 알려진 내용이라고 합니다. 1949년 인도 수학자 D.R. Kaprekar가 이름 붙인 셀프 넘버란? 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의할 때, n을 d(n)의 생성자(Generator)라고 한다. 생성자가 없는 숫자를 셀프 넘버라고 한다. n이 주어졌을 때, n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예시 - d(75) = 75+7+5 = 87 이므로 87은 셀프 넘버가 아니다. - 생성자가 한 개보다 많은 경우 : 101 d(91) = 91 + 9 + 1 = 101 d(100) = 100 + 1 = 101 저의 모자란 코드 문제 : 1~100까지의 숫..

cmath에서 유용한 것들을 소개합니다. http://www.cplusplus.com/reference/cmath/?kw=cmath 위 레퍼런스에 보시면 훨~~씬 다양한 기능들이 많지만 자주 사용하는 것만! 왜냐면 저도 보기 위해서 입니다.1. C/C++ 제곱 표현 (Raise to Power)http://www.cplusplus.com/reference/cmath/pow/ pow(base, exponent) base^exponent의 값을 리턴합니다. 1) base가 유한한 음수이고, exponent가 유한하지만 정수가 아닐 때 domain error을 일으킵니다. 2) base, exponent 둘 다 0일 때 특정 실행에 대해 domain error을 일으킵니다. 3) base가 0이고 expone..

std::getline을 이용한다. // extract to string #include #include int main () { std::string name; std::cout

bool a = false; bool b = true; 일 때 cout

scanf("%s", str) ..... 는 적합하지 않다."%s" 는 whitespace(공백) 전까지의 문자열만 입력받기 때문이다. 1 fgetsgets()도 있긴 하지만 지양하는 편이 좋다고 한다.왜냐면! gets는 입력받는 문자열의 길이를 모르기 때문에 버퍼를 초과하여 char들을 저장할 수 있는데 이것은 위험하고.. 아무튼 뭐 하나라도 찝찝하면 안써야 뒤탈이 없다고 한다.공백을 포함한 문자열 = line을 읽고 싶다면 gets 대신 fgets()를 사용한다. fgets (str, 100, stdin);에서 알 수 있듯이 fgets의 매개변수로는 문자열이 저장되는 곳, 입력받는(stdin) 문자열의 최대길이(100)가 포함된다. 2 scanf [] scanf ("%[^\n]%*c", str); s..

소수 Prime number 양의 약수로 1과 자기 자신만을 가지는 자연수 따라서 1은 소수가 아님 에라토스테네스의 체 소수를 찾는 방법. 2부터 어디까지~의 소수를 구하는 데 편리함 물론 몇 번째 소수를 구하시오 등등의 문제.. 어쨌든 소수를 구하는 데 좋다. 아이디어? 소수가 아닌 수를 지워나가므로써 소수만을 남게 한다. (소수 아닌 숫자를 걸러주는 체) 위 그림을 보면서 설명하면, 2는 소수다->2의 배수들은 소수 아니므로 걸러냄->3 확인해보니 소수다->3의 배수들은 소수 아니므로 걸러냄->4는 아까 걸러졌으므로 5 확인->..... 반복 노가다로 코드짜면 나올 것 같다. 근데 수학적으로 나타내어진 공식이 있다. 덕분에 실행시간을 훨씬 줄일 수 있다. ▼▼▼ 소수는 n의 배수가 아니어야 한다. 다..

C++에서 제공하는 덱 라이브러리 사용법입니다. 앞뒤로 넣고 뺄 수 있는 방식의 덱입니다. 사용 #include deque dq //dq라는 이름의 (자료형) 요소들로 구성된 덱 선언 dq.push_back(값) //덱 dq의 뒤에 값을 넣는다. 리턴 값이 없다. dq.push_front(값) //덱 dq의 앞에 값을 넣는다. 리턴 값이 없다. dq.pop_back() //덱 dq의 back을 삭제한다. 리턴 값이 없다. dq.pop_front() //덱 dq의 front를 삭제한다. 리턴 값이 없다. dq.begin()/dq.end() //덱 dq의 시작과 끝을 iterator로 리턴합니다 dq.front() //덱 dq의 front를 리턴한다. front는 삭제되지 않는다. (peek기능) dq.ba..