본문 바로가기

Computer Science/알고리즘 문제풀이

 (49)
BaekJoon _ 백준 1149 > DP> #34 RGB 거리 RGB 거리 문제: https://www.acmicpc.net/problem/1149 알고리즘 종류: DP algorithm 1. 문제설명 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 ..
BaekJoon _ 백준 1026 > 탐색> #33 보물 보물 문제: https://www.acmicpc.net/problem/1026 알고리즘 종류 : 탐색 1. 문제설명 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.S = A[0]*B[0] + ... + A[N-1]*B[N-1]S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안된다.S의 최솟값을 출력하는 프로그램을 작성하시오.첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 1..
Programmers > 연습문제 > #32 N-Queen N-Queen 문제: https://programmers.co.kr/learn/courses/30/lessons/12952?language=java 1. 문제 설명 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다. 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요. 제한사항 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다. n은 12이하의 자연수 입니다. 2. 나의 코드 - 알고리즘을 공부..
Programmers > 연습문제 > #31 2 x n 타일링 2 x n 타일링 문제: https://programmers.co.kr/learn/courses/30/lessons/12900 1. 문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많..
Programmers > 스택/큐(Stack/Queue) > #30 기능개발 기능개발 문제: https://programmers.co.kr/learn/courses/30/lessons/42586 1. 문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 2. 나의 코드 - q: 완료되지 않은 모든..
Programmers > #28 winter recruit > #2 [JAVA] winter intern #2 1. 문제 설명 - (5,5) 2차원 평면에서 (0,0)에 물체가 있다. 이 물체에 명령어 "U","D","R","L"을 주어서 각각 위, 아래, 오른쪽, 왼쪽으로 움직일 수 있다. - 이때, 이 물체가 움직인 거리의 총 합을 구하라.- 단, 물체는 한번 지난 경로를 중복하여 지날때는 이를 무시한다.- 평면 밖을 나가게 된다면, 이를 무시하고 움직이지 않는다. 2. 나의 코드 import java.util.*; class Solution { public int solution(String dirs) { int answer = 7; int lx =0,ly=0; String [] directs = dirs.split(""); boolean flag = true; ArrayLis..
Programmers > 깊이/너비 우선 탐색(DFS/BFS) > #27 타겟 넘버 [JAVA] 타겟 넘버 1. 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 2. 나의 코드 - dfs를 통해 깊이 우선 탐색을 한다. - 연산과정을 하나의 트리로 생각해 볼때, '+'연산은 왼쪽 자식노드로 '-'연산은 오..
Programmers > 완전탐색 > #26 소수찾기(level 2) [JAVA] 소수 찾기 (Level 2) 1. 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 2. 나의 코드 - 소수를 구하기 전에 주어진 문자열에서 만들 수 있는 모든 순열을 찾아야 한다.(이게 난이도 헬...) - 1~numbers.length 까지 for문을 돌면서 각 숫자에 맞는 조합을 우선 찾고, - 그 조합을 permutation 메소드에 넣어서 순서가 있는 순열을 찾는다. - HashSet을 이용하여 중복을 제거해주고! - 그 다음 소수인지 아닌지..

티스토리툴바