궤도

문제 풀이 myunji.tistory.com/287?category=1154147 [백준] 1697번 : 숨바꼭질 문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아 myunji.tistory.com 이 문제의 응용버전이다. 순간이동과 앞뒤 이동 모두 1초가 걸렸던 1697번과 달리 이번엔 순간이동을 0초만에 할 수 있다. 즉 각 이동에 대한 가중치가 달라진 것인데, 그래프의 관점에서 말하자면 간선에 가중치가 생긴 것이다. 이런 경우에서 최단거리를 찾고자 한다면 가중치가 작은 것을 우선으로 탐색해야 한다. 괜히 가중치 0으로 갈 수 있는 곳을 가중치 ..

문제 풀이 클립보드를 관리하는 것이 중요한 문제다. 처음에는 덮어씌워진다길래 변수 하나로 클립보드를 관리하려 했는데, bfs의 상태에 따라 클립보드의 상태가 다를 수도 있다는걸 생각하지 못한 것이다... 그래서 방문여부를 관리하는 visited 배열을 2차원 배열로 만들어 클립보드의 정보를 저장했다. 그리고 이모티콘의 현상태 정보또한 구조체로 관리했다. 구조체에는 이모티콘의 개수와 그때까지 걸린 시간, 그리고 그 상태에 클립보드에 복사된 이모티콘의 개수를 저장했다. 소스코드 #include #include using namespace std; const int MAX = 1001; struct emoji { int num, time, pasted; }; int S; bool visited[MAX][MAX..

문제 풀이 먼저 모든 친구 관계를 저장한다. 메모리를 아끼기 위해 myunji.tistory.com/291?category=1154147 [백준] 1707번 : 이분 그래프 문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으 myunji.tistory.com 이때 썼던 방법으로 저장했다. i번째 사람을 시작점으로 하는 dfs를 N번 돌리면서 문제의 조건에 맞는 친구 5명을 찾으면 리턴한다. 문제를 풀고 다른 사람들의 코드를 보니 친구 관계 4개를 찾는걸 종료 조건으로 한 사람들이 많았다. 근데 그거나 이거나 같은 말이니까 상관없다. 소스코드 #include #include u..

문제 풀이 예제 입력 2에 대해 그냥 중복 상관없이 모든 수열을 사전순으로 출력하면 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 가 될 것이다. 여기서 중복을 제거해야 하는데 처음엔 아무리 머리를 굴려봐도 비효율적인 방법만 떠올랐다. 출력한 수열을 모두 저장해서 비교한다거나...각 숫자의 등장횟수를 세서 계산한다거나... 그러다가 백트래킹 과정을 그림으로 그려봐야겠다 싶었다. 현재 1을 선택한 상황에서 백트래킹으로 7을 선택했다. (1-7) 그리고 더 이상 고를 필요가 없으니 다시 1로 올라와서 9로 내려간다. 9가 선택된 상태이다. (1-9) 또다시 1로 올라와서 9를 선택하려고 보니 이전에 선택한 값과 같은 값이다. 이러면 탐색을 하지 않는 것이다. 9 1 9..

문제 풀이 비트연산과 관련된 문제이다. 여기저기에서 배운거라 개념은 잘 알지만 막상 문제를 풀어보려니까 살짝 당황한건 사실이다. S에 들어올 수 있는 값을 7까지로 제한하도록 하겠다. S = 0이라고 하고 이걸 8자리의 2진수로 표현해보면 0000 0000 이다. 여기부터 시작하자. add 3을 한다고 하자. 1

문제 풀이 dp로 풀면 더 빨리 풀 수 있을텐데 난 그냥 완전탐색(브루트포스)으로 풀었다. 문제를 풀고 보니 dfs를 사용한 코드가 많았다. 근데 뭔가 논리가 그냥 이대로 dp 쓰면 되는거 아닌가 싶긴 했다. 소스코드 #include #include #include using namespace std; int N, money, result; vector input; void backtracking(int idx) { if (money > result) //최대 비용 비교 result = money; for (int i = idx; i N; for (int i = 0; i > dur >> profit; in..

문제 풀이 백트래킹으로 탐색하면서 S가 되는 값이 나오는지 확인하면 된다. 부분수열의 길이가 정해진건 아니라 이와 관련된 종료조건은 딱히 없다. S와 같은 부분수열의 합을 찾자마자 return을 하는 실수를 할 수도 있다. 근데 만약 S=0이고 주어진 정수가 -7 7 -3 3이라면 -7 7도 가능한 부분수열이지만 -7 7 -3 3도 가능한 부분수열이다. 이걸 놓치지 않도록 하자. 소스코드 #include using namespace std; int input[20], N, S, sum, cnt; void backtracking(int idx) { for (int i = idx + 1; i < N; i++) { //중복되는 수열을 제거하기 위해 sum += input[i]; //visited 처리 if (..

문제 풀이 사전순으로 출력하라고 했으니까 일단 문자 입력을 정렬해야할 것이다. 백트래킹으로 C길이의 문자열을 만들고, 이 문자열이 모음 1개 이상, 자음 2개 이상의 규칙을 충족하는지 확인하면 된다. 소스코드 #include #include using namespace std; int L, C; char input[15], arr[15]; bool isPromising() { int vowel = 0; for (int i = 0; i = 1) && ((..