welcome!

백준 2*n 타일링본문보기https://www.acmicpc.net/problem/11726 dp문제. 경우의 수 문제이며, 점화식을 구하는 문제이다. 이 문제의 형식은 다음 문제와 유사하다. n 길이의 비트스트링 문자열의 경우의 수를 구하여라. 단 0이 두개 이상 연속하면 안된다.우선 n길이의 비트스트링 문자열 경우의 수는 2^n 이다. 그런데 0이 연속되면안된단다. 확실히 2^n보다 작을것 같지만 경우의 수가 몇개인지 모른다. 여기서 접근법은 이전 문제(1로만들기)처럼 차근차근 접근하는 것이다. 문자열 3일 때의 경우의 수를 생각해보자.문자열 3일때의 경우의수는 3번째 수가 1인경우와 3번째 수가 0인경우로 표현할 수 있다. 3번째 수가 0일때에는 반드시 2번째 수는 1이 되어야한다. 그리고 물음표인..

백준 1463 1로만들기https://www.acmicpc.net/problem/1463 해설dp로 불어보았다. 문제를 딱 봤을 때 우선 음.. 확실히 3으로 나누는 것이 이동수를 크게 줄이는 이득부분이니까 나누는게 좋다. 라고 생각했고, n에서 1까지 내려가는 것을 연산하였다.그런데 반례는 예제에서도 있듯이 10은, 10 ->9->3->1 이 최소이동이며 내가 생각한대로 하면10->5->4->2->1 이므로 이동횟수가 하나 더 많았다. dp의 배열을 이용하면서 1에서부터 차근차근 해당수로 올라가면서 1에서부터의 최소거리를 구한다면 우리가 원하는 방식으로 알고리즘은 동작한다. 어떤 수 n는 default로 하나 작은 수[n-1] 에서 1을 더한만큼의 거리를 가진다. 그리고 그게 2로 나누어지고 d[n-1..

경우의 수영어로는 Counting이다. 수 세기. 셈법. 조합론. 등 으로도 불린다. 조합론은 무엇인가?1 무엇보다 이산수학에서 굉장히 중요한 분야 중 하나다.2 비교적 최근 수학이다. 17세기 즈음에 도박 확률 문제와 연관되어 정립되었다.3 주로 특정 상태의 어떤 것들을 세는데 사용한다. 예) 2개 이상 연속하는 0을 포함하지않는 0과 1로만 이루어진 n길이의 문자열 갯수는?4 이론적인 곳 외에도 굉장히 다양한 곳에서 사용된다.예) 알고리즘의 복잡도 구하기, IP 수요와 그 할당의 문제, DNA 염기서열 등등의... 앗 복잡해 어찌됐든 알아보기로 하자... 경우의 수 기초컴퓨터를 사용할 때 패스워드를 생성하는 것을 생각해보자. 패스워드를 생성하는데 최소 1개의 숫자를 포함해야하고 최대 8자의 소문자 알..

다트게임난이도 : 5/10어렵다. 구현이라는게 생각보다 어렵다. 어떨 땐 기초 BFS, DFS, dp 등의 문제가 쉽다 ... 가끔은 그렇다. (-.-....)... 아래 시계문제를 포스팅해서 갑자기 기억나서 또 비슷한 원문제를 포스팅했다. 내용보기https://www.codeground.org/practice/practiceProblemView 설명흠... 두가지가 중요하다. 1 에 선언된 atan2 함수의 사용atan2 는 c에서 지원하는 (gcc에서는 -lm 옵션을 붙여야함) 함수이다. atan2 에 대한설명보기http://egloos.zum.com/ForJustin/v/1199696 360도를 표현하려면 " atan(y,x) * 360 / PI "를 사용하여야한다.y축이 음수일 땐 각도가 음수이므..

868B Race Against Time난이도 : 5/10구현이지만 까다로운 문제이다. 원을 이용해 문제를 푸는건 익숙치 않다. 차라리 backtracking, dp, BFS 등 등 알고리즘 문제가 더 쉬울정도. 컨테스트에서는 풀지 못하였다. 아마도 블라인드 입사문제 (카카오)의 구현 급 난이도였다. 문제보기http://codeforces.com/contest/868/problem/B Race against time 이란 뜻은 굉장히 짧은 시간내에 무언가를 해내려고 한다는 뜻이다. 일분 일초를 앞다퉈... 라는 것과 비슷한 뜻 어쨌든 각설하고... 문제의 주인공이 misha는 space-time paradox라는 상황에 처해있는데, 이는 시공간이 서로 대체되는 특수한 상황이다. 이 상황속에서 misha는..

Bark to Unlock난이도 3/10 까다롭다면 까다로울 수 있는 문자열 문제. 문제보기http://codeforces.com/problemset/problem/868/A 캡쳐하다가 뭔가 꼬여서 다날라가버렷다 ㅡ.ㅡ;; 대충씀Input 패스워드가 주워진다. (소문자 두글자) Kashtank가 짖을 수 있는 횟수가 주어진다. (1

Codeforces : Ordering Pizza난이도 : 6/10 (탐색은 탐색이였는데 해 탐색인줄 몰랐음 ㅅㄱ) 문제보기http://codeforces.com/problemset/problem/865/B 코딩대회가 시작했고, 참가자를 위해 피자를 주문하려고한다. (ㅇㅅㅇ!! 착한 대회인정) 피자는 2종류밖에 없다. (그래도 압도적인 감사 ㅠ.ㅠ) 그리고 모든 피자는 정확히 S 조각으로 이루어져있다.i 번째 참가자는 정확히 S[i] 조각을 먹을 것이고, 그리고 타입 1의 피자 "한조" 각당 a[i] 만큼의 기쁨이 상승하고 타입 2의 피자 "한조" 각당 b[i] 만큼의 기쁨이 상승한다고 알려져있다. 1타입과 2타입 피자는 어떤 갯수로도 주문 가능하지만, 모든 참가자들이 만족할 만큼의 피자를 먹을 수 있는..

Codeforces: Between The Offices난이도 2/10 문제 바로가기http://codeforces.com/problemset/problem/867/A 문제 소개MemSQL은 샌프란시스코와 시애틀에 미국지사를 가지고 있음. 너님이 매니저가 되었으므로 두 지사를 비행기를 타고 왔다갔다 많이 해야함.샌프란시스코가 따뜻하기 때문에, 너님은 보통 시애틀에서 샌프란시스코로 가는걸 좋아함. 너님은 조낸 바쁘기 때문에 비행기를 총 몇번 탔는지는 기억 못 하지만, 최근 n 일 동안 샌프란시스코 지사에 있었는지 시애틀지사에 있었는지는 기억을 할 수 있음. 항상 밤에만 비행기를 타고 이동하기 때문에, 같은 날에 두 지사에 있는 것은 있을 수 없음. 아래와 같은 input이 주어졌을 때 n일동안 시애틀에서 ..

이전글 보기 알고리즘 Introduction + 알고리즘의 특징http://ingyeoking13.tistory.com/75 Contents탐색알고리즘 (순차탐색, 이진탐색) 정렬알고리즘 (버블정렬, 삽입정렬) 탐색 알고리즘Searching Algorithms정렬된 리스트에서 어떤 원소를 찾는 문제는 많은 상황에서 발생합니다. 예로, 사전같이 순서대로 정렬되어있는 단어 리스트들 중에서 단어 탐색을 하기위해 스펠링을 체크하는 프로그램이 있습니다. 이런 류의 문제들은 탐색 문제searching problems 입니다. 우리는 이 섹션에서 탐색을 위한 몇 몇 알고리즘들에 대해 논의할 것입니다. 일반적인 탐색 알고리즘은 다음과 같이 서술될 수 있습니다. 각 각 다른 원소들 a1, a2, .... , an 의 리..

스택 2개로 큐를 구현하기 스택 2개로 큐를 구현하다구? 뭔 개소리야... 라고 생각한다면.. 이 문제를 처음접했었던 저의 반응과 같아요 ^~^ 아래를 참고합시다. http://creatordev.tistory.com/83 http://www.geeksforgeeks.org/queue-using-stacks/ 즉 큐를 구현하고싶은데 스택두개를 쓴다는 거구요, 스택 한개는 큐에 푸쉬 전용으로 (enqueue) 다른 스택은 dequeue 전용으로 쓴다는 겁니다. 1 개요아래는 구조체와 메인함수, 구현 내용입니다. 2 queue init 3 enqueue enqueue 는 기본적으로 stack 푸쉬해줍니다. 저는 s1에 푸쉬를 해주었습니다. 4 dequeuedequeue는 기본적으로 stack에서 팝하는것입니..