yulee

🤔문제 이해 행과 열, 그리고 3x3의 작은 사각형 안에 1~9까지의 수가 중복없이 나오게 보드를 짜는 문제이다. 조건 보드 : 9 x 9 시간 : 2초 메모리 : 256MB 🔥풀이🔥 백트래킹 방식으로 값이 비어있는 부분에 넣을 수 있는 수 중에서 가장 작은 수부터 넣어보면서 처음으로 보드가 숫자로 다 채워질 수 있을 때를 출력하면 된다. 변수 - bool width[i][num] : i번째 행에 num의 존재 유무 - bool length[i][num] : i번째 열에 num의 존재 유무 - bool square[i][num] : i번째 사각형에 num의 존재 유무 - square의 경우 좌표가 (i, j)일 때 (i/3)*2 + (j/3)을 계산한 값이 몇번째 사각형인지 나타낸다. 재귀함수 solve..

🤔문제 이해 진실을 알고 있는 사람들이 파티에 참석하는 경우 그 파티에선 진실만 말해야하고, 순서 상관없이 진실을 한번이라도 듣게 되는 사람들이 참석하는 파티는 진실만 말해야 할 때 과장된 이야기를 할 수 있는 파티의 개수를 구하면 되는 문제이다. 💡첫번째 아이디어 진실을 아는 사람이 포함된 파티에 간 사람들을 모두 진실을 알고 있다고 처리해주고 이 과정을 반복하면 진실로 말해야 하는 파티와 과장해서 말해도 되는 파티를 구분해줄 수 있다고 생각했다. 🔥풀이🔥 know[i] : i번 사람이 진실을 알면 true, 모르면 false party_know[i] : i번 파티가 진실을 말해야 하는 파티면 true, 과장해서 말해도 되는 파티면 false party[i][j] : i번째 파티에 참석한 사람들의 번호..

🤔문제 이해 상어는 주어진 속도와 방향으로 1초마다 이동하고, 같은 위치에 두마리 이상이 이동된 경우 사이즈가 큰 상어만 남게 된다. 낚시왕도 1초마다 오른쪽으로 이동해 낚시왕이 위치한 열에 있는 상어 중 가장 위에 있는 상어만 잡아 올리고 잡은 상어의 크기를 모두 합한 값을 출력하는 문제이다. 💡첫번째 아이디어 단순하게 구현하는 문제인데 시간이 적게 걸리게 하기 위해서는 상어를 이동시킬 때 격자판의 경계를 만났을 때마다 방향을 바꾸는게 아닌 한번에 옮기는 식을 세워야 한다고 생각했다. 여러 경우를 시뮬레이션 해보고 식을 세웠다. 🔥풀이🔥 격자판의 크기를 넘어간다면 처음 넘어가고 그 이후부터는 (격자판 크기-1)로 나눈 나머지가 규칙적으로 0, 1, ... (격자판 크기 -1) , ...,1, 0이 되게..

🤔문제 이해 먼저 푸는 게 좋은 문제는 먼저 풀어주되 번호가 낮은 문제를 더 우선적으로 풀면 된다. 출력으로는 문제 푸는 순서를 출력하면 되는 문제이다. 💡첫번째 아이디어 먼저 푸는 것이 좋은 문제가 있는 문제를 모두 순서대로 출력해주고, 나머지 문제들을 오름차순으로 출력해주면 된다고 생각했다. ❌첫번째 제출 제대로 풀었다고 생각했고, 출력 값도 잘 나왔다.문제를 다시 읽어보고 반례를 생각해보니 문제의 조건에 "가능하면 쉬운 문제부터"라는 조건을 빠뜨렸었다..! 💡두번째 아이디어 먼저 푸는 것이 좋은 문제가 없는 문제의 in_degree도 0으로 초기화해서 가능하면 쉬운 문제들부터 출력되게 해주었다 . 🔥풀이🔥 위상정렬 알고리즘을 이용하였다. 우선순위큐를 사용하여 in_degree가 0인 문제 먼저 출력..

🤔문제 이해 연속된 몇 개의 수를 선택했을 때 그 합이 가장 큰 수열의 합을 출력하는데 그 수열 중에서 하나를 없앨 수 있는 문제이다. 💡첫번째 아이디어 하나를 어떻게 없앨까 하다가 바로 전에 푼 가장 긴 바이토닉 부분 수열이 떠올랐다. 앞에서 순서대로 합이 가장 큰 연속합1을 구해주고, 뒤에서 순서대로 합이 가장 큰 연속합2을 구해주고 어느 숫자를 기준으로 양옆으로 연속합1과 2를 더한 값이 가장 크다면 그 기준 숫자를 없앤 것이 더 큰거고, 연속합1의 최댓값이 가장 크다면 하나를 없애지 않아도 가장 큰 연속합을 구할 수 있는 것이라고 생각해서 풀었다. 🔥풀이🔥 dp[i]는 i번째 수를 마지막 수로 했을 때 가장 큰 연속합을 의미한다. dp2[i]는 i번째 수를 첫번째 수로 했을 때 가장 큰 연속합을 ..

🤔문제 이해 i+1번째 수가 i번째 수보다 큰 부분 수열 중에서 가장 긴 수열의 길이를 출력하는 문제이다. 💡첫번째 아이디어 처음엔 부르트 포스가 생각났다. 그냥 눈으로 계산해봐도 모든 조합을 생각해봐야 풀린다고 생각했기 때문이다. 근데 저걸 처음부터 모든 조합을 다 계산하게 되면 1초는 거뜬히 넘기게 된다... 💡두번째 아이디어 멘토님에게 LCS(longest increasing subsequence)를 푸는 방법을 전수받았다! 풀이에 자세히 설명하겠다. 🔥풀이🔥 입력받은 수열은 arr에 순서대로 저장해놓고 dp 배열을 arr값으로 초기화해준다. 수열의 두번째 수부터 n번째 수까지를 나타내는 인덱스 i와 첫번째 수부터 i번째 수까지를 나타내는 인덱스 j가 있다고 하자. 만약 arr[j]가 arr[i]보..

🤔문제 이해 0이 맨 앞에 올 수 있으므로 1~N자리의 숫자 중 i번째 숫자가 i+1번째 숫자보다 작거나 같은 수의 개수를 구하는 문제이다. 💡첫번째 아이디어 일단 맨 처음에 0이 오고 그 다음에 올 수 있는 숫자들을 나열해 봤다. N이 커질수록 중복되는 값들이 보였고 DP 문제임을 확신했다! 🔥풀이🔥 dp[i][j]에서 i는 맨 처음에 올 수 있는 수로 0~9까지를 나타내고, j는 자릿수를 의미한다. 자릿수가 j일 때 dp[0][j]는 dp[0][j-1] ~ dp[9][j-1]까지의 값을 다 더한 값이다. 구하고자 하는 자릿수까지 dp를 채웠으면 마지막으로 그 자릿수로 만들어지는 처음 숫자가 0~9까지인 숫자들의 개수를 다 더한다. 모든 dp연산과 마지막 총합, 출력까지 %10007 연산을 해주어 계산..

🤔문제 이해 한 공장에서 다른 공장으로 가는 경로 중에서 그 경로 상에 있는 중량 제한 값 중에서 최솟값을 찾고, 그 최솟값 중 가장 큰 것을 출력해주는 문제이다. 💡첫번째 아이디어 DFS를 통해 모든 경로를 탐색해서 그 경로의 가장 작은 중량제한 값을 저장하고 그 값들끼리 비교해서 젤 큰 값을 찾아주면 된다고 생각했다. ❌첫번째 제출 섬이 1만개, 도로가 10만개로 10억번을 다 돌게 되는 첫번째 아이디어 방법으로는 시간초과가 났다. 💡두번째 아이디어 시간초과를 어떻게 해결해야할지 막막해서 질문을 했다. 문제에서 나와있듯 짐의 무게보다 중량제한이 작은 다리를 지나가려는 경우엔 다리가 무너진다고 했다. 이 점을 활용해서 이분탐색을 이용하여 결과를 도출해주면 1초 안에 해결이 가능했다. 🔥풀이🔥 DFS +..

🤔문제 이해 상, 하, 좌, 우, 대각선 4방향으로 인접한 1을 한 글자로 취급하여 글자가 몇개 있는지 구하는 문제이다. 🔥풀이🔥 정말 간단한 BFS 문제인데 방향이 4개 더 추가된 버전이다. 방향을 표현해주는 dx와 dy를 다음과 같이 선언해서 오른쪽, 왼쪽, 위쪽, 아래쪽, 오른쪽 아래, 왼쪽 아래, 오른쪽 위, 왼쪽 위를 나타내주었다. int dx[8] = { 1, -1, 0 , 0 , 1, -1, 1, -1}; int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1}; #include #include using namespace std; int m, n; int map[251][251]; bool visited[251][251]; queue q; int dx[8] = { 1, -1..

🤔문제 이해 같은 색이 연속으로 나오지 않게 칠했을 때 비용이 가장 적게 드는 경우의 비용을 구하는 문제이다. 🔥풀이🔥 전에 풀어본게 기억이 나서 바로 DP를 이용해 풀었다. dp[i][j]에서 i는 집의 번호, j는 색을 의미한다. dp[i][0]은 0을 칠했을 때 그 전 집에서 칠할 수 있는 경우는 1과 2이므로 dp[i-1][1]과 dp[i-1][2]를 비교해 더 작은 값과 i번째 집을 0으로 칠했을 때의 비용과 합해 dp[i][0]을 업데이트 해준다. 색깔 1과 2도 동일하게 해주게 되면 마지막 집에서 색을 0을 칠했을 때 vs 1을 칠했을 때 vs 2를 칠했을 때를 비교해 그 최솟값을 출력해준다. #include #include using namespace std; int n; vector dp..