huiyu's blog

일반적인 방법, n까지 for문 돌면서 나머지가 0인 i의 합을 구하면 된다. 이 때 진약수는 대칭적으로 나타나기 때문에 n/2이후는 중복 계산이 된다. n/2까지만 for문을 돌린다. #include using namespace std; int main() { int n, m; int sum = 0; cin >> n; for (int i = 1; i

-비트연산 : 한개 혹은 두개 이진수에서 비트단위로 적용되는 연산 1. AND(&) - 두 값의 각 자릿수를 비교해, 두 값 모두에 1이 있을 때에만 1을, 나머지 경우에는 0을 계산한다. : 0100 & 1100 = 01002. OR(|) - 두 값의 각 자릿수를 비교해, 둘 중 하나라도 1이 있다면 1을, 아니면 0을 계산한다. : 0101 | 0011 = 01113. XOR(^) - 두 값의 각 자릿수를 비교해, 값이 같으면 0, 다르면 1을 계산한다. : 0001 ^ 1111 = 11104. NOT(~) - 각 자릿수의 값을 반대로 바꾸는 연산이다. : ~1(0001) = 1110 비트연산의 활용1. Flag처리 : 비트를 이용하여 상태처리, 4Byte = 32Bit, 32개의 상태 처리 가능왜 ..

연쇄행렬 최소곱셈 알고리즘 두 개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구하는 문제-> 행렬의 곱셈은 아래와 같이 결합법칩이 성립한다. A*(B*C) = (A*B)*C 그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.예를들어 설명하면, 행렬 A,B,C,D 4개가 존재한다. 각각 행렬의 차수는 20x1, 1x30, 30x10, 10x10이라고 한다. 4개의 행렬은 여러가지 방법으로 곱할 수 있지만, 다음 4개의 경우에 대하여 생각해볼때, 곱셈 횟수를 비교하면 아래와 같다.((A*B)*C)*D) = (20*1*30) + (20*30*10) + (20*10*10) = 8,600 A*(B*(C*D)) = (30*10*10) + (1*30*10) + (20*1*10) = 3,500 (A*B)*(C..

해시테이블(Hash Table)이란?Key값에 Value를 저장하는 데이터 구조로 key값을 통해 데이터에 접근하게 됩니다. 그렇기 때문에 상수시간에 접근이 가능하여, 탐색이 빠르단 장점을 갖고있습니다.만약 10개의 데이터 순서대로 0~10의 id값을 갖는 데이터를 해시테이블에 저장한다면, table[1] = id(1) table[2] = id(2) table[3] = id(3) table[4] = id(4) ... table[9] = id(9)와 같이 순차적으로 저장이 되서 id 5인 값을 찾을 때 table[5]의 값을 주면됩니다.코드로 간단히 구현하면 id에 따라 아래와 같이 table에 저장하면 되겠죠.12345678910111213141516171819202122#include#define MA..

Queue(큐)는 선입선출(FIFO; First In First Out)의 자료구조로 데이터들이 들어온 순서대로 처리되는 구조를 말합니다. 데이터 삽입이 들어오는 back/rear 부분과 데이터가 나가는 front 부분이 있습니다. 입력 동작은 Enqueue, 출력동작은 Dequeue라고 합니다. 스택과 마찬가지로 연결리스트만 완벽히 이해한다면 구현하기 쉽습니다 -> 연결리스트 구현하기 큐 구현먼저 Node와 Queue를 만듭니다. Queue에서는 데이터를 추가할 부분인 back, 데이터를 가져올 부분인 front를 갖고 있습니다.123456789101112typedef struct Node{ int data; Node *next;}Node; typedef struct Queue{ Node* front;..

Stack(스택)은 모든 원소들의 삽입과 삭제가 한쪽 끝에서만 수행되는 선형 자료구조를 말합니다. 삽입/삭제가 일어나는 부분을 top이라고 하며, 이 부분에서 삽입(Push)과 삭제(Pop)이 일어난다. Peek은 top의 데이터를 확인하는 연산. 후입선출(LIFO; Last In First Out), 나중에 들어온 데이터가 먼저나가는 자료구조입니다. 아래 그림고 같이 'Top'에서 Push와 Pop 연산이 일어나며, 각 노드는 이전의 노드를 가르키고 있게 구현하면 됩니다. 스택을 배열로 구연할 경우는 간단합니다. 배열을 하나 생성 후, top이라는 변수를 통해 삽입/삭제 시 top을 통해 데이터에 접근하면 됩니다. 동적 할당으로 구현하기, 결국엔 연결리스트를 잘 활용하면 스택/큐의 구현은 쉽습니다 ->..

리스트(List) - 자료구조의 하나, 데이터를 일렬로 순차적으로 나열한 형태리스트를 구현하는 방법에는 배열을 이용하는 방법과 동적할당을 이용해 구현하는 방법이 있습니다.배열로 구현할 경우,구현이 간단하고, 인덱스를 참조하여 한번에 참조가 가능하다는 장점을 갖고 있지만, 갯수에 제한이 있어 유한적인 데이터만 넣을 수 있다는 단점을 갖고 있습니다. 동적할당으로 구현을 할 경우,새로운 자료가 입력될 때마다 새로운 주소로 메모리를 할당해주고 이전에 할당된 메모리를 연결해주므로 메모리 관리에 용이하다고 볼 수 있습니다.그래서 연결리스트(Linked List)란 각 노드가 데이터와 포인터를 갖고 있어, 각 노드가 다음 순서의 노드의 위치정보를 갖고 있는 방식으로 데이터를 저장하는 자료구조입니다. 연결리스트엔 세가..

백준 기업투자 문제 : https://www.acmicpc.net/problem/2662 문제 요약- 일정금액을 기업들에게 돈을 투자해서 최대 이익을 얻고자한다.- 투자액이 정해져 있고 기업의 개수와 기업에 투자할 이익이 주어질 때, 가장 많은 이익을 얻을 수 있는 투자방식과 이익금을 구하기위의 경우 최대 이익을 얻는 경우는 B기업에만 4만원을 투자하는 경우 15만원입니다. 우선 문제의 기본 입력을 받고 필요한 함수를 구현합니다.123456789101112131415161718192021222324252627282930#include using namespace std; int arr[301][21];int DT[301][21]; int M, C; int MAX(int a, int b){ return (..

백준 9465번 스티커 문제 풀이 : https://www.acmicpc.net/problem/9465 문제요약 : - 2xn개의 스티커를 갖고있다. 각 스티커는 점수가 있다.- 스티커를 떼면 그 스티커와 변을 공유하는 스티커는 찢어져 사용할 수 없다(점수x)- 뗄 수 있는 스티커 점수의 최댓값을 구하시오. 우선 이런 유형의 문제는 완전탐색을 하여 구현을 해봅니다.. 그다음 DP를 적용.. 1. 완전탐색을 할 경우를 생각해봅니다. "-->" 오른쪽 방향으로 탐색을 했을 때, 스티커를 떼는 방법은 위를 떼는 방법, 그리고 아래를 떼는 방법 두가지가 존재합니다. 우선 공유하는 변의 스티커가 뜯어지는 경우를 무시하고 전체 경우를 구한다면, 아래와 같이 구현할 수 있습니다. 12345678int solve(in..

배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다 배낭에 짐을 넣을 때,짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데, 쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem),쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부릅니다. 쪼갤 수 없는 0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다. -> 위키백과 냅색 문제는 아래 링크에서 풀어 볼 수 있습니다. ->0/1 Knapsack 문제 보러가..