매일 조금씩

문제 https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 풀이 설명은 복잡하게 해놨는데, 문제는 굉장히 쉽다. A와 B를 오름차순으로 정렬하고 B를 기준으로 순회하면서 현재 B값이 A보다 같거나 작을 경우 B의 다음 index 체크 현재 B값이 A보다 큰 경우를 A의 index를 증가 A: 1, 3, 5, 7 B: 2, 2, 6, 8 2 -> 6 -> 8 2는 3보다 작으므로 skip 순회가 끝난 ..

문제 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 예시 1) hat headgear sunglasses eyewear turban headgear headgear의 경우의 수: 3 (hat을 쓴다, turban을 쓴다, 안 쓴다) eyewear의 경우의 수: 2 (sunglasses를 쓴다, 안 쓴다) 3*2 = 6 모두 안쓸 경우 알몸이므로 ..

문제 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 풀이 큰 링의 반지름과 나머지 링 반지름의 최대 공약수를 각각 구하여 나눈다. 유클리드 호제법을 사용한다. 소스코드 package math; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokeni..

문제 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 풀이 ex) 24의 약수 2 3 4 6 8 12 2*12 = 3* 8 = 4*6 = 24 어떤 수의 모든 약수가 주어졌 때는 약수의 최소값과, 최대값을 곱하면 해당 수를 구할 수 있다. 소스코드 package math; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringToken..

문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 Greedy알고리즘을 사용해 풀 수 있는 문제이다. 무조건 싼 기름을 채워넣으면 해결할 수있다. 1번 도시 -> 2번도시 1번 도시의 1리터 당 주유비용은 5원이며 1번과 2번도시 간 거리는 2이다. 1번 도시에서는 무조건 주유를 해야 한다. 총비용 = 5*2 = 10 2번 도시 -> 3번 도시 2번 도시에서 3번 도시로 가기 위해 기름을 주유해야 하는데 1번 도시에서 미..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 마이너스 기호가 한 번이라도 나온다면 그 뒤에 나오는 숫자는 모두 음수로 더해질 수 있다. 5+10-(20+30+50)-(20+30) 단 초항은 양수이므로, -가 처음 나오기 전까지의 숫자는 양수로 더해져야 함 5+10-(20+30+50)-(20+30) 5+10 은 양수로 더하고 나머지 숫자는 음수로 더하여 합계를 내면 된다. 만약 - 기호가 없다면 모두 양수이므로 모든 숫자를 더..

문제 https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이 정수 삼각형과 유사한 문제이다. land와 동일 사이즈의 배열을 생성하여 행과 열을 순회하면서, 해당 index에서 가질 수 있는 최대 점수를 저장해나간다. 마지막 행의 최대 값이 답이 된다. 2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java) [BOJ 1932] 정수 삼각..

문제 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 풀이 dp 문제로 각 위치마다 최대값을 저장해나간다. 마지막 행에서 가장 큰 값이 답이된다. 2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java) [BOJ 1932] 정수 삼각형 (Java) 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄..

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전체 전깃줄 개수 - 전깃줄의 최장증가 수열 개수 = 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수 A 값의 순서로 B 값을 수열로 만들어보면 {8, 2, 9, 1, 4, 6, 7, 10} 이다. 이 수열의 최장증가수열의 개수를 구해서, 전체 전깃줄 개수에서 빼면 답을 구할 수 있다.입력이 정렬되어 들어오지 않기 때문에 A값 기준으로 정렬한 후, 이분 탐색 이용하..

LCS 문제란? 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다 https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에 ko.wikipedia.org 문제 https://www.acmicpc.net/problem/9251 9251번:..