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/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr numbers의 길이가 20개 이하라는 점과 가능한 연산의 수가 +, - 두 가지라는 점을 먼저 생각해야 합니다. 이것은 모든 케이스에 대해서 계산해도 2의 20승인 1,048,576이므로 시간초과가 발생하지 않는 것을 알 수 있습니다. 문제 접근법 number 배열에 있는 값들을 재귀함수를 이용하여 모든 계..
https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr stack을 사용하여 풀 수 있는 문제입니다. 문제 접근법 stack에 number의 원소 하나를 넣습니다. 다음 원소가 들어가기 전에 stack에 있는 원소가 다음 원소보다 작을 경우 해당 원소를 stack에서 제거하고 k를 1감소시킵니다. 제거가 됬을 경우 다시 stack안에 있는 원소와 다음 원소를 확인합니다. stack에 있는 원소가 다음 원소보다 작다면 이번에도 stack에서 원소를 제거 후 k를 1감소시킵니다. 위 작업을 k가 0이 될 때 까지 반복합니다. stack에 남아있는 값들을 string 배열에 더해주고 reverse ..
https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr sort와 그리디 알고리즘을 사용하면 해결할 수 있는 문제입니다. 문제 접근법 보트에 탈 수 있는 인원의 최대가 2명이라는것을 생각합니다. 가장 베스트한 케이스는 가장 가벼운 사람과 무거운 사람이 탔을때 한계치를 넘지 않는것입니다. 이를 위하여 sort를 사용합니다. 앞과 뒤를 체크하기 위한 index 두개를 준비합니다. 맨 앞 인원과..
https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제를 보자마자 단순하게 2중 for문을 사용해서 다 확인해야겠다는 생각을 할 수도 있다. 하지만 그럴경우 시간 복잡도가 1,000,000 * 1,000,000이므로 시간초과가 날 것이다. HINT : 이 문제는 sort와 substr을 통하여 간단하게 해결 할 수 있다. 더보기 문제 접근법 phone_book을 sort한다. 일반적으로 sort시 오름차순으..
https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr skill_trees에 있는 스킬트리중 익힐수 있는 스킬트리의 갯수를 출력하는 문제입니다. 문제 접근법 skill_trees의 원소에 접근해야하고, skill의 각각의 문자들을 skill_tress원소의 길이만큼 확인해야 하므로 3중 for문을 사용하면 좋을것 같다는 생각을 할 수 있습니다. skill의 최대 길이는 26, skill_trees의 최대 길이는 20, skill_trees의 원소의 최대 길이는 26입니다 그러므로 시간복잡도는 26 * 20 * 26으로 3중 for문을 사용해도 괜찮다는 결론이 나옵니다. 3중 for문을 돌며 ski..
https://programmers.co.kr/learn/courses/30/lessons/12901 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 문제 접근법 다른 년도를 신경 쓸 필요없이 2016년만 신경쓰면 되는 문제입니다. 요일에 대한 string 배열(저는 answer로 표현하겠습니다)과 1월~12월에 해당하는 일수에 대한 int 배열을 준비합니다(저는 month로 표현하겠습니다). for문을 통해 a월 이전까지의 month배열값을 더해줍니다(이 값을 num이..
https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 문제 접근법 바구니가 모든 인형이 들어갈만큼 크다고 했으므로 moves의 크기만큼의 vector를 준비한다. moves의 값을 y값으로 두고 board[x][y]를 x를 0부터 borad의 size - 1만큼 순회하면서 board[x][y]가 0이 아닌값을 찾는다. vector의 index가 0일경우(vector에 아무것도 안들어온 상태일 경우) vector[index]에 board[x]..
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 ..
https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 접근법 전체 인원이 체육복을 가지고 있다고 가정한다. reserve에 해당하는 인원들에게는 체육복을 하나씩 더 추가한다. lost에 해당하는 인원들에게는 체육복을 하나씩 제거한다. 자기의 체육복이 2개 일 때 체육복을 분배한다. 아래는 해당 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..
