98건의 항목
실버1 : 동적 계획법 문제이다. 생각 전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.
실버5 : 동적 계획법 문제이다. 생각 생각 보다 힘들게 푼 문제이다. n이 50000이고, 시간 제한이 0.5초이기 때문에 완전탐색으로 풀면 힘들 것이라 생각했다. 그래서 동적 계획법 방법으로 풀이를 채택했다. 이 문제는 동전 문제와 비슷하게 생각해야 한다.
골드4 : 이분 탐색 문제이다. 생각 어려웠다. 여러가지 배열이 섞이고, 계산하는 방법을 생각하지 못했다. 이 문제를 풀면서 배운 것은, 정말 컴퓨터처럼(센다..) 생각해야 된다는 것.
골드5 : 동적계획법 문제이다.
실버1 : 동적계획법 문제이다. 생각 동적 계획법하면 유명한 문제이다. 나는 동적 계획법을 풀 때 보통 두가지 방법을 많이 사용한다. 상태에 대한 정의와 점화식을 직관으로 때린다. (감..) 순차적으로 완전 탐색 방법으로 그려본다.
브론즈1 : 구현 문제이다. 풀이 단순한 문제이다. 앞뒤에 어떠한 문자를 넣을 수 있으니, 현재 가지고 있는 ROT13만 가지고서 부분적으로 보았을 때, 가장 작은 차이를 가지고 있는 지점만 알면된다. 이후는 맞춰서 끼워넣으면 되니까.
실버2 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다.
골드3 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다. 이 문제는 가장 긴 감소하는 부분 수열, 가장 긴 증가하는 부분 수열을 합한 문제이다.
골드2 : 이분 탐색 문제이다. 생각 기존에 dp로 풀었던 문제가 데이터의 개수만 달라져 새로운 문제가 되었다. 이번 문제는 풀이를 좀 참고하였으며 새로운 공부를 할 수 있었다. 이 문제는 먼저, 일반적인 dp문제로 풀수가 없다.
골드4 : 동적 계획법 문제이다. 생각 전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.
실버1 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다. 이 때, 시간제한 때문에 구한 소수를 담아두는 것이 좋다.
실버2 : 파라메트릭 서치 문제이다. 생각 파라메트릭 서치 문제이다. 일단 완전 탐색이 불가하고, 답을 제시했을 때 분기를 만들 수 있다는 점에서 바로 접근했다. 인접한 집간의 최대 거리를 제시한다.
골드2 : 유니언 파인드 문제이다. 생각 이런 문제는 정말 비행기가 온다고 생각하고 푸는 것이 가장 좋은 것 같다. 그러니까 모든 문제는 시뮬레이션을 제대로 하는 것이 중요. 총 5개의 게이트가 있다고 하자. 그 때, 4번으로 비행기가 들어온다.
실버4 : 스택 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
플래티넘5 : 세그먼트 트리 문제이다. 생각 전형적인 세그먼트 트리 문제이다. 구간에 대한 합을 연속된 쿼리로 물어보는 경우인데, 이런 경우 단순하게 짜면 그냥 펑!이다.
실버1 : 이분 탐색, Parametric Search 문제이다. 생각 처음에 이 문제를 풀 때, 세그먼트 트리로 풀려고 했다. 그런데, 문제가 생겼다.
실버4 : 메모이제이션 문제이다. 생각 고등학교 때 많이 풀어본 함수의 개수 구하는 문제와 같다. 결국은 공역단에서 N개의 site를 고르게 되면 자동으로 순서가 결정되기 때문이다.
실버1 : DFS 문제이다.
실버1 : 동적 계획법 문제이다. 생각 다이나믹의 유형 중 중요한 유형이다. 대부분의 동전 문제의 방식과 비슷하다. 1차원 다이나믹이지만 2개의 반복문을 통해 2차원 처럼 생각하는 것이 필요하다.
실버1 : 동적 계획법 문제이다. 생각 다이나믹의 유형 중 중요한 유형이다. 대부분의 동전 문제의 방식과 비슷하다. 1차원 다이나믹이지만 2개의 반복문을 통해 2차원 처럼 생각하는 것이 필요하다.
플레티넘1 : 동적 계획법, Convex Hull 문제이다. 생각 일단 완전 탐색을 생각해 본다. 음. 말도 안된다. 몇개를 겹쳐서 만드는지 완전탐색을 한다면 시간 복잡도가 O(n!) 이다. 이 문제는 그냥 직관적으로 동적 계획법 냄새가 난다.
실버3 : 이분 탐색 문제이다. 생각 이분 탐색 문제이다. 이전의 문제들과 마찬가지로, 값을 제시하고 그에 대한 분기를 만드는 것이 중요하다. 이 때, 어느 영역에서 답이 나오는지를 잘 체크하고, 답의 후보를 기록해두는 행위가 중요하다.
실버2 : 조합 문제이다. 풀이1 기본적인 조합 문제이다.
골드3 : 그래프 문제이다. 생각 현재 시작 위치에서 다음 쓰레기를 치우고, 그 위치에서 다시 다음 경로를 탐색하는 과정으로 문제를 풀려 했다. 하지만 코드를 짜면서도 탐색과정이 계속하여 중복되서 어떻게 풀어야 할지 고민을 많이했다.
골드1 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다. 특정한 상태의 발전소로 오는 방법은 몇가지로 정해지기 때문이다. 그래서 정의를 잡으면 다음과 같다.
골드2 : 그리디, 정렬 문제이다. 생각 실제로 운송물을 움직인다고 생각해보자. 그렇다면 가장 무거운 하중을 움직일 수 있는 크레인이 가장 많이 움직여야 최단 시간에 짐을 움직일 수 있다. 이부분이 핵심이다.
실버1 : 구현 문제이다. 너무 짜증난다. 문제 제대로 읽어. 제발제발젭라. 뱀이 지나가는 경로를 잡아줄 자료구조 map에 표시해서 갈 수 있는지 없는지 알아야 한다. tail의 위치를 tracking할 수 있어야 한다.
실버2 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.
골드4 : bfs 문제이다. 풀이 bfs는 가중치가 없는 그래프의 최단 거리 문제를 풀 때 사용하는 방법이다. 이 문제는 최단 거리 문제이므로 이 풀이를 선택하는 것은 맞다.
골드1 : 기하 문제이다. 생각 볼록 껍질, Convex Hull이라 한다. 이 알고리즘에서 유명한 것을 그라함 스캔 알고리즘인데, 해당 동영상을 봐보자. 이것과 같은 알고리즘을 구현하기 위해서는 다음과 같은 절차를 거쳐야 한다. 가장 y가 작은 점을 구한다.
골드4 : bfs 문제이다. 생각 단순한 구현 문제이다. 이 때, 순서를 잘 파악하는 것이 중요하다. 먼저, 불을 번지게 한 상태에서, 사람의 현재 위치로 부터 어디로 가는 것이 좋은지를 판단해야 한다.
실버3 : 분할정복 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
골드5 : bfs 문제이다. 생각 최소 경로를 묻는 문제로써, 완전 탐색으로 풀이할 수 있다. 이 때, 중요한 점은, 한번의 스텝을 넘어감에 있어서 소수여야 한다는 것, 그리고 불가능하다는 것을 알려주기 위한 visited를 만드는 것이다.
실버2 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.
실버4 : 수학 문제이다. 생각 소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.
골드4 : 구현 문제이다. 상당히 갑갑했다. 일단 무한개의 소용돌이가 생길 수 있다는 점에서 기존의 달팽이 문제처럼 생각하면 안된다라는 판단이 들었다. 발생하는 모든 숫자를 저장한다면 메모리 초과가 날 것이 분명했기 때문이다.
실버5 : 정렬 문제이다. 생각 정렬 문제이다. merge sort(합병 정렬)을 구현해보고자 시도했다. 알고리즘 기본적인 병합 정렬의 알고리즘은 다음과 같다. 위키 백과 - 합병 정렬 좀 더 자세한 설명 partition 나누는 방법은 간단하다.
풀이1 실버1 : BFS 문제이다.
풀이1 실버4 : 이분 탐색 문제이다. 생각 특정 숫자가 등장하는 lowerBound와 UpperBound를 잡아내면 끝나는 문제이다.
실버1 : 동적계획법 문제이다.
실버3 : dfs 문제이다. 생각 기본적인 dfs 문제이다. 반으로 나눈 팀에 대한 점수를 더하는 것이므로, true false를 통해 구현할 수 있다.
실버3 : 정렬 문제이다. 생각 문제에서 하라는 대로 비교만 하면 된다.
실버2 : 동적계획법 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
골드3 : 동적 계획법 문제이다. 생각 이 문제는, BOJ - 평범한 배낭(12865)과 매우 비슷하다. 한번 푸는 것이 좋다. 이 문제는 memory의 범위가 매우 크기 때문에, 이 것을 기준으로 로직을 짜면 메모리가 터진다.
실버3 : 이진 탐색 문제이다. 풀이 예산 금액은 최대예산과 아예 안주는(0원) 방법이 있다. 따라서 0과 max금액을 양 끝으로 잡는다.
실버1: 동적 계획 법을 사용하는 문제이다. 대표적인 동적계획법 문제이다. 기초적인 동적 계획법 문제를 풀 때에는 펜을 갖고 쓰는 것이 중요해보인다. 기본적으로 점화식을 갖고 해결하는 방식이기 때문에, 수열 문제를 푸는 것도 같은 사고로 접근해야 한다.
골드1 : stack 문제이다. 생각 아, 어려웠다. 처음에 dp로 풀생각을 했더니, O(n^2) 이라 500,000인 input에 맞지 않는다. 또한 그 과정에서 세그먼트 트리 혹은 우선 순위 큐를 사용하려 했지만 구현 난이도가 올라가 고민했다.
골드4 : stack 문제이다. 풀이 아, 정말 아쉬운 문제였다. 하지만 배운 것이 있었다. Stack을 기본적으로 사용하는 이유은 어떤 복잡도 문제를 해결하기 위함이다. 이 부분은 뒤에 다시 살펴보도록 하자.
실버1 : dfs를 사용하는 기초적인 문제이다. 이런 문제를 풀 때, 생각보다 실수를 많이하는 부분은, testcase가 있을 때, 초기화를 하지 않는 것이다. 항상 testcase가 있는 문제는, 이 부분을 유념해야 한다.
실버1 : 동적 계획법 문제이다. 생각 DFS나 BFS로는 depth가 깊어져 시간초과가 난다. 이 문제는 동적계획법으로 풀어야 한다. 그저 최대 사탕의 개수만 출력하면 되기 때문이다.
DFS graph 골드4 : 그래프 문제이다. 생각 이분 그래프란 무엇인가? 문제를 읽고는 파악하는 게 힘들었다. 차라리 그림으로 보는 것이 좋다. {:.center-text} 왼쪽과 같은 그래프가 있을 이걸 오른쪽 그림처럼 바꿀 수 있느냐의 문제이다.
실버3 : 동적계획법 문제이다. 생각 이 문제의 핵심은, 최고자리 숫자가 0 또는 1일 때의 상황을 분리해서 생각해보는 것이다. 이유는 나열하면 금방 알아차릴 수 있다.
실버1 : 동적계획법 문제이다. max_element 최대한 쓰지 말자. 그리고 sizeof는 바이트수를 리턴해준다.
실버2 : 동적 계획법 문제이다. 생각 앞으로 보내는 dp문제이다. 정의 이 문제는 위치에 따라 개수가 결정되므로 dp의 인자를 좌표의 위치로 잡는 것이 수월하다.
실버2 : 파라메트릭 서치 문제이다. Root 찾기 처음에 또다시 해시로 풀려고 하다가, 중간에 입력값의 범위가 후덜덜한 것을 보고 풀이 방법을 바꾸었다. 이 문제를 그냥 linear하게 풀려고 하면 100000번을 linear하게 탐색해야 하기 때문에 터져버린다.
골드4 : 유니온 파인드 문제이다. 생각 문제를 이해해보자. 먼저 처음에 아무일도 하지 않을 경우에 입력된 n에 대해서 0 ~ n까지의 바구니가 생긴다. 그 다음, m개의 명령이 들어온다.
플래티넘5 : 세그먼트 트리 문제이다. 생각 01234564175298 입력값이 이렇게 주어진다고 생각해보자. 이 상태에서 3~6까지의 최소값을 구하는 것은, 단순한 방법으로 구해도 O(n^2)으로 풀 수 있다.
플래티넘5 : 슬라이딩 윈도우 문제이다. 생각 N이 500만이라 세그먼트 트리로 풀면 터진다.
실버1 : 분할정복 문제이다. 처음에 너무 삽질했다. 그냥 구조적으로 부족한 것 같다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
골드1 : 구현, 시뮬레이션 문제이다.
실버1 : 구현 문제이다. 생각 단순 구현 문제이다. 비트마스크 연습을 위해 비트마스크로 풀었다. 해당 과정을 하는 동안에 인접행렬 같은 matrix를 만들어 무언가를 해보려 했지만 좋지 못했다. 구현 문제는 노가다로 적어주는게 정신 건강에 이롭다.
실버4 : 정렬 생각 최빈값 구할 때, 머리를 좀 써야한다. map구조를 잘 써볼 것. 그리고 정렬하는 방법도 고민해볼 것. Code // // main.cpp // test2 // // Created by 최완식 on 2021/03/29.
골드2 : 트리, 유니온파인드 문제이다. Root 찾기 흠. 입력으로 들어오는 node들이 순차적이지 않다는 점을 알아야 한다.이거 때매 시간 엄청 날렸다 즉, 랜덤으로 들어오는 그래프 정보를 가지고, 어떤 녀석이 tree의 root가 될 것인지 알아내야 한다.
골드3 : dfs 문제이다. 풀이 트리 = 사이클이 없는 무방향 그래프. 어떠한 두 노드를 선택해도 경로는 하나이다. 즉 무조건 연결되어 있다. 쉽게 생각하기 위해서 이미 두 지름인 점을 알고 있다고 가정하자.
실버3 : 수학 문제이다. 생각 일단 코드가 처음보는 거라 유심히 보았다. 결국 이런 것을 묻는 문제였다. 가장 큰 약수가 뒤에서 부터 몇번째에 나오니? 그렇다면 가장 큰 약수를 구해야 하는데, 가장 큰 약수는 사실 \sqrt{n} 까지만 조사해도 풀 수 있다.
골드5 : 동적 계획법 문제이다. 생각 결국 무게 제약이 있는 문제이다. 나는 이 문제를 풀 때 감을 잡기 참어려웠는데, 무게에 제약이 있다는 점을 갖고 완전 탐색을 한다는 아이디어를 가지고 생각했다.
실버1 : 동적계획법 문제이다. 생각 dp[i] : i번째 포도주의 위치에서 마실 수 있는 최대 포도주 양 i번째 포도주의 포도주 양은 세가지 경로에서 답을 찾을 수 있다.
실버1 : 최단경로 문제이다.
실버3 : 동적 계획법을 사용하는 문제이다.
실버1 : 분할 정복 문제이다. 생각 특정 행렬을 10번 곱하라는 의미는, 곧 이렇게 해석 된다.
실버2 : 그래프 문제이다. 생각 아. 정말 쉽겠지 했는데, 되지도 않는 시간 복잡도 줄여보겠다고 확인 되지 않는 것 썼다가 하루 다 날린 문제이다. 문제는 상당히 간단하게 DFS로 풀 수 있다.
level2 : 구현, 또는 동적 계획법을 사용하는 문제이다. 처음 풀이로는 빠르게 풀기 위해서 그냥 단순히 구현을 했다. 입력이 1000 x 1000 이라, 완전 탐색을 수행하더라도 로직을 최대한 덜 쓰도록 짜야된다는 생각을 하면서 짰다.
Infomation 발표년도 : 1983 설계자 : Bjarne Stroustrup, 덴마크 패러다임 : 절차적 프로그래밍, 함수형 프로그래밍, 객체 지향 프로그래밍 절차지향, 객체지향의 성격을 동시에 띄기 깨문에, 굉장히 유연하고 강력하다.
Identifier Reserved Words 사용가능 문자 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_0123456789 예약어는 안된다.
함수의 기본 모양 수학에서의 함수와 같이, input , output 이 있고, input 이 들어갔을 때, 어떤 작업을 한 뒤, output 을 내보내는 방식으로 작동한다.
Local, Global Variables Local Variables 함수 안에서만 동작하고 함수가 끝나면 메모리에서 삭제된다.
Recursion Function Factorial 같은 함수를 구현하기 위해서는, 자기자신의 출력값을 다시 불러야 되는 필요성이 있다. 이것을 재귀함수라 한다. 11. Function Part.
Aliasing (Reference Variable) 기본적으로, 우리가 선언된 변수를 다른 변수에 할당하게 되면 이 값을 복사해서 사용하는 셈이 된다.
참조변수와 일반변수의 사용의 차이점을 알았다면, main 함수가 동작하는 도중 다른 함수를 호출할때, 그 함수의 인자 역시 두 종류가 있음을 알 수 있다. 마찬가지로 일반변수와, 참조변수를 사용할 수 있다.
기존에 작업한 글이 있어 링크로 대체한다. 05. Control Flow 06. Loop Part. 01 07. Loop Part. 02 iomanip library 기본적으로 iostream 라이브러리로 출력을 하게되면, 왼쪽 정렬이다.
fstream Reading from file #include <iostream> #include <fstream> #include <string> using namespace std; int main(){ string line1; string line2 ifstream myfile("input.txt"); if (myfile.is_open()){ if(!myfile.eof()){ // end of file 이 아니면 계속 진행.
String library method #include <string> #include <iostream> using namespace std; int main(){ string word = "good"; word.length(); // 길이 리턴 word.empty(); // 빈 문자열인지 1, 0값 리턴 word.clear(); // 문자열 삭제 word += "-bye"; // 더하기 가능 word[0]; // h word[word.length() - 1]; // 마지막...
What is Array? 직접적으로 값을 순차적으로 매핑한다. C언어에서 오래된 기술이고, 객체가 아니다.
What is Class? 우리는 클래스라는 개념을 왜 도입했을까? C++에서 함수가 태어나게 된 이유도 분리해서 관리하기 위함이었다.
Pass by Reference 내가 클래스를 만들고, 그 클래스를 바탕으로 객체를 만들었다. 이때, 이 클래스에 연결되어 있는, 함수를 메서드라 했다.
Overloading 같은 함수이름, 혹은 연산자를 사용하면서, 하나 이상의 정의가 가능한 방법이다. Function Overloading 연산자 오버로딩과 방식이 동일하다. 밑에서 예를 든것을 보고 이해해보자.
friend 두개의 클래스가 있을 때, 서로 만들어진 모든 멤버변수, 멤버함수를 공유하기 위해서 우리는 friend 라는 키워드를 사용할 수 있다. a 객체가 b 객체를 친구로 선언한다면 b객체는 a객체의 모든 변수와 함수값을 갖다가 사용할 수 있다.
static Members 때때로는, 클래스의 객체들이 모두 공유하는 변수를 가지는 것이 용이하다. 전역변수와는 조금 다른 점이 있다 공통점 : 특정 함수나 클래스가 끝나고 나서 변수가 사라지지 않는다. 차이점 : 특정 클래스에 구속되어 있다.
Destructor 소멸자는 특별한 멤버함수이다. 객체가 생성되고, 소멸될 때 호출된다. 소멸자의 목적은, 컴퓨팅 자원의 절약에 있다. 객체가 생성되고 계속 남아있다면 메모리 자원을 많이 소모하게 된다.
Inherence 전체적인 구조 상속이 필요한 이유 상속은 매우 유용하다. 13. Class & Object & Constructor 글을 다시 기억해보자.
Static Binding (정적 바인딩) #include <iostream> #include <string> #include <vector> using namespace std; class Base{ public: void f(){cout << "Base::f()" << endl;} virtual void vf() {cout << "Base::vf()" << endl;} }; class Derived:public Base...
Dynamic Binding (동적 바인딩) 그런데, 우리가 두 클래스가 상속관계에 있다는 것을 안다면, 이 멤버함수를 자동으로 묶어줄 수는 없을까? 이제 override , virtual 의 강력한 기능을 알 수 있다.
Header File 왜 사용하는가? C++ 코드를 작성하다가 보면, Class 내의 멤버변수, 멤버함수, 또 내가 만들어서 사용하는 사용자 정의 함수, main 함수 등 결국 어떤 프로그램을 동작하고 싶은 건지 전체적 구조를 알기 어렵다는 점이 있다.
List 이제껏 vector container 에 대해서 집중적으로 사용했는데, list container 역시 vector와 마찬가지로 많이 사용된다. Vector 장점 : search가 빠르다. 단점 : pop/ push 가 느리다.
Iterator 반복자는 33. Generic 함수이다. 즉, 일반적인 프로그래밍을 가능하게 하기위해 만들어진 전역함수이다. 우리는 배열을 다루기 위해 vector, array, list와 같은 것들을 사용했다.
Lambda function 함수 안에서 부를 수 있는 Local function! 사실 정체는 객체이지만, 우리는 함수의 개념으로 갖다 쓴다! Usage [closure](입력 매개변수)->출력 type{내용} Local function 이기 때문에 만들어졌다가 리턴 후 사라진다.
for_each() algorithm 라이브러리에는 다양한 함수가 있지만, 그중에서 for_each() 함수에 대해서 알아보자.
예외 처리 예외 처리를 사용하므로써 알고리즘이 마주할 수 있는 예외 상황에 대해 코드를 분리할 수 있다. 이 결과 알고리즘에 보다 집중할 수 있다. 에러를 만들어 보자.