기록방

👉 문제링크🔸 문제 분석 🔸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 ..

프로그래머스에서 주관하는 자격증 중 하나인 PCCP의 Lv3 를 취득했다🎉🎉 🚀 왜 따고자 했더라프로그래머스에는 현재 3가지 자격증이 있다. (https://certi.programmers.co.kr/)먼저 PCCP는 코딩전문역량인증시험으로 어려운 난이도의 코딩 자격증이고,PCCE는 코딩필수역량인증시험으로 쉬운 난이도의 기초 코딩 자격증이다.그 밖에도 최근에 생긴 SQL 관련 PCSQL 자격증도 생겼는데, 나중에 취득해볼 생각이다.(PCCE도 따볼까 하는데, 응시 비용이 4만원으로 비싸서 고민...) 난 개발자 지망이고, 다음과 같이 PCCP Lv3 부터 우대사항이 있으므로 목표를 Lv3 취득으로 정했었다.아쉽게도 신입이 아니라 경력직을 많이 뽑아서 직접 지원은 못해봤지만...그래도 포트폴리오용으로..