✅ 운영체제는 MacOS(M1) 사용중입니다. ☘️ EC2 인스턴스 생성하기 1. 인스턴스 시작 AWS에 가입해주고 검색창에 EC2를 검색해준다. 왼쪽 메뉴에서 인스턴스를 눌러주고 인스턴스 시작 클릭! 2. 인스턴스 설정 2-1. 애플리케이션 및 OS 이미지 Quick Start에서 Ubuntu로 선택하고 AMI는 무료로 사용가능한 Ubuntu Server 22.07 LTS (HVM), SSD Volume Type으로 선택해준다. (Ubuntu 선택 시 자동으로 선택됨) 인스턴스 유형의 경우도 자동으로 선택되는 프리티어인 t2.micro를 그대로 사용 2-2. 키페어(로그인) 생성 기존에 쓰던 키 페어를 쓸 경우엔 선택해주고, 새로 만들어 줄 경우엔 새 키 페어 생성을 눌러준다. 키 페어 이름은 기억하기..

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

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

🤔문제 이해 어느 한 숫자를 기준으로 왼쪽에는 감소하는 숫자들이, 오른쪽에는 증가하는 숫자들이 오는 부분 수열을 찾는 문제이다. 이때, 같은 숫자가 연속적으로 나올 수 없다. 💡첫번째 아이디어 가장 긴 증가하는 부분 수열의 응용 버전이었다. 🔥풀이🔥 dp_in[i]는 i번째 수를 마지막 수로 했을 때 증가하는 수의 개수를 의미하고, dp_de[i]는 i번째 수를 첫번째 수로 했을 때 감소하는 수의 개수를 의미한다. 1. dp_in과 dp_de는 모두 1로 초기화한다. 2. 앞에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_in과 이전값 dp_in에 1을 더한 값 중에서 더 큰 값을 dp_in의 현재값에 넣어준다. 3. 뒤에서부터 차례대로 현재 숫자가 다음 숫자보다 크다면, 현재 dp_de..

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

🤔문제 이해 나라를 세운 사람이 1 왕족이고, 왕족이 아닌 외부 사람은 0왕족이다. 부모의 왕족 점수를 각각 2로 나누어 더한 값이 자식의 왕족 점수가 되고, 왕위를 계승받기를 주장하는 사람들 중 왕족 점수가 가장 높은 사람을 출력하면 되는 문제이다. 💡첫번째 아이디어 예제 입력 9 2 edwardi charlesi edwardi diana philip charlesi mistress wilhelm mary philip matthew wilhelm helen edwardii charlesi laura alice laura charlesi helen alice bernard henrii edwardii roxane charlesii elizabeth henrii charlesii matthew 예제 입력1..

🤔문제 이해 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..