궤도

문제 풀이 myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇.. myunji.tistory.com 번호로는 위 문제의 다음이지만 사실 이 문제가 더 간단하다. 왜냐하면 현재 노드를 기억해 둘 필요도 없고...눈치가 빠른 사람은 알겠지만 입력에 따른 출력 갯수가 N^M이다. 소스코드 #include using namespace std; const int MAX = 8; int N, M; int a..

문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇기 때문에 전역 변수 쓸 일이 좀 많다. 백트래킹 문제를 그림으로 myunji.tistory.com 이 문제를 약간 응용한 문제이다. 오름차순을 구현하려면 어떻게 해야할까? 현재 노드의 값을 기억해두면 될 것이다. 소스코드 #include using namespace std; const int MAX = 8; int N, M; int arr[MAX]; void backNM(int cnt, int flag) { //오름차순 위해 현재 노드 저장하는 flag 추..

문제 풀이 입력으로 들어오는 값의 범위가 커서 단순한 덧셈 연산으로는 해결할 수 없다. 구몬 수학을 풀던 초등학교 시절로 기억을 되돌려보면 이런식으로 1의 자리부터 더하는게 좋을 것이다. 그런데 위와 같이 두 수의 자릿수가 다르면 어떻게 될까..? 여러 방법이 있겠지만 가장 간단한 방법은 이렇게 0을 붙여주는 것이다. 소스코드 #include #include #include #include using namespace std; int main() { string str1, str2; vector A, B, C; bool isCarry = false; //받아올림 여부 cin >> str1 >> str2; if (str1.size() < str2.size()) //str1(A)의 길이가 더 길도록 swap..

문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇기 때문에 전역 변수 쓸 일이 좀 많다. 백트래킹 문제를 그림으로 표현할 때 트리를 많이 사용하는데 이 문제도 간단히 트리로 나타내면 이런 모습이다. visited를 true로 하느냐 false로 하느냐에 따라 트리의 아래로 가거나 위로 올라갈 수 있다. 이 문제도 노드들을 방문하며 visited를 갱신하고, 배열에 값을 넣는다. 배열의 크기가 M이 되면 트리 탐색을 끝내고 배열에 있는 수를 출력한다. 재귀함수는 아무래도 머리로 따라가기가 좀 까다로우니 그림을 그려가며 공부하면 좋을 것이다. 소스코드 #include using namespace std; const int MAX..

문제 풀이 내가 극찬하는 sort 함수는 사실 stable을 보장하지 않는다. 근데 이 문제는 stable sort를 요구한다. 그렇다면 새로 정렬함수를 짜야할까? 그렇지 않다. stable_sort 함수가 있다. 정말 친절하지 않을수가 없다. 이렇게 stable이 보장됐으니, 나이만 고려하면 된다. 소스코드 #include #include using namespace std; struct info { int age; char name[101]; }; bool cmp(const info& p1, const info& p2) { if (p1.age < p2.age) //가입 순이고 stable이면 그냥 나이만 고려하면 됨 return true; else return false; } int main() { ..

문제 풀이 정렬은 어렵지 않다. sort 함수가 있기 때문이다. 먼저 길이 조건으로 한번 걸러주고, 길이가 같은 경우에만 사전 순으로 정렬한다. 사전 순 정렬도 어렵지 않다. string str1, str2가 있을 때 str1이 str2보다 사전 순으로 앞선다면 str1> N; for (i = 0; i > arr[i]; sort(arr, arr + N, cmp); for (i = 0; i < N; i++) { if (arr[i].compare(arr[i + 1]) != 0) //중복 제거 cout

문제 풀이 sort 함수에는 사실 3번째 인자가 있다. 이 3번째 인자를 통해 정렬의 조건을 입맛대로 바꿀 수 있다. 이 인자는 bool을 리턴하는 함수인데, 요구하는 인자의 형식이 중요하다. 그건 아래 코드를 보면 알 수 있다. 사용법도 코드의 주석에 써놓아서 여기에 또 쓸말이 없다. 아무튼 sort 함수는 참 좋다. 소스코드 #include #include using namespace std; struct point { int x, y; }; bool cmp(const point& p1, const point& p2) { //p1이 p2보다 앞에 있어야하는 조건 if (p1.x < p2.x) return true; else if (p1.x == p2.x) return p1.y < p2.y; else ..

문제 풀이 요구하는 것이 많지만, 이 중에서 까다로운건 최빈값 구하기 뿐이다. 입력을 받으면서 모든 배열의 합도 구해놓고, 최댓값과 최솟값도 구해놓는다. 그리고 해당 숫자의 등장 횟수도 count 배열을 갱신하며 기록해준다. 중요한건 입력으로 음수가 들어오기도 한다는 것이다. 범위가 -4,000~4,000 이니까 8,000 크기의 배열을 선언하고 입력으로 들어온 값에 4,000을 더한 인덱스를 갱신하면 된다. -4,000~4,000의 범위가 0~8,000으로 변하는 셈이다. 입력을 다 받았으면 중앙값을 구하기 위해 정렬한다. 그리고 count 배열을 돌며 최빈값을 체크한다. 해당 최빈값이 유일하다면 바로 출력하면 되지만, 유일하지 않다면 배열을 다시 돌며 최빈값 중 두 번째로 작은 값을 출력한다. 최빈값..