키보드워리어

백준코딩에서 발견한 배낭문제입니다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 배낭문제에서 최소 물품을 가지고 가장 가치 있는 물건을 가져갈 때 최대 이익을 구하는 문제예요. 이번에 알고리즘을 아주 살~~ 짝 터치해 보면서 범접해 볼 수 없는 어려움을 느꼈더랬죠.. ㅎㅎ;; 위 문제와 같은 문제인데 한번 아래 문제를 풀어볼까요? 문제 풀어보기 [01] 용량이 20인 배낭이 ..

[01] 주어진 데이터를 퀵정렬 해보자. A [] = {30, 35, 50, 45, 10, 20, 70} 먼저 퀵정렬이란 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고 부분배열에 대해 퀵정렬을 순환적으로 적용하는 분할 정복 알고리즘을 사용하여 정렬을 수행하는 방법입니다. 두 부분배열로 분할할 때 기준이 되는 특정 원소인 피벗으로 지정하는데 일반적으로는 첫 번째 요소(30)를 선택합니다. 그리고 피벗을 기준으로 배열을 분할합니다. 피벗보다 작은 요소는 왼쪽 배열, 큰요소는 오른쪽 배열에 배치합니다. 왼쪽 모든 값 < 피벗 < 오른쪽 모든 부분배열의 모든 값 이렇게 정렬하면 {10,20} 30 {35,50,45,70} 이렇게 정렬이 됩니다. 그러면 분할된 두 배열에 대해 퀵정렬을 순환적으로 적용..

안녕하세요 【키보드 워리어】 ⌨🗡🧑 블로그 방문자 여러분, 안경닦이입니다. 오늘은 지난 시간에 이어서 컴퓨터과학 개론 기출문제를 정리해보는 시간 가져보겠습니다. 기출문제 - 2 [05] 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관 없이 각 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택해서 결과적으로 전체적인 최적해를 얻는 전략을 사용하는 방법은? 보기 (1) 동적 프로그래밍 방법 (2) 욕심쟁이 방법 (3) 분할정복 방법 (4) 희귀 분석 방법 [정답]: 2번 우리가 풀고자 하는 문제와 제반 조건이 매우 다양하기 때문에 모든 문제 혹은 대부분의 문제에 대해서 일반적으로 적용할 수 있는 알고리즘 설계 기법은 존재하지 않습니다. 하지만 비교적 단순하면서 많은 문제에 사용가능 한 기..

안녕하세요 【키보드 워리어】 ⌨🗡🧑 블로그 방문자 여러분, 안경닦이입니다. 여러 문제들을 접하면서 풀어보는 맛이 있어 살펴보도록 하겠습니다 [01] 컴퓨터에서 처리 가능한 작업의 유형과 연산의 집합을 결정하며, 이를 통해 컴퓨터를 다양한 형태의 작업을 처리할 수 있는 범용의 기계로 만들어주는 역할을 하는 것은? (1) 프로그램 (2) 인터넷 (3) 데이터 (4) 정보 [정답]: (1) 프로그램 ※ 컴퓨터를 이용해서 어떤 작업을 처리하기 위해서는 우선 해당 작업에 대한 프로그래밍 과정을 거쳐야 합니다 즉 , 문제를 어떻게 해결할 것인지에 대한 방법과 절차를 찾고, 이것을 컴퓨터가 이해할 수 있는 형태로 표현하는 단계를 거쳐 프로그램을 완성합니다 [02] 여러 진법의 숫자 중에서 나머지와 다른 값을 나타내는..

안녕하세요 【키보드 워리어】 ⌨🗡🧑 블로그 방문자 여러분, 안경닦이입니다. 정렬 알고리즘 알고리즘은 주어진 문제에 대한 하나 이상의 출력 결과를 생성하기 위해 모호함이 없는 간단하고 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것입니다 그중에서 정렬(sort)이란 컴퓨터 과학에서 가장 많이 사용되는 응용 중의 하나로서, 주어진 데이터를 일정한 기준에 따라 순서 있게 재배열하는 연산입니다 정렬 방법은 정렬이 수행될 당시 데이터가 어디에 저장되어 있느냐에 따라 크게 두 가지 방법, 즉 내부 정렬(internal sort)과 외부 정렬(external sort)로 나눌 수 있는데요 내부정렬은 정렬할 데이터의 양이 충분히 크지 않기 때문에 모든 데이터를 주기억장치에 적재해서 정렬하는 방법으로 ..

안녕하세요 【키보드 워리어】 블로그 방문자 여러분, 안경닦이입니다. 오늘은 알고리즘 에 대해 알아보겠습니다. 알고리즘이란 서론:알고리즘(algorithm)은 수학과 컴퓨터과학에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차입니다. 알고리즘은 전산학, 컴퓨터과학, 언어학 등에서 핵심적인 과목으로, 적절한 자료구조와 적절한 알고리즘이 있다면 좋은 소프트웨어가 됩니다. 그러므로 알고리즘에 관한 내용들은 컴퓨터의 전 분야에서 기본적이며, 필수적이라고 할 수 있는데요. 앞으로 알고리즘으로 정렬, 탐색, 그래프 등주요 알고리즘 설계 및 분석 방법을 포스팅하도록 노력하겠습니다. 문제 해결들을 위해 여러 동작과 반복들을 정리하면 시간 복잡도와 공간 복잡도를 어느 정도 이해해볼 수 있습니다. 알고리즘의 수행 시간을 ..