세상의 모든 Software 지식을 정리

<문제> https://algospot.com/judge/problem/read/QUANTIZE <key 포인트> N개의 숫자를 S개의 묶음으로 묶어서 해결 할 것. 만약 첫 묶음의 크기를 x라고 한다면 이제 나머지 묶음의 크기는 n-x개의 숫자를 S-1개로 묶는다. 이때 나머지 S-1개의 묶음의 합이 최소 값이어 야한다. 구간의 오차제곱의 최소합 구하기( 한개의 숫자로 표현했을시) 예를들어 1,4,6을 4로 표현  b ∑(A[i]-m)^2=(b-a+1)^2*m^2 -2*( ∑A[i])*m+ ∑(A[i])^2  a 이를 미분해서 정리하면 결국 m=( ∑A[i])/(b-a+1)로 평균이 된다. 이를 일일히 구하면 O(n)시간이 들지만  O(1)에 계산 할 수도 있다. 바로 A의 부분합을 계산하면 된다. pSum[k]=i는 0부터 k 까지의 A[i]의 합이라 할때 pSum[b]-pSum[a-1]=i가 0부터 b까지인 A[i]의 합 - i가 0부터 a-1까지인 A[i]의 합으로 나타 낼 수 있다. 오차제곱도 일일히 계산하면 오래걸린다.  오차제곱의 합= i가 a부터 b까지 일때 (A[i]-m)^2을 더한 값으로 이는 상수인 A[i]^2의 합- 2*m*(A[i]의 합)+m^2(b-a+1)이다. 이때, 첫 인자와 두번째는 m과 관련없는 부분합으로 미리 계산해 둔다. public class Quantization { private static int N; //사이즈 private static int p; private static int A[]; private static int pSum[]; private static int pSqSum[]; private static int cache[][]; private static final int INF=9999; public static void main(String[] a...

짐멀락이란? 같은 방향으로 오브젝트의 두 회전 추이 겹치는 현상을 말한다. 간단설명하면 우리의 오브젝트가 회전하려고 하는 방향으로 오브젝트가 회전하지 않는 것이다. 이것은 회전행렬을 사용할 시에 주의해야 할 제약사항이다. 오일러 앵글을 사용하는 시스템들(마야,Max,Lightwave,softimgage)에서는 이러한 짐벌락문제를 가집니다. 이것이 생기는 이유는 오일러 앵글이 설정한 순서에 각 축을 독립적으로 평가하기 때문입니 다. 3DS Max는 회전순서가 X,Y,Z로 되어있습니다. 물론 이 순서는 여러분이 원하기만 하면 변경이 가능합니다. 어찌 됐든 X,Y,Z로 회전순서가 돼어있다는 것은 먼저 X축으로 오브젝트를 회전시키고 그 다음 Y축으로 회전하고 마지막으로 Z축으로 회전한다는 의미입니다. 이때 여러분이 Y축을 90도로 회전할 때 짐벌락이 발생합니다. 왜냐하면 X 성분이 이미 평가가 됐기 때문에, 다른 두축으로 이동되지 않습니다. 이렇게 되면 X와 Z축이 서로 같은 축을 향해 가리키게 됩니다. 여러분이 오일러 앵글을 사용한다면 여러분은 짐벌락 문제를 항상 염두해 두어야만 합니다. 오일러 앵글을 사용하면서 얻어지는 장점은 오일러 앵글을 사용하면 쿼터니언 회전보다 그래픽 아티스트들이 이해하기가 매우 쉽다는 점입니다. 쿼터니언 회전은 훨씬 더 강력하며 튼튼합니다. Max에서 ,TCB 컨트롤러는 방향을 구하기 위해서 쿼터니언 수학을 사용합니다. 쿼터니언 회전은 얼마큼 회전하는지를알려주는 행렬을 위해 4개의 값과 회전하려고 하는 방향을 구하기 위해 동시에 세개의 축을 평가합니다. 이렇게 쿼터니언을 사용하면서 얻는 이점은 여러분은 짐벌락에 대한 문제에 더 이상 고민하지 않아도 된다는 것입니다. 쿼터니언은 세개의 축이 동시에 업데이트 되기 대문에 짐벌락이 일어나지 않습니다. 물론 단점이 있는데 쿼터니언을 사용하게 되면 오일러 앵글보다 이해하기가 훨씬 더 복잡해지며 개념화하기가 어렵다는것입니다. max에서 회전 스크립트 컨트롤러는 오일러 앵글보다 훨씬 더 ...

*Atomic Operation의 사전적 의미. 기능적으로 분할할 수 없거나 분할되지 않도록 보증된 조작. 원자와 같이 분할할 수 없다는 것을 비유하여 원자조작은 끼어들기가 불가능하며, 만일 중지되면 동작 개시 직전의 상태로 시스템을 복귀시킬 것을 보증하는 복구(백업과 복원)기능이 제공된다. *Atomic Operation의 프로그래밍 언어적 의미 Atomic Operation이 필요한 부분은 멀티스레드 프로그램에서 공유자원들에 대해 여러 스레드가 동시에 액세스하는 경쟁상태(race condition)을 막기 위한 하나의 방법이다. 쉽게 말해 동기화를 위한 하나의 방법이다. 이것이 가능하려면 다음 두가지 조건이 반드시 만족해야 한다.   1. 모든 조작이 완료할 때 까지 어떤 프로세스도 변경을 알지 못하도록 비가시적이어야 하며   2. 조작중에 어느 하나라도 실패한다면 조작 전체도 실패하고 시스템의 상태를 조작 이전의 상태로 복구해야 한다. 외부에서는 조작의 집합이 단번에 성공하거나 실패하는 것으로 보인다. 그 사이에 어정쩡한 상태가 없어야 한다. 이것이 원자조작이다. 복수의 처리 장치가 있는 시스템처럼 복잡하지 않는 경우라도 이를 구현하는 것은 중요하다. 흐름제어의 변호의 가능성이 있는 한 원자성 없이는 시스템이 바르지 못한 상태로 빠질 가능성이 있다. -프로세스가 하나인 경우 예를들면 컴퓨터에서 메모리의 특정 위치에서 값을 1씩 증가시키는 프로세스가 있다고 치자. 메모리의 값을 1씩 증가시키는 절차는 다음과 같다. 프로세스는 메모리의 특정 위치에서 값을 읽어온다. 프로세스는 그 값에 1을 더한다. 프로세스는 새로 계산한 값을 메모리의 원래 위치에 써넣는다. -프로세스가 둘인 경우 이번에는 실행중인 두 프로세스가 공유하는 메모리의 위치에서 값을 1씩 증가시킨다고 해보자.   1. 첫째 프로세스는 메모리의 특정 위치에서 값을 읽어온다.   2. 첫째 프로세스는 그 값에 1을 더한...

경쟁상태 (Race Condition) 둘 이상의 입력이나 조작이 동시에 일어나 의도하지 않은 결과를 가져오는 경우를 말합니다. - 파일 또는 변수와 같은 공유 자원을 접근하는 하나 또는 그 이상의 프로세스들의 다중 접근이 제대로 제어되지 않은 것을 말합니다. -  프로세스들 끼리 하나의 자원을 갖기 위해 싸우는 것,  하나의 자원을 동시에 요청 교착상태 (DeadLock) 프로세스들이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태로, 시스템 자원에 대한 경쟁 도중에 발생할 수도 있고 프로세스간의 통신 과정에서도 발생할 수 있습니다. 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로는 아무것도 완료되지 못하는 상태 를 말합니다. - A프로세스가 A자원을 점유하고 B프로세스가 B자원을 점유한 상태에서 A프로세스의 다음 작업으로 B자원이 필요하고 B프로세스의 다음 자원으로 A자원이 필요할 경우, 서로의 작업이 끝나기만을 기다리며 아무것도 실행되지 않는 상태라고 할 수 있습니다. - 경쟁상태도 교착상태(DeadLock)의 종류 중 하나입니다. 교착상태 조건 -  상호배제  (Mutual Exclusion) : 한 순간에 한 프로세스만이 자원을 사용할 수 있다. 즉, 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수 없다. -  점유대기  (Hold and Wait) : 이미  자원을 보유한 프로세스가 다른 자원을 요청하며 기다리고 있다 . -  비선점  (No preemption) : 프로세스에 의해  점유된 자원을 다른 프로세스가 강제적으로 빼앗을 수 없다 . -  환형대기  (Circular Wait) :  프로세스간에 닫힌 연결 이 존재할 경우입니다. 블록된 프로세스가 자원을 점유하고 있는데 이 자원을 다른 프로세스가 원하며 대기하고 있는...

*가상함수 테이블: 부모클래스의 포인터에 할당 된 실제 객체가 무엇이냐에 따라 실행 할 함수가 정해진다. 각 함수는 다른 위치에 정의가 되어 있을것이다. 즉, 다른 함수를 실행 할 수 있다는 것은 각 함수의 위치를 구별 할 수 있는 방법이 있다는 뜻이다.     *가상 함수를 호출의 개요: @ 위 그림에서 B클래스를 D클래스가 상속받았고, b와d는 각 클래스의 객체이다. @ 포인터가 b객체를 가리키고 있다면 고민 할 것 없이 B클래스의 함수들이 실행된다. @ 포인터가 d객체를 가리키고 있다면 D클래스에서 재정의 된 함수는 D클래스의 것을, 그렇지 않은 것은 B클래스의 것을 실행합니다. @ 서로 다른 함수들은 임의의 위치에 각 본체가 정의되어 있고, 각 클래스 별로 자신의 각 함수가 어디서 실행해야 되는지가 정해져있고, 이 내용이 바로 '가상함수 테이블'이라고 불린다. @ 중요한 것은 !!!!!!!!!! 가상함수 테이블 자체는 클래스별로 하나씩 존재하는 것이지, 각 객체별로 존재하는 것이 아니다. 각 객체는 자신의 클래스의 가상함수 테이블의 포.인.터를 가지고 있다. @ 즉, 객체에 따라(객체의 클래스 종류에 따라) 가상함수 포인터가 가리키는 위치가 달라지고, 그 가상함수 테이블에 의해 객체별로 다른 함수를 실행 할 수 있게 되는 것이다. 이것은 상속의 단계에 상관없이 각 상속 단계별로 모두 적용되며, 역시 각 클래스별로 가상함수 테이블이 존재하고, 각 클래스의 객체는 가상함수 테이블을 가리키는 포인터, 즉 가상함수 포인터를 가지게 된다. 제가 만들었던 예제에서도 한번 그 실체가 정말 있는지 확인해 봤습니다. 폴리곤을 읽어 들이는 부분인데, 이 폴리곤 클래스는 가상함수를 가진 부모들로부터 상속을 받았습니다. 정말 이름도 위의 글처럼 __vfptr이라고 있군요. p.36  코드 상에서 인터페이스는 C++ 언어와 같은 객체지향 프로그래밍 언어에서의 순수한 가상 함수만을 멤버로 포함하는...

프로그래밍을 하다보면 클래스 내에서 동적 할당이 필요한 경우가 생긴다. 문자열의 경우가 대표적인 예인데, 이땐 필요한 만큼 char 배열을 할당해서 사용해야 한다. 문제는 객체가 복사될 때 객체가 가져야 할 모든 정보가 복사되지 않고 동적 할당한 메모리를 가리키는 포인터 변수(char* 등)만 복사된다는 것이다. 그래서 복사된 하나의 객체 내용을 변경하면 나머지 다른 객체의 내용도 변하게 되고 뜻하지 않은 자료의 변형을 초래할 수 있다. 더군다가 이런 버그는 찾기도 힘드니 애초부터 습관을 잘 들여놔야한다. 잠깐 여기서 질문! "그럼 const로 받으면 변형 못시키니 문제없지 않나요?" 물론 직접 접근을 사용한 변경은 할 수 없다. 하지만 멤버 함수에서 행하는 변경까지 막을 수는 없다 -_-; 그 예를 아래에서 살펴보자. 고객 관리 소프트웨어를 만드는 ABC사는 고객 정보를 저장하기 위해 Person 클래스를 만들었다. class Person { 　char *name; // 이름 　char *phone; // 전화번호 　int age; // 나이 public: 　void ShowData(); // 정보 출력 : 내용은 생략! }; 그리고 값을 입력하기 위해 생성자를 다음과 같이 선언하였다. 단, 이름과 전화번호의 길이가 일정하지 않기 때문에 동적 배열로 할당해서 저장하도록 하였다. Person::Person(char* _name, char* _phone, int _age) { 　name = new char[strlen(_name)+1]; // 길이만큼 배열 선언. +1은 널문자 공간 　strcpy(name, _name); // 입력받은 값을 복사해서 저장 　phone = new char[strlen(_phone)+1]; 　strcpy(phone, _phone); 　age=_age; } 동적 할당된 메모리는 사용 후 반드시 해제해줘야 한다. (그렇지 않으면 프로세스가 종료될 때 까지 메모리 공간을 차지하게 된다) 클래스 내에서 사용된 메모리는 클...

포인터가 여전히 해제된 메모리 영역을 가리키고 있다면 이를 댕글링 포인터(Dangling Pointer)이라 한다. 댕그링 포인터가 가리키는 메모리는 더 이상 유효하지 않다. 댕글링 포인터를 조숙한 해제라고 부르기도 한다. 댕글링 포인터는 다음과 같은 문제를 야기 한다. -메모리 접근시 예측 불가능한 동작. -메모리 접근시 segmentation fault -잠재적인 보안위험 이러한 유형의 문제는 다음과 같은 동작의 결과로 발생한다. -메모리 해제후 해제된 메모리에 접근 -함수 호출에서 자동변수를 가리키는 포인터의 반환 예제) int *pi=(int*)malloc(sizeof(int)); *pi=5; free함수로 메모리를 해제 한 후에도 변수 pi는 여전히 메모리의 주소를 가리키고 있다. 그러나 이 메모리는 힙관리자에 의해 재사용되거나 기존의 정수가 아닌 다른 타입으로 재사용 될 수 있다. free함수를 호출하면 원래 pi가 가리키고 있던 주소에 위치한 메모리는 해제되며 다시는 사용 할 수 없다. 그러나 대부분의 런타임 시스템에서 해제 뒤에 발생하는 메모리 접근이나 변경을 막지 않는다. 여전히 해당메모리에 접근하여 쓰기를 시도 할 수 있으며, 이러한 시도의 결과는 예측 할 수 없다. free(pi); *pi=10; 하나이상의 포인터가 같은 메모리 영역을 가리키고 그 중 하나가 해제된 경우에는 좀 더 복잡하다. 아래 변수 p1고 p2 둘다 같은 메모리 영역을 가리키고 있으며, 이러한 상황을 포인터 에일리어싱(Ailiasing)이라고 한다. 그런데 p1이 해제 되었다. int* p1=(int*)malloc(sizeof(int)); *p1=5; int* p2; p2=p1; ... free(p1); *p2=10; 이떄, p2는 댕글링 포인터이다. 또 다른 예제가 있다. 아래코드와 같이 블록 구문을 사용 할 때에도 다른 미묘한 문제가 발생한다. 변수 pi에는 tmp주소가 할당 되며, 변수 pi는 전...

                                                      예              난이도 모든 숫자가 같을 때                           333, 5555          1 숫자가 1씩 단조 증가하거나 감소할때       23456,3210     2 두 개의 숫자가 번갈아가며 나타날 때         323, 54545    4 숫자가 등차수열을 이룰 때                       14,8642        5 이 외의 모든 경우                                17912, 331       10 원주율의 일부가 주어질 때, 난이도의 합을 최소화하도록 숫자들을 세 자리에서 다섯자리까지 끊어 읽는다. 최소 난이도를 계산하라 예제) 5(입력케이스) 12341234 11111222 12122222 22222222 12673939 출력: 4 2 5 2 14 public cla...

참고 사이트: http://www.elex.pe.kr/entry/Java-cf-C-Sharp 클래스 / 인터페이스 Java 접근 키워드 public private protected static // 상속 class FootballGame extends Competition { ... } // 인터페이스 interface IAlarmClock { ... } // 인터페이스의 상속 interface IAlarmClock extends IClock { ... } // 인터페이스 구현 class WristWatch implements IAlarmClock, ITimer { ... } C# 접근 키워드 public private internal protected protected internal static // 상속 class FootballGame : Competition { ... } // 인터페이스 interface IAlarmClock { ... } // 인터페이스의 상속 interface IAlarmClock : IClock { ... } // 인터페이스 구현 class WristWatch : IAlarmClock, ITimer { ... } Java의 기본 접근 제한자는 동일 패키지 내에서 접근 가능인 반면, C#에서는 private이다. C#의 internal 키워드는 현재 어셈블리 내에서만 접근 가능하도록 지정하는 것이며, 어셈블리는 Java의 Jar파일과 유사한 개념이다. Java에서 클래스가 더이상 상속 될 수 없도록 지정하는 final 키워드 대신, C#에서는 sealed 키워드를 사용한다. Java에서 상속과 구현을 나타내는 키워드인 extends와 implements 대신, C#에서는 :을 사용한다. Java의 super 키워드 대신, C#에서는 base 키워드를 사용한다. Java와 달리, C#에서는 오버라이드 될 메서드에는 virtual 키워드를...

1. 순차컨테이너(Sequential Container)   * vectorl   * deque   * list   * array   * forward_list 2. 컨테이너 어댑터  컨터이너어댑터는 순차컨테이너를 이용하여 구현되어 있다.   *queue   *priority_queue   *stack 3. 연관컨테이너   연관컨테이너는 크게 map,set으로 구성되며   *map   *multmap   *set   *multset 4. 비순차 연관 컨테이너   *unordered_map으로 되어 있으나, hash라고 생각하면 된다.

1. 모든 답을 만들어보고  그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계 2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 대해 해당하는 점수 만을 반환하도록 부분문제의 정의를 바꾼다. 3. 재귀호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 문제의 최적부분구조가 성립할경우 이전 선택에 관련된 정보를 완전히 없앨 수도 있습니다. 여기서 우리의 목표는  가능한 한 중복되는 부분 문제를 많이 만드는 것입니다. 입력의 종류가 줄어들면 들수록  더 많은 부분 문제가 중복되고 ,따라서 메모제이션을 최대한 활용 할 수 있다. 4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모제이션 할 수 있도록 합니다. 5. 메모제이션을 적용합니다. 예) 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 1. 모든 경로를 만들어 보고 전체 합 중 최대치를 반환하는 완전 탐색 알고리즘 path1()을 만듬. 2. path1()이 전체 경로의 최대 합을 반환하는 것이 아니라 (y,x)이후로 만난 숫자들의 최대합만을 반환하도록 바꾼다. 3. 이렇게 반환 값의 정의를 바꿧기 때문에 이전에 한 선택에 대한 정보인 sum을 입력받을 필요가 없어진다. 이 정보를 받을 필요가 없는 것은 문제에 최적 부분 구조가 성립하기 때문입니다. 4. 메모제이션 적용. ---------->>>path(y,x,sum)=현재 위치가 (y,x)이고, 지금까지 만난 수의 합이 sum일 때, 이 경로를 맨 아래줄까지 연장해서 얻을 수 있는 최대합을 반환 path(y,x,sum)=max(path(y+1,x,sum+triangle[y][x]).path(y+1,x+1,sum+triangle[y][x])); path2(y,x)=(y,x)에서 시작해서 맨 아래줄까지 내려가는 부분경로의 최대합을 반환 path2(y,x)=triangle[y][x]+max(pat...

1. 템플릿 클래스 #include<iostream> #include<vector> using namespace std; template<typeame T> class MyArray {  private:   vector<T> list;  public:   void add_list(T const&);   void delete_last_list(void);   void show_list(void); }; template<typename T> void MyArray<T>::add_list(T const& element) {  list.push_back(element); } int main(void) {  MyArray<int> array1; array1.add_list(1); } ----->>>>>함수 템플릿과 비슷하지만 우선 클래스 멤버 함수를 정의할 때에도 template<typename T>를 다시 정의해야 한다 또한 MyArray::add_list(T const& element)가 아니라 MyArray<T>::add_list(T const& element)로 <T>가 정의 되어 있어야 한다. 또한 메인 함수에서는 MyArray<int> array1, MyArray<double> array2,가 되어야 한다. 2.1 템플릿 파라미터 여태까지 템플릿 파라미터가 typename으로 시작했지만 그렇지 않은 때도 있다. 이것을 non-type템플릿 파라미터라고 하는데 정수형 값, 나열형 값, 포인터 값, 참조형 변수와 같은 것들이다. template <typename T,int init> 예제) #include<ios...

**템플릿을 하면 코드의 재사용성이 높아진다. 참고로, 코드의 재사용성은 클래스 상속이나 오버로딩으로도 효과가 나타난다. <템플릿의 종류> 1. 함수 템플릿 2. 클래스 템플릿. (1) 함수 템플릿 함수 내에서 사용되는 파라미터의 데이터형을 추상화한 형태이다. 즉, 일반함수를 구현한 뒤 함수 내의 일부 또는 파라미터를 템플릿 파라미터로 치환하 것이다.  예) #include<iostream> using namespace std; int const add(int const& a,int const& b) {  return a+b; } int main() {  int i=5;  int j=10;  cout<<add(i,j)<<endl; } 만약 double형을 더하려고 한다면 함수를 다시 정의해야 한다. 이 문제를 해결하기 위해 템플릿을 사용해 보겠다 예) template <typename T> T const add(T const& a,T const& b) {  return a+b; } int main(void) {  double i=5.1;  double j=10.2;  int a=5;  int b=10;  cout<<i<<"+"<<j<<add(i,j)<<endl;  cout<<a<<"+"<<"b"<<add(a,b)<<endl; } 그러나 만약 add()인자에 int형과 double형을 넣으면 에러가 난다. 그런 경우는 다음과 같이 바꾼다. template <typename T,typename U...