Machineboy空

https://www.acmicpc.net/problem/1717 문제요약0 a b : a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다.1 a b : 두 원소가 같은 집합에 포함되어 있는지를 확인한다.난이도Gold 5풀이 포인트Union-Find TreeREVIEW DP를 썼다고 함. 무슨 소린지 아직 파악 전.CODE// 코테 통과는 백트래킹까지만 알면되고! 유니온 파인드 부터는 킬러 문항으로 나옴!// Union은 합집합, Find: 그룹의 대표찾기!// DP기법의 두 가지 기법 중 하나로, 메모리자이제이션?#include using namespace std;int n, m;int par[1000001];// 0: 합집합, 1: Find // 대표를 리턴하는 연산void init(){ ..

https://www.acmicpc.net/problem/15649 문제요약1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하라! 난이도Silver 3풀이 포인트백트래킹REVIEW 백트래킹은 곧 dfs다.. 아직 무슨 말인지 잘 와닿지 않는다.다시 공부해야한다.CODE// 백트래킹: 뒤로 다시 돌아가서 확인해본다! 역으로 돌아가본다!// 백트래킹을 곧 dfs라고 할 수 있다!#include using namespace std;// 거쳐온 경로vector v;int visited[10];int N,M;// 리프노드에 왔는지 체크를 phase ,단계void f(int phase){ if(phase == M){ for(auto it:v){ cout > N>>..

원래 버전에 새로운 기능을 추가했을 때 오류 없이 완벽하게 동작한다는 보장이 없다면 어떻게 해야할까?제대로 동작하는 소스는 그대로 둔 채 새 소스를 추가한 버전을 따로 만들어 관리하고 완벽하게 완성한 다음 원래 소스에 더할 수 있다면 편리할 것. 1) 브랜치란?브랜치(branch) : 나무에서 가지가 새 줄기를 뻗듯이 여러 갈래로 퍼지는 데이터 흐름을 가리키는 말로 사용합니다. 2) 브랜치 만들기// 새 브랜치 만들기git branch 브랜치명// 브랜치 사이 이동하기git checkout// 커밋내용 한 줄로 확인git log --oneline 3) 브랜치 정보 확인하기// 한번에 스테이지 올리기git add .//각 브랜치 최근 커밋 보기git log --oneline --branches//그래프 형..

1) 깃 저장소 만들기저장소를 만들고 싶은 디렉터리로 이동해서 깃을 초기화하면 그때부터 해당 디렉터리에 있는 파일들을 버전관리할 수 있습니다.$ git init  2) 버전 만들기 (add, commit)버전이란?문서를 수정할 때마다 간단한 메모와 함께 수정 내용을 스냅숏으로 찍어서 저장한다.ver.0.1 , ver.0.2 ...프로그램 개발에서는 수정 내용이 쌓이면 새로 번호를 붙여서 이전 상태와 구별한다. 이렇게 번호 등을 통해 구별된 것을 버전이라고 부른다.깃에서 버전을 관리하면 원래 파일 이름은 그대로 유지하면서 파일에서 무엇을 변경했는지를 변경 시점마다 저장할 수 있습니다. 또 각 버전마다 작업했떤 내용을 확인할 수 있고 그 버전으로 되돌아갈 수도 있습니다. // 깃 상태 확인$ git stat..

2005년 리누스 토르발스(Linus Torvalds), 리눅스 창시자이기도 한 그가 지옥같은 작업환경에서 벗어나기 위해 만든 시스템이 바로 깃입니다. 리눅스를 만드는 개발자들은 깃을 통해 리눅스의 수많은 소스 코드를 효율적으로 관리하기 시작했습니다. 그리고 오늘날에는 리눅스뿐만 아니라 수많은 소프트웨어의 소스 코드가 깃을 통해서 관리되고 있습니다. 버전 관리(Version Control)문서를 수정할 때마다 언제 수정했는지, 어떤 것을 변경했는지 편하고 구체적으로 기록하기 위한 버전 관리 시스템백업(Backup)백업은 현재 컴퓨터에 있는 자료를 다른 컴퓨터에 복제하는 것입니다. 외장 하드 디스크나 USB 디스크 등 별도의 저장 장치를 마련해서 백업할 수도 있고, 드롭박스(Dropbox)나 구글 드라이브..

분할정복(Divide and Conquer)Divide : 큰 문제를 작은 문제로 분할한다.기저사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야한다.Conquer: 작은 문제의 답을 모아 큰 문제의 답을 구한다.일반적으로 재귀로 구현한다.  백트래킹(backtracking)답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘가지치기(pruning)를 통해 연산량의 유의미하게 줄여줌가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야함.정확한 시간 복잡도를 구하기 어려움 분할 정복백트래킹주로 재귀적인 방식으로 해결하위 문제를 해결하고 결과를 결합하여 문제를 해결문제 해결을 위해 모든 가능한 선택을 시도한 후,..

1. 회문(Palindrome)ex) "소주만병만주소", "수박이박수", "Madam, I'm Adam", "1234321" 회문을 판단하는 방법? 2. 올바른 괄호 문자열(VPS = Valid Parenthesis String)ex) (()), (())()보통은 스택(Stack)을 사용해서 해결')'가 입력될 때마다, 스택에 있는 '('를 하나씩 지운다. 이때 스택(top)이 비어있거나 '('이 없으면 올바른 괄호 문자열이 아님모든 문자열을 순회한 뒤, 스택이 비어있으면 올바른 괄호 문자열이고 비어있지 않으면 올바르지 않은 괄호 문자열임

내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다. 오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.입력오늘 푼 문제의 개수 자연수 N1 출력다음날 풀 문제의 개수 출력문제요약입력값과 같은 구성의 수 중 가장 작은 큰 수풀이 포인트Next-permutation정렬REVIEW경우의 수가 다양해지면 자꾸 생각하길 포기한다.작은 단계로 나누어 생각하는 법을 또 명심!999999까지가 아닌 1000까지만 해서 생각해보고 넓히고 하면 됌!CODE#include #include #include using namespace s..