yulee

🤔문제 이해 모든 도시를 거치고 다시 처음 도시로 돌아오는 모든 경로 중 비용이 가장 적게 드는 경로의 비용을 구하는 문제이다. 💡첫번째 아이디어 그냥 순열을 구해서 풀면 최대 16! =20,922,789,888,000으로 1초 안에 절대 풀 수 없다. 이 문제는 1주차 스터디에서 배운 비트마스킹에 대한 문제였고, 문제 풀이 방식을 거의 다 배웠어서 DP와 비트마스킹으로 바로 풀 수 있었다. 물론 DP 동작 방식을 이해하기 위해 시간이 조금 걸리긴 했다. 🔥풀이🔥 dp[i][j]는 현재 위치 i와 현재까지 방문했던 정점들의 정보를 담은 j 값일 때, 앞으로 필요한 순회 비용의 최솟값을 의미한다. j가 (1 w[i][j]; } } cout

🤔문제 이해 시작점에서 각 정점을 방문하기 위해 필요한 최소 비용을 구하는 문제이다. 💡첫번째 아이디어 문제가 그냥 딱 다익스트라 문제라 다익스트라를 이용했다. 🔥풀이🔥 다익스트라를 그대로 구현하였고, 다음 정점까지의 거리를 우선순위큐에 넣어주기 전에 이미 그 정점까지 최소거리보다 크면 큐에 넣어주지 않고 continue를 해주었다. 그리고 우선순위큐에 들어있는 정점이 이미 최소거리가 확정되었다면 그 때에도 continue를 해줘서 불필요한 연산을 줄여주었다. 아래는 제출한 코드이다. #include #include using namespace std; #define INF 100000000 int dist[20002], v, e, k; int main() { cin.tie(nullptr); cout.t..

🤔문제 이해 중복이 존재하고, 순서에 상관있게 나열하는 연산자 순열의 모든 경우에 대해 계산한 값의 최솟값과 최댓값을 찾는 문제이다. 💡첫번째 아이디어 브루트 포스, 즉 모든 경우의 수를 찾아보고 계산해 비교해봐야 최솟값과 최댓값을 찾을 수 있겠다고 생각했다. 모든 경우를 트리 모양으로 나타내보면 n번째 연산 다음에 올 수 있는 연산들은 n번째 연산이라는 공통된 값을 가지고 연산을 수행하므로 DFS를 이용해 풀면 될 것 같았다. 계산 결과나 계산 도중에 나오는 값들은 정수형인 int의 범위 안에 들어가므로 변수는 int로 선언하고, N의 범위가 11 이하이므로 이 아이디어로는 시간 초과 걱정은 없음! 🔥풀이🔥 main에서 +, -, x, / 를 각각 한번씩 dfs 함수를 실행시켜 준다. dfs함수는 연산..

🤔문제 이해 1부터 N까지 숫자를 이어써서 만든 수의 k번째 자리의 숫자를 구하는 문제! 문제가 짧은 만큼 간단했다. 💡첫번째 아이디어 간단하게 생각했을 때 N의 자릿수가 n일 때 새롭게 만들어지는 수는 1*9 + 2*90 + 3*900 + ... (n-1)*((10^n -1)-(10^n-2))에 가장 작은 n자리 수부터 n까지를 더하면 구할 수 있을 것이라고 생각했다. k를 찾을 때에는 k가 포함되는 곳이 몇 자릿수일 때인지를 파악해서 최악의 경우 10000000~9999999까지 탐색하므로 시간 제한에 걸리지 않을 것이라고 판단했다. 🔥풀이🔥 첫번째 반복문 -> k가 포함되는 자릿수 구하기 두번째 반복문 -> 해당 자릿수의 최솟값~최댓값까지 total에 자릿수를 더해주면서 k가 포함되는 범위를 찾고 ..

🤔문제 이해 다음 값이 현재 값을 3으로 나눈 값이거나 2를 곱한 값으로 나열되어 있는 수열을 뒤섞어 놓은 게 입력으로 주어지고, 뒤섞기 전의 형태를 찾는 문제이다! 💡첫번째 아이디어 주어진 예제1에서는 N이 6이고 수열 B는 4 8 6 3 12 9였다. 각 숫자별로 이전에 올 수 있는 값(*2하기 전, /3하기 전 값)과 다음에 올 수 있는 값(*2한 후, /3한 후)을 적어보았다. 이전과 이후에 올 수 있는 값이 명확해 보여서 해당 방법을 가지고 구현해봤다. 해당 문제의 정답을 저장하는 자료구조는 앞 뒤로 넣고 뺄 수 있는 list를 사용하였다. list를 채워넣기 위해 입력 값을 저장하는 배열을 0부터 n-1까지 for문으로 돈다. list가 비어 있는 경우 이전에 올 수 있는 값과 다음에 올 수 ..

💡첫번째 아이디어 일단 보자마자 BFS임을 알았다! 일단 갈 수 있는데는 다 가보는데 안되면 끝인거니까 간단하게 map이라는 2차원 배열을 사용하여 두개의 지도를 표현해 주었고, BFS의 큐에는 몇초가 지났는지를 의미하는 cnt, 현재 지도의 위치를 나타내는 idx, 어떤 지도인지를 나타내주는 map_num의 정보를 담고 있는 pair 형태로 구성해주었다. 간단하게 +1, -1, 반대편 +k이므로 해당 지도의 값이 1이고, 사라지지 않은 idx일 경우에 큐에 넣어주고 idx가 n보다 커졌을 때 1을 출력하고 그렇지 않고 큐가 다 비게 되면 0을 출력한다. ❌첫번째 제출(4%에서 틀렸습니다) 예제 출력은 잘 나왔는데 제출해보니 틀렸다고 떴다. 문제를 다시 읽어보니 지도에서 먼저 이동하고 cnt가 커지는 방..

💡첫번째 아이디어 이번 문제는 모든 경우의 수를 다 생각해봐야 할 것 같았다. DFS를 이용한 모든 조합의 경우를 다 탐색해보는 알고리즘으로 구현해보았다. (구글링 참고했음,,) 일단 nCr에서 n은 문제에서 주어지고, r은 bound 변수로 반복문을 통해 1~n까지 다 DFS를 돌게 된다. DFS 함수는 시작 인덱스인 idx와 현재까지 선택된 케이크의 개수를 나타내는 cnt가 parameter로 전달되고 cnt가 bound가 같아지면 check를 통해 선택된 수들의 역수(1/x)를 total변수에 더해주고 total이 0.99보다 크고 1.01보다 작으면 경우의 수를 나타내는 ans를 ++해준다. DFS의 반복문은 예시를 들어보자. n = 4, bound = 2 일때 DFS(0,0)이 실행되면 idx ..

💡첫번째 아이디어 최솟값과 최댓값을 따로 저장해서 추가된 값이 최댓값보다 크거나 최솟값보다 작으면 최댓값과 최솟값을 업데이트해주는 방식을 생각했다. 이 방법으로는 1 > x; if( i==0 ) { dp[0] = 0; min_num = x;} else { if ( x dp[i-1] ? (x-min_num) : dp[i-1]; } cout

💡첫번째 아이디어 소문자대문자로 바뀔때마다 끊어서 문자열의 개수를 센 배열을 만들었다. 예를 들어 iLoveINHA의 경우 1(i) / 1(L) / 3(ove) / 4(INHA)로 만들고 그 사이에 별과 마름모가 들어가는 규칙을 찾아봤다. 예제 1) iLoveINHA => 1 1 * 3 ◆ 4 예제 2) ConquerThePlanet => 1 * 6 1 * 2 1 * 5 같은 크기별로 나눈 문자열의 첫번째가 대문자인지 소문자인지 확인해서 대문자면 숫자 배열의 홀수번째가 대문자, 소문자면 숫자 배열의 짝수번째가 대문자이다. 따라서 홀/짝에 따라 대문자/소문자를 구분한다. 현재 마름모가 활성화되었는지 같은 크기의 문자가 몇개인지 확인 1. 활성화 1.1 대문자 (1개orN개) - 그냥 입력 1.2 소문자 (..