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 두개를 준비합니다. 맨 앞 인원과..
www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 접근법 S층에서 G층까지 가는 최소 버튼수를 구해야한다. 최단거리를 구할 때 사용할 수 있는 BFS를 사용해도 되는지 체크해본다. 최대 백만번을 초과하지 않으므로 BFS를 충분히 사용가능하다. 아래는 코드입니다. 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42..
https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 문제 접근법 입력 값과 명령어를 저장할 queue를 만든다. 4가지 명령어를 수행할 때 방문을 체크하기 위하여 bool 값 배열을 준비한..
https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 접근법 점화식을 세워 접근 하면 된다. 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다. 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다. 단, 2x1 타일 대신 2x2 타일을 사용할 수도 있으므로 DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2] * 2가 성립한다. 아래는 ..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 접근법 점화식을 세워 접근 하면 된다. 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다. 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다. DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2]가 성립한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 1..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 접근법 제일 작은 수 부터 X까지 갈때의 경우의 수를 구한다. 해당하는 배열에 가장 작은 경우의 수를 넣는다. 아래는 코드입니다. 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 27 28 29 30 31 32 #include #include using namespace std; int check[1000001]; int main() { check[1] = 0; int n; scanf("%d", &n); for (int i = 2; i
https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 1+3 (3+1) 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 접근법 이전의 만들 수 있는 방법의 수에 그 다음 수가 추가 되었을 경우 만들 수 있는 경우의 수를 추가하는 방식으로 진행한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..
