✏️ 문제유형: DFS / 백트래킹 https://www.acmicpc.net/problem/15652     ✏️ 풀이  처음에는 from itertools import permutations 써야지 했다가 중복 처리가 안되니까for문으로 해보려고 했는데 시간 초과가 날 것 같고.. 이를 어쩔까 생각했다.  결국 구글링... 그래서 알아낸 것은 DFS & 백트래킹으로 풀 수 있다는 거  1로 시작한다고 하자. 그러면 1부터 N까지 큰 수 하나 중복으로 고른 게 i라고 하자. i를 배열에 저장해두고, i로 다시 가서 i부터 N까지 큰 수 하나 중복으로 고르고 반복..  이 과정을 배열의 길이가 M이 될때까지 반복하고, return해서 다른 길로 가지치기를 해야 한다.  가지치기는? 백트래킹. 따라서 df..

✏️ 문제유형: 구현/ 큐https://www.acmicpc.net/problem/11866  ✏️ 풀이 N명 중에서 K번째 사람을 계속해서 제거하는 문제이다.  위의 예제로 이해를 해보면, 7명 중 3번째 사람을 계속 제거한다.  앞에서 2명 pop-push하고 3번째 사람은 pop만 반복하면 되는데, 큐의 동작을 간단히 나열해보면 아래와 같다.  1 2 3 4 5 6 7pop-push: 1 2 / only pop: 3 4 5 6 7 1 2 pop-push: 4 5 / only pop: 6 7 1 2 4 5pop-push: 7 1 / only pop: 24 5 7 1 ... 반복  이를 코드로 나타내면 아래와 같다. from collections import dequen, k = map(int, inp..

📌문제 유형: 스택https://www.acmicpc.net/problem/1874  📌 풀이  처음에 문제를 이해하지 못해서 꽤나 헤맸었다.. (입력된 수열로 오름차순을 만들라는 줄 알고) 찬찬히 문제를 읽어보면,  1. 1~n의 수를 이용한다. 2. push는 오름차순으로 진행한다. 3. 입력된 수열이 스택에서 push/pop한 결과물이어야 한다.  따라서 1부터 n까지 직접 적어보며 push와 pop을 언제하게 되는지 해보면 된다.  1번 예제로 설명해보면, 입력이 8 4 3 6 8 7 5 2 1 이다. N = 8이고 결과 수열 = 4 3 6 8 7 5 2 1add = 1로 카운트해보자. add = 1 ~ 4까지 push poppop ==> 4 3 완료 / stk = 1 2add = 5, 6 p..

📌문제 유형: 그래프 이론 https://www.acmicpc.net/problem/11403   📌풀이  문제의 조건을 분석하면, 아래와 같이 볼 수 있다. 1. 방향 그래프 2. i->j로 가는 방법이 있는지를 모든 정점에 대해 알아봐야 함.  이때 한 방향으로 계속 깊게 파고 들어야 하니 DFS가 맞다고 판단했다.  각 정점에 대해서, dfs()를 수행하고 갈 수 있는 정점이면 output 1차원 배열에 저장하면 된다. 하나의 정점 n에 대해 output = [0] * N으로 정의되어 있고, graph[n][i] == 1 (갈 수 있는 길이 있고), output[i] == 0 (아직 방문 안했으면) 그 정점 i에 대해 dfs()를 재시행한다.  이걸 모든 정점에 대해 반복하면 완성 !!  ⭐ 아..

📌문제 유형: 그래프 탐색 (BFS)https://www.acmicpc.net/problem/14940   📌 풀이  전형적인 BFS 문제이다. 단, 시작점이 (0,0) 이 아니라 2 값을 갖고 있는 위치부터라는 점! 따라서 먼저 2의 값을 가진 위치를 찾아야 한다.  그 뒤에 모든 지점까지의 최단거리를 출력하라고 한다. 최단거리는 BFS로 구할 수 있다.  이때 움직일 수 있는 방향이 상하좌우이므로, dx/dy를 선언해 bfs() 안에서 for문을 통해 한 지점이 갈 수 있는 상하좌우 4곳을 살펴볼 수 있도록 한다. 이때 갈 수 있는 곳은 queue에 담는다.  여기서 포인트는, 거리 값을 visited에 누적합으로 표현한다는 점이다.  1. 모든 지점에 대해 visited[i][j] = -1로 초..

📌 문제 유형: DPhttps://www.acmicpc.net/problem/1463   📌 풀이 문제를 읽으면서 딱 눈에 들어오는 것은, 시간 제한이 0.15초 밖에 안된다는 점이다. 그리고 N이 1~10^6이라면, 완전탐색으로는 시간 초과가 날 것이라는 걸 느끼게 된다.  이 상태에서 문제를 좀 더 살펴보자.  3으로 나누어 떨어질 때, 2로 나누어 떨어질 때, 둘 다 아닐때 이렇게 3가지 경우에 대해 연산을 제한해 두고 있다. 이 3개의 연산을 적절히 사용해 연산 횟수를 MIN로 만드려고 한다. 드는 생각들! 1. 3의 배수일 때 (2의 배수는 아님)2. 2의 배수일 때 (3의 배수는 아님) 3. 둘 다 아닐 때 - 1을 뺀다. 4. 6의 배수일 때 ==> 이 경우가 추가되어 고려될 수 있다. ..