거듭 제곱의 합 

 우리가 고등학교 수열과정에 배우는 내용중 하나인 거듭제곱 공식에 대해서 배운다.

 사실 많은 사람들이 이 공식에 관해서 머리속에 박아 외우고 있는 사람들은 많지만 정작 이런 공식들이 어떻게 나오는 지에 관해서는 모르는 경우가 많다.

1~n까지 모든 자연수들의 합을 나타내면

다음과 같이 표기한다. 보통 시그마라고 읽는다.  보통 우리들은 이 공식들을 외우고 있다.

혹시 이 공식의 증명법을 모르시는 분들을 위해서 한번 정리해 보자면 1)식과 2)식을 더하면 3)식이 나오는데 이때 (n+1)의 갯수가 총 n개 존재한다.(1~n이 n개존재하므로) 따라서 n(n+1)이된다.

그리고 그식을 정리하면 마지막 공식이 톡하고 튀어나오게 되시겠다.

이런 것들을 정리해 보자면

그런데 이게 4일때는? 5일때는? 6일때는?... k일때는?.... 

넘나 복잡한 것

이제 우리가 하고자 하는 일은 아래의 식을 모든 정수 k에대해 n에 관한 식으로 나타내는 것이다.

사실 여기서부터가 재밌다. 어떤 점화관계가 주어지면 재귀적으로 쉽게 풀 수 있는 문제들이 있다. 이는 재귀적으로 정의하고 그것을 정리하면 n에관한 식을 손쉽게 표현하고 구할 수 있을 것이다. 

우리는 문제를 풀기 앞서서 아래의 공식을 배운 적 있을 것이다.

위와 같은 식이 성립함으로 인해서 우리는 이 식을 가지고 장난을 쳐 우리가 원하는 바를 이루어 낼 것이다. 

(이 식을 처음 보시는 분들은 이항 정리에 관하여 검색해 보세요)

우리가 원하는 바를 이루기 위해서는 k+1에 관한 식이 필요하다. 그 이유는 포스트를 쭉 읽다보면 이해 할 수 있을 것이다. (k를 k+1로 치환하도록 하자)

이제 이 식에서 

을 좌항으로 옮길 것이다. 그렇다면 아래와 같은 식이 나타난다.

그리고 우리는 이식을 보면 하고 싶은 짓이있을 것이다. 계차수열의 일반항을 구할 때 했던 방법. 이제부터 x에 1부터 n까지의 수를 대입해보도록 하자.

이제우리가 할일은? 

다 더하기

그러면 좌측항이 아주 이쁘게 정리되면서 아래와 같은 식을 얻을 수 있다.

우리가 구하고 싶은 것은 S(n,k)이므로 이것에 대해 정리하기 위해서 S(n,k)만 우항에 놔두고 모든 식을 좌항으로 옮기도록 하자. 그렇다면

짜란 이제 우리는 임의의 k가 주어졌을때 S(n,0)~S(n,k-1)을 사용해 k일때의 n에 관한 식으로 만들 수 있다.

즉 점화식을 완성한 것이다 ^ㅇ^

식을 정리해서 만들었으니 k=2일때 제대로 정리 되었는지 보자.

완젼 잘나오네요 ㅎㅎ

k=3일때랑 k=4일때도 해보세요. 저는 귀찮아서 하기싫어여…

사실 이 문제에 관해서 점화관계뿐만 아니라 일반항을 나타낼 수 있다. 베르누이 수를 이용해서라고... 

수학자가 아닌 내가 이해하기는 힘든 증명이라 링크만 달아 놓도록 하겠다. 

Faulhaber's formula

능력자 분들 중 이글을 보게 되는 분이 있다면 저것에 관해서 설명좀 부탁드려요..

이것과 관련된 알고리즘 문제 풀어보기

.

이걸 계산하는 프로그램을 원하시면 코멘트 달아주세요. 만들어 드리겠습니다.

참고

http://blog.naver.com/dalsapcho/20141141955

딱히 필요해서 정리하는 것은 아닌데 이런 것이 정리하고 공유하는게 다른 분들이 공부하기 더 쉬울 것 같아 포스팅 한다.

1. dovelet : www.dovelet.com

더블릿은 부분유료 사이트이다. 모든 문제를 볼수는 있다. 다만 1,2,3계단만 공짜로 채점 받을 수 있다. 즉 4단계 이상의 문제를 제출해 볼 수는 없다. 1,2,3단계는 기본적인 입출력, 반복문등을 연습하는 기초적인 단계이므로 알고리즘을 공부하기로 마음 먹은 사람에게 거의 필요없는 문제들이 많기 떄문에( 물론 코딩 속도를 올리는 용도로는 효과적이라는 이야기도 있다. ) 사실상 유료사이트라고 봐도 될 것 같다.

특징

장점

1.  계단별로 특정 알고리즘의 설명, 수도코드, 소스코드등이 첨부되어 있어 혼자 공부하기 쉽다. 
2. 특정 알고리즘을 배운 다음에 그 밑에 그 알고리즘으로 풀리는 문제들이 있다. 그 문제들을 풀어보며 감을 익힐 수 있다. 
3.  만약 제출한 코드가 틀렸을 경우 틀린 testcase를 볼 수 있다. 

단점

1.  제출한 코드가 틀렸을 경우에 틀린 testcase를 보여주는게 항상 좋은 것은 아니다.(실전 처럼 연습할 때 불편할 경우가 많다.)
2.  테스트케이스가 빡빡하지 않다. 통과되지 말아야할 소스코드가 통과되는 경우가 왕왕 있었던 것으로 기억한다.
3.  제대로 공부를 할 요량으로 이 사이트를 사용하려면 3만원? 정도되는 가격을 지불해야한다. (평생 사용 요금이다.)

2. 백준 온라인 저지 : www.acmicpc.net 

백준은 완전 무료사이트로 모든 문제를 공짜로 풀어볼 수 있다. 유아이도 상당히 이쁜 편이다. 직관적이고 상당히 많은 문제를 풀어 볼 수 있다. acmicpc관련 문제 + 올림피아드 관련 문제들이 많아 이 쪽 준비를 하는 사람들에게는 상당히 도움이 되는 사이트다. 질문 게시판들도 있어 모르는 문제를 물어볼 수 있다. 갓갓갓님들이 잘 답변해주신다고....

특징

장점

1. 공짜다.
2. 문제양이 상당히 많다.
3. UI가 이쁘다.
4. 갓갓갓님들이 주로 상주하는 사이트이고, 또 질문을 올릴 경우 이 갓갓갓 분들이 답변을 잘해주신다.
5. 테스트 데이터가 빡빡한 편이라 어셉이 나지 말아야할 코드가 어셉이 나는 경우는 거의 없다. 있다고 해도 사람들이 찾아서 데이터를 보강해준다.  
6. 그룹을 만들어 아는 사람들끼리 가상의 대회를 열어볼 수 있다.

단점

1.  아직 분류 기능이 활성화 되어 있지 않아서 분류되어 있는 문제가 적다. 특정 알고리즘으로 푸는 문제를 분류탭에서 찾아보면 문제가 너무 적거나 말도안되게 어렵거나... 
2. 친구기능이 없다. ㅠ

기타

1. icpc.me/[문제번호] 라는 url로 접속하면 해당 문제로 바로 이동 가능하다.
    예) 자물쇠 문제 : icpc.me/1514
2. BOJ 슬랙이 있다. 질문을 게시판으로 해도되지만 슬랙에 올려도 된다. 슬랙에 올리는 편이 더 자세한 답변을 들을 수 있는 것 같다.  

3. UVA, live archive: https://uva.onlinejudge.org/ ,https://icpcarchive.ecs.baylor.edu/

 되게 짜증나는 외국 사이트인데 처음 시작하는 사람에게는 별로 추천해주고 싶지는 않다. 문제양은 정말 많지만... 데이터 자체가 틀렸을 경우가 왕왕이아니라 아주 많다. (정답인 코드가 틀린다던가 하는) 뿐만아니라 개행문제등을 이유로 틀렸습니다가 뜨는 문제들이 너무많다.(스트레스... ) 

특징

장점

1. 공짜다.
2. 문제양이 상당히 많다.
3. acmicpc관련 문제는 거의 대부분 있다.

단점

1. 내가 알기로 문제 분류기능 따위는 없다. UI도 불편... 
2. acm문제들 중 예선문제는 수록되어 있지 않다.
3. acm문제들이 대부분 수록되어있으나 데이터가 틀린 경우가 너무 많다.
4. 틀리기만 하는 것도아니고 데이터가 약한 것도 너무 많다.
5. 개행등으로 틀렸습니다가 뜨는 경우가 많다.

기타

1. 가상의 대회를 열어볼 수 있다. https://icpcarchive.ecs.baylor.edu/uhunt/
2. 근데 위에 저게... 시간이나 문제링크등이 이상하게 되어있다. 짜증남... 

4. codeforces, topcoder : www.codeforces.com  , www.topcoder.com

 온라인 저지라기보다 컨테스트 사이트다. codeforces는 러시아 것이고 topcoder는 미국 것이다. 문제는 둘다 영어로 제공되며 게임처럼 레이팅을 경쟁할 수 있다. 레이팅별로 색깔이 달라지는데 빨간색, 노란색, 보라색 티어(?)가 있다. 롤로 치면 마스터, 다이아, 플레티넘 같은 것이라고 보면 된다. 레이팅 올리는 재미가 있으며 정규 컨테스트에서만 레이팅이 변경된다. 둘다 가상의 컨테스트를 열어볼 수 있고 DIV1/DIV2로 나누어져있는데 DIV1은 상위리그, DIV2는 하위리그다. 처음 시작 하는 분들은 DIV2 대회로 시작하시면 되겠다.

특징

장점

1. 공짜다.
2. 게임처럼 참가할 수 있다. 롤 레이팅 올리는 느낌이다. 
3. 에디토리얼이라고 문제풀이가 제공된다. 따라서 보면서 공부할 수 있다.
4. 둘다 핵 개념이 있는데 컨테스트중에 제공되는 테스트 케이스는 약한 테스트 케이스다. 따라서 어셉이나도 최종적으로 어셉이 아닐 수 있다. 이런 부분 때문에 각별히 예외나 시간복잡도 신경써야한다. 다른사람이 여러분의 소스코드를 읽고 틀린 데이터를 만들어 여러분의 소스코드를 공개할 수 있다.
5. 반대로 문제를 잘 못풀어도 핵을 잘해서 점수를 딸 수 있다. 다른 사람의 소스코드에서 예외를 찾아 던지면 추가 점수를 얻을 수 있다.  

단점

1.  소스코드를 읽기가 힘들다. 각종 define과 typedef의 연속... 
2.  콘테스트에서 영어에 의해서 디버프를 받을 수 밖에 없다. 부족한 영어실력을 알고리즘 실력으로 극복해야한다. ㅠㅠ
3.  핵당하면 괜히 기분이 나쁘다.
4. 사이트가 빠른 편은 아니다. (아무래도 한 컨테스트당 몇천명의 사람이 몰리기 때문인 것 같다.) 

자세히 소개는 안했지만 다른  좋은 곳들도 많다. 

주로 사용하는 사이트만 리뷰하고 자주 사용하지 않은 사이트들은 정리하지 않았다. 잘못된 정보를 줄 수도 있기 때문에...

아래는 그외 사이트들이다.

알고스팟 : www.algospot.com 

수학관련 문제 - 프로젝트 오일러 :  http://projecteuler.net/ 

수학관련 문제 - 프로젝트 오일러(한국) : http://euler.synap.co.kr/ 

아주대학교 알고리즘 온라인 저지 라비다 : http://www.lavida.us/ 

시험기간엔 알고리즘이 재밌고 알고리즘을 해야할 땐 다른 개발이 재밌는 법이죠... 

그동안 미뤄뒀던 HTML, CSS, javascript 관련 글들을.. 아마 포스팅 할 겁니다. ㅎㅎ 

원 출처 : 모름

문제 링크 : 

https://www.acmicpc.net/problem/1514

문제 설명 : 

 숫자로 이루어진 문자열 2개가 주어지는데 첫 번째 문자열을 두번 째 문자열로 바꾸는데 드는 최소 코스트를 구하는 문제.

 문자열에 가할 수 있는 연산은 최소 1개에서 최대 3개를 선택해서 그 값을 한꺼번에 최대 1이상 3이하 증가/감소 시킬 수 있다. 물론 숫자는 0~9까지만 사용하며 0밑으로 내려가면 9로, 9 이상으로 올라가면 0으로 다시 돌아간다. 즉 숫자를 회전시키는 것이라고 볼 수 있다.

전처리가 좀 필요한데 다른 분들은 수식만으로 구하신 것 같지만 나는 멍청함으로 수식따위 구하지 않고 직접 bfs를 사용해서 구했다.

 가장 기초적인 전처리 방법은  

 pre[s1][s2][s3][t1][t2][t3] :: 세 다이얼이 s1, s2, s3일 때 t1, t2, t3로 변환하기 위한 최소 코스트

 근데 이걸 전처리하기 너무 귀찮다. 일단 더럽게 배열이 6차원이다. 

이 전처리를 줄일 수 있는데 s1, s2, s3, t1, t2, t3 정보가 모두 필요하지 않다는 데 핵심 아이디어가 있다. 실제로 필요한 정보는 (t1 -s1), (t2 - s2), (t3- s3) 정보다. 따라서 전처리 해야하는 내용을  

 pre[s1][s2][s3]  원래 다이얼로 부터 차이 값이 s1, s2, s3일 때 변환하기 위한 최소 코스트 

로 정의 할 수 있다. 물론 구현의 편의상 (-1 == 9) (-2 == 8) ... 이다. 따라서 s1, s2, s3 는 모두 0에서부터 9사이의 값을 가진다. 

dp 점화식 :

여기서 

n2 == 원래 다이얼의 n번째 숫자 

t0 == 목표 다이얼의 n-2번째 숫자

cost((s0,s1,s2) ->(t0,t1,t2)) 는 pre[t0-s0][t1-s1][t2-s2]이다.

디피 테이블 하나를 체우는데 10^2이 들고 모든 테이블을 체우기 위해서는 n*10^2이 드므로 시간복잡도는 n* 10^4 

상당히 많이 틀렸던 문제. 

이문제를 처음 틀리고 나는 완벽한데 틀렸다며 부들부들했던 문제다.

포스팅에 신경을 못쓰고 있었는데 요즘은...

공부도 귀찮고 그냥 현재 스터디 중인거나 공부했던 내용을 정리하는 용도로 블로그를 운영하기로 했당... 

넘나 귀찮은것... 

스터디 때도 진행된적이 있는 포스팅에 앞선 기본 지식들을 점검하는 시간이다. 

앞으로 C로 자료구조를 구현하는데 있어서 기본이 되는 

C를 처음 배우는 친구들이 모를 것 같은 문법과 기초 지식들을 소개해본다. 

1. 구조체(Structure Types)

구조체는 서로 다른 기본 자료형들을 한데 묶어 관리할 수 있게 도와주는 놈이다. 

구조체 없이도 자료구조를 구현하는데 문제 없을 수 있다. 

순수하게 배열과 동적할당, 그리고 로직들을 사용하여 자료구조를 구현할 수 있는데 그런 방식으로 코드를 작성하게 될 경우 코드도 읽기 힘들고, 짜는데도 시간이 오래걸릴 수 있다. 

즉 구조체는 여러가지 구현에 있어서 우리를 편리하게 해준다. 

구조체는 우리가 직접 정의한다는 관점에서 사용자 정의 자료형이라고 볼 수도 있는데 형태는 다음과 같다.

구조체에 대해 더 자세한 내용을 알고 싶은 분들은 다른 블로그나 구글을 참고하길 바란다.

2. 동적할당

동적 할당이란 런타임중에 원하는 메모리 공간을 할당받는 것을 말한다. 

막 프로그래밍을 시작한 사람들에게 말이 조금 어려울 수 있는데, 간단히 원하는 크기 만큼 그때 그때 메모리를 받을 수 있는 것이다...(전혀 간단하지 않은 것 같다..)

하지만 역시 이 포스트는 C언어의 사용법을 다루는 것이 아니므로 자세한 설명은 생략하도록 하겠다.

C언어 에서는 이 동적할당을 편하게 이용하기 위해서 대표적으로 2가지 함수를 제공하고 있는데 

malloc과 calloc이 그 두개다.

C언어에서 이 두 함수가 작동하는 방식은 다음과 같다.

시스템에게 원하는 만큼 메모리 요청하면 그 메모리만큼을 미리 힙에 할당하고 메모리의 시작 주소를 반환

단, malloc과 calloc의 차이점은 malloc은 해당하는 메모리 영역을 초기화 하지 않고 사용자에게 반환하고, calloc은 초기화(0으로) 시키고 사용자에게 반환한다는 사실이다. 

해당하는 메모리 영역을 어떤 방식으로 활용할지는 전적으로 사용자에게 위임하기 때문에 return형은 void * 형이다. 그래서 대부분 원하는 타입으로 케스팅해서 다시 사용한다.

이 두함수는 모두 stdlib.h 라는 헤더에 존재한다.

자세한 함수의 원형을 알고 싶은 사람은 

malloc <-클릭

calloc <-클릭

사용방식은 다음과 같다. 

 이 함수를 사용할 때 주의 할 사항은 일반 기본자료형과 다르게 구조체의 크기는 시스템마다 할당하는 크기가 다를 수 있다는 것이다. 그렇기 때문에 일반적으로 해당 자료형의 사이즈를 반환해주는 sizeof 연산자와 함께 사용한다.

  또 사용이 끝난 공간은 메모리를 해제 해 주기 전까지 영원히 남아있다. 반드시 사용이 종료되면 메모리를 해제해 주어야 한다. 이는 free함수로 메모리 해제를 시스템에 알릴 수 있다.

3. 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

시간 복잡도와 공간복잡도에 대해서는 굉장히 많은 내용을 설명해야 한다. 주로 다룰 내용은 빅-오 표현이 굉장히 중요하다.(사실 평균도 나름 중요하다.)

그래서 안할꺼다.  간단히 설명하자면 상수 때고 가장 크게 영향을 주는 식만을 시간 복잡도로 나타낸다. 보통 O(n),O(lgn) 등과 같이 나타낸다.

역시 구글과 다른 블로그들을 참조하길 바란다. 앞으로 대부분의 자료구조에서 연산을 정의할 때 그 정의된 연산이 얼만큼의 시간복잡도와 공간복잡도를 가지는 지를 소개할 텐데 꼭필요한 부분이다. 학습하고 오시길 ^ㅇ^ 

이부분은 나중에 따로 포스팅 할 수도 있다. 

잘못된 내용은 덧글로 알려주세요. 수정하도록 하겠습니다.

현재 학교 소모임에서 자료구조를 스터디 하고 있는데

학년도 4학년이기도 하고 다시 자료구조를 스터디하거나 

심도있게 다룰 것 같지는 않습니다. 

마지막이라는 심정으로 자료구조를 포스팅하도록 할게요.

아마 겨울 방학 때는 알고리즘 쪽 스터디를 맡을 수도 있는데

그렇게 되면 아마 알고리즘 관련 포스팅도 진행할 것 같아요.

자료구조 관련 포스팅은 기본적으로 C로 진행됩니다.

후반부로 가면  C++을 사용하긴 할 것 같습니다만... 가봐야 알겠네요.

포스팅 순서는 아마도

링크드 리스트

스택

큐

트리

힙

------------------------------------ 요기까지 C

그래프

최단거리알고리즘

MST알고리즘

------------------------------------ 요기까지 C++ 

이런 것들을 다룰 것 같습니다. 더 다룰수도 있고 아닐수도 있고... 

이제 여기다 포스팅해야징 ㅎㅎ

아마 주로 다룰 내용은 PS(problem Solving), game제작, it 가십거리 정도 될거같네요.