hansjour 개발일지

문제 파악-dp활용  제한 사항1 1 0 접근 방법-0~n까지 현재 금액 누적해가기(for문)-금액 도달 전까지 누적해가며 dp 수행, 수행하면서 대상 값을 업데이트해가며 돌려줌(amount-coin)-완전탐색으로도 구현이 가능하나 효율성에서 문제 발생!!-메모이제이션 활용) n번째 계단처럼, n번째 값까지의 최소값을 하나하나 메모해두고계산하지 않은 것만 dp수행, 이미 계산된 것은 배열 안에서 골라서 result값 갱신하기코드 구현import java.util.*;class Solution { public int solution(int[] coins, int amount) { int[] memory = new int[amount+1]; Arrays.fill(memory,I..

문제 파악-dp를 이용해 구현한다.Constraints:2 0 접근 방법-bottom-up 방식으로 구현한다.-n(cost.length) 계단까지 최소비용을 구하기 위해 최소비용 배열 선언하여 메모하기-마지막 계단에 해당하는 최소 비용 리턴코드 구현import java.util.*;class Solution { public int minCostClimbingStairs(int[] cost) { //memoization initialization int[] dp = new int[cost.length+1]; for(int i=2;i배우게 된 점처음에 첫 계단 혹은 둘째 계단에서 시작할 수 있으므로 둘 다 비용 계산 의미 없음고로 2번째 계단에서부터 ..

https://www.acmicpc.net/problem/2468    문제 파악-특정 강수량마다 잠기는 곳/안 잠기는 곳 구분하여 배열 저장- 안잠기는 곳을 '섬'이라 칭하자- dfs원리로 매 케이스의 섬을 카운트하여 가장 큰 카운트를 리턴 🎈[알고리즘 분류]그래프 이론브루트포스 알고리즘그래프 탐색너비 우선 탐색깊이 우선 탐색 접근 방법-BufferedReader와 StringTokenizer 이용해 값을 입력받기- BufferedReader는 처음에 선언하고 br.readLine()으로 받기- StringTokenizer는 한 줄단위로 쪼갤 때마다 선언..!, delimeter는 뒤에 적어주기, 실제 쪼갤 때는 st.nextToken() 사용-각 강수량마다 잠기는 지역/안잠기는 지역 비교문으로 fa..

부트캠프 수업을 들으며 작업을 하다보면 컴퓨터가 매우 느려지는 경우가 있다.며칠 전, 실습을 진행하다가 인텔리제이 구동 속도가 다른 친구들에 비해월등히 느린 걸 보고 강사님께서 램 몇기가인지 여쭤보셨다. (8G요..)나름의 대책으로 프로젝트는 한 개만 켜놓고 안 쓰는 크롬창도 다 닫았는데,그래도 느렸다😥귀차니즘이 심해서 느려도 그냥 참고 대충 살았는데보시던 짝꿍 분이 집에서 남는 DRAM을 가져다 주셨다.뭐가 맞을 지 몰라서 이것 저것 가져오셨다. (천사..?👩‍💻)   2G짜리도 하나 주셨는데 그건 DDR3로 슬롯이 달라 끼울 수가 없어 패스하고내 노트북에 맞는 DDR4 8G 두 개 중에 선택을 하기로 했다. 제품은 다음 두 개로 클럭 속도 빼고는 SODIMM에 사양이 거의 같음.    램을 끼울..

https://www.acmicpc.net/problem/2606   문제 파악-컴퓨터가 이어져있으면 바이러스가 옮는다. 는 개념-저번에 파이썬으로 푼 문제 재풀이-한 네트워크에서 영향받는 컴퓨터 수 세는 것임 접근 방법-주어진 int끼리 연결하여 인접 리스트 먼저 만들고(양방향)해당 노드와 이어진 모든 노드 순회하며 카운트-visited와 count는 모두 멤버변수로 선언한다. 코드 구현import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class 바이러스 { static..

문제 파악-저번 실습으로 나온 문제. 각 방을 돌며 최초의 좌석 찾고 그로부터 되는 방향을 나아가며 거리가 2 이내에 좌석이 발견되면 false리턴places의 행 길이(대기실 개수) = 5places의 각 행은 하나의 대기실 구조를 나타냅니다.places의 열 길이(대기실 세로 길이) = 5places의 원소는 P,O,X로 이루어진 문자열입니다.places 원소의 길이(대기실 가로 길이) = 5P는 응시자가 앉아있는 자리를 의미합니다.O는 빈 테이블을 의미합니다.X는 파티션을 의미합니다.입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.return 값 형식1차원 정수 배열에 5개의 원소를 담아서 return 합니다.places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로..

문제 파악-주어진 2차원 배열은 서로 간선으로 연결 된 관계-주어진 그래프에서 최대 거리에 있는 노드 갯수를 구하기노드의 개수 n은 2 이상 20,000 이하입니다.간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.접근 방법💡 -각 노드와 연결관계를 파악하고 인접리스트 형태로 변환하여 진행-bfs 를 이용하여 해당 그래프의 순회 거리를 구하고 최대 거리의 노드 갯수 구하기-방문 노드는 제외하고 큐 순회를 한다.-간선 별로 몇번 째로 순회하는지 세기 위한 cnt와 직관적으로 보기 편한 리스트 구현하기 코드 구현import java.util.*;class Solution { public ..

문제 파악-서로 이어져있는 그래프의 간선을 ‘하나’ 끊었을 때, 두 개로 나누어진 그래프를 각각 순회-순회 시 방문 노드를 카운트하여 리턴하고, 각 순회가 끝났을 때 두 그룹의 카운트 차를 비교-최솟값을 갱신하여 최종 리턴n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.1 ≤ v1 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.접근 방법💡 -BFS를 이용하여 각 노드를 순회 -그래프를 둘로 쪼갤 때 ⇒ 간선을 순회하며 하나씩 다 삭제해보기(O(n))-인접리스트 형태로 ..

https://www.acmicpc.net/problem/2178 문제 파악-BFS를 이용해 최소 거리 구하기-1은 이동 가능한 거리, 0은 이동 불가능한 거리  접근 방법-(1,1)이 시작점이지만 좌표 상 0,0이므로 고려해서 풀기  코드 구현import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int answer=0; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(..

https://www.acmicpc.net/problem/1260 문제 파악-그래프를 DFS 혹은 BFS 형태로 순회하기 접근 방법-주어진 연결 정보를 인접 리스트 형태로 변환하여 그래프로 만들기-각각 DFS,BFS 함수를 만들기-결과값을 출력 코드 구현import java.util.*;public class Main { static boolean visited[]; static ArrayList[] A;//연결리스트로 구성된 Int형 배열 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(..