while (1): study();

링크: https://algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 동적 계획법으로 풀 수 있는 대표적인 문제입니다. 동적 계획법으로 최적화 문제를 풀때, 다음과 같은 절차를 밟는다고 생각하면 편합니다. 완전 탐색으로 설계 (최적 부분 구조) 최적화 문제로 부분문제 변환 메모이제이션 적용 아래 코드들은 다음과 같은 절차에 의해 LIS(Longest Increasin..

링크: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt 자료형별로 정리되어 있어 참고하기 용이하다.

링크: https://www.algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 www.algospot.com 동적 계획법이란 완전탐색 알고리즘에서 중복되는 부분문제를 메모이제이션으로 해결하는 것을 의미합니다. 동적 계획법 알고리즘을 계획할 때는 몇 가지 중요한 조건이 있는데, 하나는 참조 투명성이며 다른 하나는 최적 부분 구조(optimal substructure)입니다. 최적 부분 구조란 부분문제의 최적..

링크: https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com 완전탐색은 문제의 한 조각을 풀고 나머지 문제의 처리를 재귀함수에 맡길 수 있다. 나아가 분할정복 알고리즘은 부분문제의 결과를 조합하여 원하는 답을 도출한다. 동적 계획법은 분할정복에서 한발 더 나아간다. 분할정복으로 접근가능한 어떤 문제들은 중복되는 부분문제(overwrapping subproblems)가 생긴다. 이 경우 따로 처리해주지 않으면 같은..

알고리즘 공부를 하다보면 온라인저지에 올라온 많은 문제를 풀게 됩니다. 그러나 일반적으로 sys.stdin.readline() 명령어를 사용하여 입력을 받는 실제 코딩테스트와는 달리 문자열을 다른 방식으로 전처리하거나 매번 수기로 입력해주어야 하여 실제 테스트와 연습 간의 괴리가 발생합니다. 이럴 때 다음과 같이 클래스를 활용하면 연습과 실제 간의 괴리를 최대한 해결할 수 있습니다. class Input: def __init__(self, txt): self.txt = txt self.idx = 0 def __len__(self, line): return len(line) def __getitem__(self): ret = self.txt.split('\n')[self.idx] self.idx += 1 ..

https://www.algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 www.algospot.com 해당 문제의 풀이에는 분할 정복을 사용합니다. 분할 정복이란 문제를 더 작은 부분문제들로 나누고, 부분문제들의 결과를 적절히 조합하여 전체 정답을 도출하는 과정입니다. 흔히 알려진 바로는 분할(divide) - 병합(merge)의 단계를 거쳐 푼다고 합니다. 쿼드트리 자체가 재귀적으로 정의되어 있기 때문에 재귀 호출을 사용하여 압축 혹은 ..

링크:https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 완전탐색은 가능한 모든 사건을 탐색하는 알고리즘입니다. 모든 것을 탐색한다는 워딩부터 왠지 계산이 힘들 것 같습니다. 그러나 많은 경우에 그렇지만, 항상 그런 것은 아닙니다. 입력 자료가 많지 않을 경우 오히려 더 빠를 수도 있으며, 처음에 문제에 접근하기 위한 좋은 직관을 제공하기도 합니다. 특히 ..

LNK2019는 보통 두 가지 상황에 발생한다. lib 파일이 선언되지 않은 경우 함수가 선언만 되고 정의되지 않은 경우 필자 같은 경우 두 번째 케이스였다. 함수 정의를 지웠는데, 선언 부분에서 지워주지 않아서 오류가 발생했다. 선언된 함수와 정의된 함수 목록을 맞춰주니 오류가 해결되었다.

복사 생성자는 메모리 공간의 할당과 초기화가 동시에 일어나는 상황에 호출된다. 좀 더 디테일하게는 세 가지 상황으로 나누어진다. 기존에 생성한 객체로 새로운 객체를 초기화하는 경우 call-by-value 방식으로 객체를 함수의 인자로 전달하는 경우 함수가 참조형이 아닌 객체를 반환하는 경우 1. 기존에 생성한 객체로 새로운 객체를 초기화하는 경우 Object obj2 = obj1; Object obj2(obj1); 가장 대표적인 복사 생성자 호출 방식이다. 이 경우 obj2를 저장할 메모리 공간을 할당함과 동시에 obj1과 멤버 대 멤버 얕은 복사가 발생하여 새로운 객체를 호출한다. 2. call-by-value 방식으로 객체를 함수의 인자로 전달하는 경우 void Function(Object obj)..

아래 코드를 실행 시 예외가 발생한다. #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; class Person { private: char* name; int age; public: Person(char* myname, int myage) { int len = strlen(myname) + 1; name = new char[len]; strcpy(name, myname); age = myage; } void ShowPersonInfo() const { cout