yulee

✅ 운영체제는 MacOS(M1) 사용중입니다. ✅ 이전 포스트 [공부/Spring] EC2 인스턴스 생성 및 연결 ✅ 운영체제는 MacOS(M1)을 사용합니다. ☘️ EC2 인스턴스 생성하기 1. 인스턴스 시작 AWS에 가입해주고 검색창에 EC2를 검색해준다. 왼쪽 메뉴에서 인스턴스를 눌러주고 인스턴스 시작 클릭! 2. 인스 yulee.tistory.com ☘️ 보안그룹 설정 1. 인바운드 규칙 설정하기 이전 포스트에서처럼 인스턴스 생성이 완료되었으니 이제 해당 서버에서 사용할 포트를 열어줘야 한다. 왼쪽 메뉴에서 보안 그룹에 들어가보면 default 하나와 새로 만든 인스턴스에 적용되는 보안그룹이 launch-wizard-번호 형태의 보안 그룹을 클릭하고 인바운드 규칙 편집을 눌러준다. 아래와 같이 S..

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

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

✅ 운영체제는 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 연산을 해주어 계산..