궤도

문제 풀이 myunji.tistory.com/299 [백준] 10972번 : 다음 순열 문제 풀이 myunji.tistory.com/19?category=1154147 [EPPER] 11회 6번 문제 풀이 접근을 잘못했던 문제. 하필이면 그 접근으로도 입력 예시는 전부 다 맞게 나와서 난 그게 맞는 줄 알았다. 근데 혹시나 하는 마. myunji.tistory.com 이 문제의 반대 버전이다. 풀이도 반대로 하면 될테니까 그냥 이번에도 내장 함수를 써야겠다. www.cplusplus.com/reference/algorithm/prev_permutation/?kw=prev_permutation prev_permutation - C++ Reference function template std::prev_pe..

문제 풀이 myunji.tistory.com/19?category=1154147 [EPPER] 11회 6번 문제 풀이 접근을 잘못했던 문제. 하필이면 그 접근으로도 입력 예시는 전부 다 맞게 나와서 난 그게 맞는 줄 알았다. 근데 혹시나 하는 마음에 돌려본 테스트 케이스에서 오류를 발견했다. 먼저 myunji.tistory.com 비슷한 문제를 푼 적 있다. 이때는 알고리즘을 막 공부할 떄라 그렇게 효율적인 코드를 짠 것 같진 않지만 어떤식으로 푸는지에 대한 풀이는 알고 있으니까 www.cplusplus.com/reference/algorithm/next_permutation/?kw=next_permutation next_permutation - C++ Reference function template ..

문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다. 소스코드 #include using namespace std; int cnt; void backtracking(int num) { if (num == 0) { //0이면 카운트 추가 cnt++; return; } for (int i = 3; i >= 1; i--) { //3부터 1까지 뺄 수 있는지 확인 if ((num - i) >= 0) backtracking(num - i); } } int main() { int t, n; cin >> t; for (int i = 0; i > n; backtracking(n)..

문제 풀이 가능한 모양을 하나하나 분리해서 찾는건 이 문제가 브루트포스라고 해도 너무한 방법이다. 보라색 조각을 제외한 나머지 4개의 조각은 백트래킹으로 탐색할 수 있는 조각이다. 백트래킹으로 탐색할 수 있다는걸 쉽게 설명하면 한붓 그리기처럼 탐색할 수 있단 뜻이다. 그럼 보라색 조각을 제외한 나머지 조각은 백트래킹으로 처리한다고 치고, 보라색 조각은 어떻게 처리할까? 이런 조각 하나가 있다고 하자. 이 조각을 기준으로 상하좌우에 조각을 붙이면 이런 + 모양이 될 것이다. 여기에 상하좌우 중 하나의 조각만 빼면 가능한 모든 보라색 조각의 경우가 나올 것이다. 소스코드 링크 = 0) && (nr = 0) && (nc < M)) { //범위에 들어오면 저장 cnt++; arr[i] =..

문제 풀이 홀수인 두 소수의 합으로 짝수를 나타내는 문제이다. 홀수인 두 소수이므로 3부터 시작하면 될 것이고 입력값의 절반까지만 탐색하면 된다. 만약 입력이 8이라면 3+5와 5+3은 같은 말이기 때문이다. 그리고 두 소수의 차가 가장 큰 것을 출력하라고 했는데 그럼 뭐 3부터 탐색하다가 두 소수를 찾으면 바로 출력하면된다. 20은 3+17로도 나타낼 수 있고 7+13으로도 나타낼 수 있지만 두 수의 차가 가장 큰 것은 먼저 발견된 3+17이다. 이 소수를 찾는 과정에서 시간초과가 나지 않도록 빠르게 구하는 것이 중요하다. 나는 에라토스테네스의 체를 사용했다. myunji.tistory.com/61 [백준] 1929번 : 소수 구하기 문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토..

문제 풀이 예제 입력1을 오름차순 정렬해보자 -10 -9 2 4 4 여기서 중복을 제거하면 -10 -9 2 4 이 배열의 인덱스는 당연히 왼쪽에서부터 0, 1, 2, 3이다. 그리고 이건 각 숫자에 대해 해당 숫자보다 작은 수의 개수가 된다. 소스코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N; long long input; vector arr, sort_arr; cin >> N; for (int i = 0; i > input; arr.push_back(input); //원래 배열 } sort_arr = arr; sort..

우리 프로젝트에서 기술적으로 가장 중요한 부분은 채점 부분이다. 사용자가 사진을 찍어서 업로드한 뒤 채점 결과를 받기까지의 과정을 그림으로 나타내면 일단 이렇게 사진을 업로드 한 뒤 이런식으로 채점이 이루어질 것이다. 이미지 업로드는 저번에 해서 블로그에 글로도 올렸다. 그리고 욜로 학습 담당 팀원이 모델을 파이썬에 이식하는 건 성공했고 내가 그걸 플라스크에 이식하는 것까지 성공했다. 그럼 이제 리액트로부터 넘어오는 url을 플라스크까지 보내서 결과를 받아 다시 리액트에 보내는 과정을 해야 한다. 아직 욜로와 ocr api 연결부분을 하지 않아서 당장 채점 알고리즘을 만들 순 없고 오늘은 그냥 리액트-노드-플라스크 사이에서 데이터가 잘 오가는지만 확인하려고 한다. node.js 서버에서 다른 서버의 ap..

문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으로 칠한 것을 볼 수 있을 것이다. 이분그래프는 인접한 두 정점을 다른색으로 칠한다고 가정할 때 오직 두가지의 색을 사용해서 모든 정점을 칠할 수 있는 그래프이다. 자료구조때 배웠던가...컴퓨터 알고리즘때 배웠던가...암튼 배웠었다. 아이디어는 간단한 이 문제가 정답 비율 20%대인 이유는 간과하기 쉬운 조건 하나와 메모리 초과 그리고 입력 초기화 떄문 아닐까싶다. 먼저 간과하기 쉬운 조건하나를 말해보도록 하겠다. 바로 모든 정점이 연결됐을거란 보장이 없다는 것이다. 이 그림처럼 다른 정점과 연결되지 않은 정점이 있을 수 있다..