정리공간

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 대표적인 동적 계획법 문제였다 집을 기준으로 1 이라 두고 좌표의 왼쪽과 위의 값을 더하며 저장하는 방식으로 풀었다 class Solution { private static int[][] nodes; public int solution(int m, int n, int[][] puddles) { nodes = new int[n][m]; for(int i=0;i

programmers.co.kr/learn/courses/30/lessons/12900 [ 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr ](https://programmers.co.kr/learn/courses/30/lessons/12900) 처음에는 동적계획법을 이용해 풀고자 했으나 시간초과가 떠벼렸다 그 후 규칙성을 찾아보고자 고민한 결과 n에따른 피보나치 수열이 결정됨을 알아냈다 아래를 확인해보자 n = 0 일경우의 타일배치의 경우의 수는 0 n = 1 일경우의 타일배치의 경우의 수는 1..

programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr dfs를 통해 풀었다 노드의 개수 크기의 노드를 방문 했음을 체크할 boolean 타입의 check배열을 통해 방문하지 않은 노드가 존재한다면 dfs를 돌려 노드와 연결된 모든 노드들의 check 배열들을 true로 만들었다 과정이 끝날때마다 하나의 네트워크가 있다는 뜻이므로 answer++를 해줬다 class Solution { public int solution(in..

programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 방향성이 있는 그래프의 최단거리 알고리즘이다 선수들을 노드라고 생각하고 노드에서 노드의 최단 경로가 존재한다면 순위를 특정지을 수 있다 판단할 수 있고 없다면 순위를 특정지을 수 없다 판단할 수 있다. 그래프 최단거리 알고리즘의 대표적인 알고리즘인 플로이드 와샬 알고리즘을 적용하여 풀었다. 이때 max값은 Integer.MAX_VALUE로 할 경우에 max값을 서로 더해 비교하는 부분때문에 오버플로우가 발생한다 따라서 max 값은 문제 제한사항에 겹치지 않을만한 적당히 큰 수로 정하..

programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 대표적인 동적계획법 문제 같았다 항상 좌우 양끝은 내려올 수 있는 경로가 정해져 있었고 꼭대기를 기준으로 내려가며 더할때마다 올수있는 경로중 최대값을 위치에 저장한다면 불필요한 연산을 줄일 수 있다. 입력 : [7] [3, 8] [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5] 입력은 위와같이 주어지며 왼쪽대각선을 갈때는 y++, 오른쪽 대각선을 갈때는 x++ y++ 와같은 방법으로 이동시켰다 class Solution { priv..

programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr PriorityQueue를 이용해 푼 문제이다 만약 queue가 비어있다면 다음 작업을 수행하는 사이에 들어오는 요청들을 소요시간 기준으로 오름차순 정렬하여 종료시간 - 요청시간을 더하는 식으로 구현하였다 주의할점은 하나의 작업이 끝나고 다음작업을 할때마다 작업중 에 들어오는 요청은 모두 PriorityQueue를 통해 정렬 해야한다. import java.util.*;..

programmers.co.kr/learn/courses/30/lessons/1836 코딩테스트 연습 - 리틀 프렌즈 사천성 리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 programmers.co.kr 굉장히 주먹구구식으로 푼거 같다 import java.util.*; class Solution { String answer = ""; public String solution(int m, int n, String[] board) { char[][] cBoard = new char[m][n]; ArrayList indexList = new ArrayList(); for..

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 전형적인 bfs 문제 같았다 import java.util.*; class Solution { public int solution(int n, int[][] edge) { int answer = 0; int maxValue = 0; int[] nodeLength = new int[n+1]; boolean[][] adj = new boolean [n+1][n+1]; for(int i =0;i

programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 동적계획법 카테고리에 있었지만 dfs을 통해 풀었다. class Solution { private static int answer = Integer.MAX_VALUE; private static int n; private static int target; public int solution(int N, int number) { n = N; target = number; dfs(0,0); return answer == Integer.MAX_VALUE ? -1 : answer; } public void dfs(int count, int prev){ if(co..