https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 크루스칼 알고리즘이나 프림 알고리즘을 알고 있다면 풀 수 있는 문제입니다. 문제 접근법 크루스칼 알고리즘을 사용하기 위하여 비용에 관하여 오름차순으로 정렬해줍니다. 자기 자신이 루트의 최상위로 인식하도록 초기화를 해줍니다. 모든 노드를 탐색하면서 진행하되, 현재 노드와 다음 노드가 루트가 다를 경우 연결합니다. 아래는 코드입니다. 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..
https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 입국심사를 기다리는 사람의 최대수가 10억명인것을 보면 for문을 사용해도 시간초과가 날수있다는 것을 생각하고 다른 방식의 풀이를 생각해야합니다. 문제 접근법 for문으로 해결하기에는 인원수가 너무 많으므로 최소치와 최대치를 설정하고 중간값을 통해 최소, 최대치를 갱신하며 진행하는 이분탐색을 사용한다. 최소치는 1분 걸리는 심사관이 있을 때 입국심사를 기다리는 사..
https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr sort후 routes를 비교하는 방법으로 문제를 해결할 수 있습니다. 문제 접근법 sort를 사용하여 routes를 오름차순으로 정렬한다. 처음 진입한 차량의 나간 시간을 저장한다. 그 다음 차량의 들어온 시간이 저장된 시간보다 작을경우 저장값을 저장값과 들어온 차량의 나가는 시간과 비교하여 작은값으로 바꿔줍니다. 그 다음 차량의 들어온 시간이 저장된 시간보다 클 경우 저장값을 들어온 차량의 나가는 시간으로 변경하고 카메라 수를 증가시킵니다. 아래는 코드입니다. ..
https://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 최상단부터 하단까지 거쳐간 숫자의 합을 누적하면서 비교하는 방식으로 해결할 수 있는 문제입니다. 문제 접근법 각 층별로 누적값을 저장하기 위한 배열을 선언한다. 맨 좌측과 맨 우측은 위에서 내려올수 있는 방법이 한가지 뿐임을 안다. 맨 좌측과 우측을 제외하고는 자신의 왼쪽 위와 오른쪽 위에 누적값이 내려올 수 있다는 것을 인지한다. 아래는 코드입니다. 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..
https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 해당 좌표까지 갈 수 있는 경우의 수들을 합쳐서 풀 수 있는 문제입니다. 문제 접근법 시작점을 기준으로 오른쪽 아래쪽으로만 움직일 수 있으므로, 시작점 모든 우측열과 시작점 모든 아래행을 1로 체크한다. 시작점 모든 우측열과 아래행을 확인하며 물이 발견시 그 부분부터 모든 부분을 0으로 바꾸어준다. 오른쪽과 아래쪽만으로 움직일 수 있으므로, 도착지 기..
https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr DFS를 이용하면 풀 수 있는 문제입니다. 문제 접근법 컴퓨터 방문 여부 체크를 위한 bool 배열을 선언한다. 0번 컴퓨터 부터 n - 1번 컴퓨터 까지 연결된 컴퓨터 방문 여부 체크 함수를 시행한다(단, 해당 컴퓨터의 bool 배열이 방문하지 않음으로 체크되어 있는 컴퓨터만 시행한다). 해당 함수가 시행된 횟수가 네트워크의 갯수와 같다. 아래는 코드입니..
https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 문제 접근법 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다. 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다. DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2]가 성립한다. 아래는 코드입니다. 1 2 ..
