추후 원본 내용을 수정하여 업로드할 계획입니다...! 이항계수 피보나치 수열 행렬 곱하기 알고리즘 다이나믹 프로그래밍 예제

문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그..

문제 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. 입력 첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. 문제 링크 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 가장 처음 생각한 것은 자릿수에 따른 숫자 등장 횟수였다. 1234라는 수를 생각해보자. 1부터 이 수에 도달할..

문제 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 ..

개요 내용은 추후 추가될 예정입니다...! 더하기 / 곱하기 알고리즘 이진 탐색 합병 정렬 허프만 부호화

개요 트리(tree) 구조는 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 말이 조금 어렵게 되어 있는데, 좀 더 쉽게 말하면 현재 노드를 떠나면 같은 길을 되돌아오는게 아닌 한 현재 노드로 돌아올 수 없다는 것이다. 버스를 탄다고 했을 때, 보통 반대 차선으로 가면 똑같은 버스가 있기 마련인데 가끔 편도로 가는 버스들이 있다. 일단 위의 말이 이해가 안된다면, 트리 구조를 편도로 가는 버스 정도로 이해하고 들어가자.▼ 앞에서 트리에 대한 설명으로 `순환이 없는 연결 그래프`라고 했다. 트리와 그래프와는 별개의 자료구조로 느껴지지만, 트리는 따지고 보면 그래프의 한 종류가 될 수 있다. 다만 그 특수성이 짙은 자료구조로서 그래프와 따..

개요 자료구조(data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 집합을 의미하며 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 말한다. 자료구조가 필요한 이유 데이터를 효율적으로 저장, 관리하여 메모리를 효율적으로 사용하기 위해서이다. 적절한 자료구조의 사용은 메모리의 용량을 절약해주고, 실행시간을 단축시켜줄 수 있다. 자료구조의 선택 기준 작업의 효율성, 추상화, 재사용성을 증가시키기 위하여 상황에 따른 적절한 자료구조의 사용이 필요하다. 따라서, 아래의 사항을 구려하여 자료를 좀 더 효율적으로 처리할 수 있도록 한다. 자료의 처리시간 자료..

개요 연결 리스트와 배열은 다른 자료구조를 구현할 때 기본이 되는 자료구조로 많이 사용이 되며 서로 비교되는 일이 많다. 스택, 큐, 덱과 같은 선형 자료구조들의 기본이 된다. 기초적인 단계의 자료구조들은 배열로 구현하기가 쉬워서 보통 배열로 많이 구현해보는데, 배열의 단점(후에 이야기 할 것이다.)으로 인해 이를 보완하고자 연결리스트를 사용하기도 한다. 둘 중 무엇을 사용하느냐는 자유지만, 둘의 특성을 잘 알아두고 상황에 맞게 응용하는 것이 가장 좋아보인다.▼ 배열(array) 배열이란? 배열(array)은 연관된 데이터를 하나의 변수에 그룹화 하여 관리하는 자료구조이다. 말이 조금 어려울 수 있는데, 다들 알다시피 같은 데이터 타입 변수들을 모아놓은 것이다. 좀 더 세부적이고 명확하게 설명을 하자면,..

개론 정렬에는 여러가지 뜻이 있는데 대체로 "가지런히 줄지어 늘어섬. 또는 그렇게 함" 혹은 "영역, 항목, 데이터 따위를 미리 지정된 양식으로 맞추는 일." 등의 의미를 말한다. 어떻게 보면 우리가 정리하는 것과 같은 얘기를 하는 것이다. 우리가 현실 세계에서 책장을 정리한다고 했을 때 어떻게 정리하는가에 대해서 생각해보자.▼ 책의 개수가 많지 않고 책장에 들어갈 자리가 넉넉하게 있다면, 크게 뭔가를 생각하지 않고 노동요를 틀고 하나씩 책장에 넣을 것이다. 그러면 컴퓨터에게 책 정리 시뮬레이팅을 시킨다고 해보자.▼ 컴퓨터는 우리의 행동 하나하나를 전부 생각하고 있어야한다. "책을 빼서 어디에 놓지?" "책장의 전체 크기가 어느정도지?" "이 책이 저 책보다 우선순위가 높은걸까?" "이 책은 전체 책 중..

개요 Swift로 PS를 한다는 것 Swift로 PS를 한다는 것은 직진할 수 있는 길을 한 바퀴 돌아가거나, 평범한 길 대신에 가시 밭길을 걷거나, 그냥 스스로를 고문하는 그런 것과 비슷하다. ▼ 사실 Swift로 PS를 한다고 하면 조금 말리고 싶지만, 대부분이 하고 싶어서 하는게 아니라 iOS 개발자로 취직할 때 Swift로 PS를 하지 않고 다른 언어로 하면 쿠사리를 먹는다는 정보를 듣고 하는 것임을 알고 있다. 그게 아니라 재밌어서라던가, 언어가 잘 맞는다는 이유면 굳이 말릴 필요가 없는거 같다. 약간 고통을 좋아하는 사람인가 생각한다. “그러는 너는 왜 Swift로 하는거냐” 그야… 재밌으니까…! 필자의 경험 필자는 솔직히 PS를 잘 한다고 하기는 힘든 레벨에 위치해있다. 하지만 C++과 Sw..