본문 바로가기

algorithm/exercise

 (15)
[BOJ 2650] 백준 2650 색종이 만들기 문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할정복문제였다. 현재 위치부터 ~ 그래프 길이 끝 (N) 의 색깔이 동일하다면 색종이 하나로 표현 가능하다. 그게 아니라면, N/2 로 현재위치~ N/2 위치 까지 색깔 비교 분할한 후에, 4 구역으로 나눠서 색깔 비교 진행 import java.util.Scanner; public class Main { public static int[][] maps; p..
[programmers] 기능개발 with JAVA 문제 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자연수입니..
[programmers] 네트워크 with JAVA 문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][..
[programmers] 타켓넘버 with JAVA 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개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. 풀이 모든 ..
[BOJ 1931] 백준 1931 회의실 배정 - Python 그리디 알고리즘 공부하려고 풀었던 문제 문제 링크 : 1931 회의실 배정 문제 정리: 한 개의 회의실에서 최대 몇 개의 회의를 진행할 수 있는가? 조건 : 각 회의가 겹치면 안된다. 회의는 중간에 중단될 수 없다. 회의가 끝나면 바로 다음 회의를 진행할 수 있다. 회의 시작 시간과 종료 시간이 동일할 수 있다. 풀이 방법 : 시작 시간을 정렬을 해야하고, 끝나는 시간 기준으로 정렬을 해야한다. (최대 값을 구해야하기 때문에, 빨리 끝나는 회의를 위주로 최대한 많이 집어 넣어야하기 때문) 끝나는 시간을 기준으로, 다음 인덱스에 시작 시간을 비교하여 answer를 작업한다. def solution(conference): last = 0 answer = 0 for start, end in conference..
[BOJ 2583] 백준 2583 영역 구하기 #문제 해결 방법 DFS와 BFS 둘다 사용 가능할 것으로 예상했고, DFS를 선택해서 풀었다. x1, y1, x2, y2를 입력받을 때 마다, arr에 바로 1로 표시해주었다. 문제에서 주어진 좌표와 똑같이 표현하기 위해서, y좌표는 (n-y2) ~ (n-y1)으로 loop을 돌렸다. DFS를 호출하기전에 block 개수를 0으로 초기화한다. DFS를 호출하고, 호출할 때 마다 block의 갯수와 visit 함수에 true 값을 넣었다. #include #include #include using namespace std; //좌 우 위 아래 int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; int arr[101][101]={0,}; bool visit[101][101]={f..
[BOJ 2748] 백준 2748 피보나치 수 2 #입출력 예제 입력1 :: 10 예제 출력1 :: 55 #문제 해결 방법 dp를 사용하는 것이 최선의 방법. dp[91]의 배열을 선언한 후(**n은 최대 90까지 값을 가지므로, 91개의 배열을 선언했다.), dp[0]과 dp[1]을 활용해서, dp[2]를 구하고, dp[1]과 dp[2]을 활용해서, dp[3]을 구하는 방법으로 입력 값 까지 dp값을 구했다. dp[90] 값을 구할 때는, 값이 상당히 커진다. (**2880067194370816120) 따라서 dp배열을 long long으로 선언하는 것이 **포인트**였다. #include using namespace std; void fibonacci (int number){ long long dp[91]; dp[0]=0; dp[1]=1; for(i..

티스토리툴바