기록방

👉 문제링크🔸 문제 분석 🔸T번의 테스트 케이스로 K개의 양수가 주어진다.연속된 두 값의 합으로 계산했을 때 연산 비용의 최소값을 출력한다.🔸 문제 풀이 🔸K가 500이지만, Brute Force로 확인했을 때 O(K^3) 이상이 나올 것으로 예상해서 더 효율적으로 구하기 위해 DP 를 활용하고자 했다.dp 배열은 다음과 같이 구했다.1번부터 K번 숫자를 합했을 때 최소값을 구하고자 하므로, dp[0][K-1]를 구한다.다시 말해 dp 배열은 해당 범위의 최소연산 비용을 저장한다.dp 배열을 채워갈 때, 연속된 두 값을 더해가므로, 중간에 1번 잘라서 좌우 값을 더했을 때의 최소값을 구한다.따라서 점화식은 다음과 같이 구할 수 있다.K개의 숫자 중 left ~ right 범위를 계산했을 때 최소..

👉 문제링크🔸 문제 분석 🔸N개의 행렬을 곱셈 계산하려고 한다. 행렬의 곱은 곱셉 연산의 순서에 따라 연산 횟수가 달라진다.행렬곱 연산의 최소값을 출력한다.🔸 문제 풀이 🔸다이나믹 프로그래밍으로 풀이할 수 있다.dp배열로 int형 2차원 배열을 만들어 dp[i][j] : i ~ j 번 행렬 곱의 연산 수 최소값을 저장한다.i ~ j 의 크기 size를 2 이상부터 N 이하까지 늘려가며 dp 배열을 채워간다.i == j (size == 1) 일 때, dp[i][j]는 0이다.최대 int형만 사용된다고 문제에서 나타내주었다.🔸 코드 🔸import java.io.*;import java.util.StringTokenizer;public class Main { public static void..

👉 문제링크🔸 문제 분석 🔸T번의 테스트 케이스안에서 다음과 같은 입력이 주어진다.n명 (2~10만)의 학생 수가 주어지고, 다음 줄에 각 학생이 같이 팀을 하고 싶은 학생의 번호가 주어진다.자기 자신을 뽑거나, 팀을 하고싶은 학생들끼리 순환구조(서클)이 만들어지면 팀을 만들 수 있다.최종적으로 팀에 속하지 않은 학생의 수를 출력한다.🔸 문제 풀이 🔸제한시간 3초에 각 테스트 케이스의 n이 10만이기 때문에 O(n^2)의 알고리즘은 사용할 수 없다.팀이 만들어지는지 확인하기 위해 깊이 우선 탐색(DFS)를 사용한다.DFS의 경우의 수는 다음과 같다.1) 탐색하다가 시작 번호를 다시 찾음 : 탐색한 모든 학생들은 같은 팀2) 탐색하다가 중간 번호를 다시 찾음 : 중간 번호까지 팀이고, 시작 번호부..

👉 문제링크🔸 문제 분석 🔸K개의 문자를 배웠을 때, N개의 단어(문자열) 중 최대 몇 개를 읽을 수 있는지 출력한다.모든 단어는 anta로 시작해 tica로 끝난다.🔸 문제 풀이 🔸단어의 시작과 끝이 정해져 있으므로, 'a', 'n', 't', 'i', 'c' 다섯 글자는 반드시 읽을 줄 알아야 한다.K가 5 미만인 경우에는 0을 반환한다.K >= 5 일 때, K-5 개의 문자를 추가로 배워서 몇 개의 단어를 읽을 수 있는지 확인해야 한다.비트 마스킹으로 배운 문자를 표시한다.배운 문자로 단어를 읽을 수 있는지 비트 마스킹으로 확인한다.🔸 코드 🔸import java.io.*;import java.util.StringTokenizer;public class Main { private ..

💡 좋은 개발자의 필수 교양인 변수 작명법에 대해서 정리해보자.1. 대표적인 변수 작명법 종류 알아보기2. 각 환경 별 적용 사례3. 좋은 변수 작명 이론📚 변수 작명법 종류1. 카멜 표기법(Camel Case)형식첫 단어는 소문자, 이후 단어의 첫 글자는 대문자유래낙타(camel)의 혹처럼 단어가 연결될 때 중간 중간 대문자가 있는 모양에서 유래의도긴 변수명을 사용할 때 각 단어를 쉽게 구분할 수 있도록 함장점가독성이 좋고 Java, JavaScript, C# 등의 언어에서 표준으로 사용단점매우 긴 변수명은 여전히 읽기 어려울 수 있음사용 예userName, orderAmount, isLoggedIn, dailyUserTable2. 파스칼 표기법(Pascal Case)형식모든 단어의 첫 글자가 대문..