궤도

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

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

문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제랑 똑같은 유형인데 그냥 방향이 4개에서 8개가 됐을 뿐이다. 소스코드 #include #include #include #include using namespace std; int matrix[300][300], l; pair dir[8] = {{1, -2}, //나이트가 갈 수 있는 방향 {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -..

문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신이 없다. 먼저 난 처음에 기존에 미로찾기 처럼 input 배열을 갱신하는데 이제 벽을 부쉈는지 아닌지를 기록하면 될 것이라고 생각했다. 하지만 이 문제는 2차원 배열 하나로 간단하게 풀리는 문제가 아니었다. 이런 배열이 있다고 하자. 당시엔 matrix를 갱신할 생각이었어서 벽을 -1로 표현했다. 아직 벽을 부술 수 있는 상태는 파란색, 벽을 더이상 부실 수 없는 상태는 빨간색으로 표현했다. 좀 더 진행했다. 보라색은 벽을 부수고도, 안부수고도 갈 수 있음을 나타냈다. 아무튼 이렇게 벽을 부순 상태에서 갱신된 3,..

문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아직 방문한 적 없는 좌표라면 X까지 오는데 걸린 시간에 1을 더해 갱신하면 된다. myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제에서 상하좌우만 뺀거라고 생각해도 된다. 소스코드 #include #include using namespace std; ..

문제 풀이 myunji.tistory.com/285 [백준] 7576번 : 토마토 문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파 myunji.tistory.com 이 문제의 3차원 버전이다. 풀이는 완전히 똑같으니 그건 어렵지 않았고, 3차원 배열 문제를 풀일이 많이 없어서 입력이 제일 어려웠다. 소스코드 #include #include #include #include #include using namespace std; struct pos { int x, y, z; }; //범위 초과 때문에 상하좌우 한줄씩 추가 int matr..

문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제랑 풀이가 거의 똑같다. 다만 모든 토마토를 방문하지 못할 수도 있는 경우를 체크해줘야 한다는 것과 가장 마지막에 익을 토마토(도착점)이 무엇인지 모른다는 것만 다르다. 소스코드 #include #include #include #include #include using namespace std; //범위 초과 때문에 상하좌우 한줄씩 추가 int matrix[1002][1002]; int N, M..

문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바로 아래, 오른쪽에 있는 좌표까지의 최단거리는 2일 것이다. 그 다음엔 이렇게 되고, 계속 하다보면... 이렇게 최단거리를 찾았다. 지금 이 과정은 bfs로 한거나 다름없다. 왜냐하면 시작점(1, 1)에 대해 갈 수 있는 좌표((2, 1), (1, 2))를 큐에 넣었고 최단거리가 2인 좌표들을 순서대로 방문하며 갈 수 있는 좌표((3, 1), (2, 2), (1, 3))를 큐에 넣어 또다시 순서대로 해당 좌표들을 방문하며 진행했기 때문이다. 그럼 왜 dfs는 안될까? 그림을 통한 설명을 하기 전 간단하게 말하자면 dfs는..