알고리즘 문제 풀이

[프로그래머스] 양궁대회 java

https://school.programmers.co.kr/learn/courses/30/lessons/92342 유형은 기본적인 중복순열이라서 어렵지 않은 문제인데 자꾸 시간초과가 나서 통과까지 해결하는 시간이 오래 걸렸다. private static void shot(int L) { if (L == N) { calRes(); return; } for (int i = 0; i other[i]) continue; lionList[i]++; shot(L + 1); lionList[i]--; } } 라이언이 이미 어피치 보다 해당 과녁을 많이 맞춘 경우는 더이상 화살을 낭비하지 않기 위해서 반복문을 continue시켰다. 그런데 결국 반복문으로 들어와서 해..

[백준 11049] 행렬 곱셈 순서

DP를 활용하는 문제이다. DP 문제인건 보자 마자 알겠는데 어떻게 식을 세워야 할지 몰라서 찾아보다가 아래 유튜브 영상을 보고 이해를 했다. https://youtu.be/prx1psByp7U Bottom Up 방식으로 작은 부분먼저 계산해두고 최종 결과를 계산 해 나간다. 예를 들어 A,B,C 세개의 행렬의 곱셈 연산수를 구하기 위해서는 (AB)C, A(BC) 의 연산 결과를 비교해야 한다. 이 때 괄호 안의 값인 AB, BC를 먼저 계산해서 dp배열에 저장 해 두고 최종 결과를 계산할 때 해당 값을 사용한다. 위 영상의 예제는 행렬 네개를 사용하여 설명하므로 A,B,C,D 네개의 행렬을 곱하는 예시를 들어보면 다음과 같다. 가장 처음엔 인접한 두개의 행렬들의 곱셈 연산 횟수를 계산한다. 문제에서 주..

[백준 20040/] 사이클게임 java

문제 Union-find 를 활용하는 기본적인문제이다. 선택한 두 점의 번호를 한 집합으로 합쳐가는데, 이 때 두 번호가 모두 이미 선택된(집합에 이미 속한)번호들이라면 사이클이 생긴다. 사이클이 발생하면 이후의 입력값들은 더이상 볼 필요 없이 바로 종료하면 된다. Java 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N,M; static int[] parent; public static void main(String[] args) throws Exception { BufferedReader br = new Buf..

[프로그래머스] 수식 최대화 java

https://programmers.co.kr/learn/courses/30/lessons/67257?language=java 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 주어진 연산자들의 모든 가능한 우선순위를 계산한 값이 최대인 값을 출력한다. 연산자의 종류는 +,-,* 로만 이루어져 있으므로 연산자들의 우선수위의 경우의수가 총 6가지이다. 6가지의 경우의 수를 모두 구해 놓고 각각의 경우마다 우선순위를 고려하여 수식을 계산했다. 문제에서 친절하게 long 자료형을 쓰라고도 알려주고 있다. 연산자 우..

[백준 2467] 용액 java

문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 정수를 2개 선택하는데, 그 정수 2개의 절댓값이 0에 가장 가까운 수가 되도록 선택한다. 같은 절댓값을 만드는 숫자 쌍이 여러개일 경우 아무거나 출력. 입력 첫째 줄에 전체 용액의 수 N ( N은 2이상 10만 이하) 둘쨋줄에는 각 용액의 특성 값이 공백으로 분리되어 주어짐. (각 용액은 -1,0000,0000,000 이상 1,000,000,000 이하) 용액은 오름차순으로 정렬되어 ..

[SWEA 1949] 등산로 조정

문제 가장 높은 곳에서 시작해서 현재 위치 이하인 높이로만 길을 탐색 할 수 있을 때, 최대로 갈 수 있는 길의 길이를 찾는다. 단 1번 높이를 깎을 수 있다. 이 때 깎은 후의 높이가 1보다 작아도 상관 없다. 풀이 방법 가장 높은곳에서만 시작 할 수 있으므로 map의 가장 높은 곳들을 찾아서 dfs를 시작 한다. dfs로 상하좌우 탐색하면서 현재 위치 보다 낮은 곳으로 이동한다. 높이를 깎는 것은 1회만 가능 하기 때문에 ,이 경로로 도달하는 동안 길을 깎았는지를 체크할 boolean 변수 하나를 설정해 주었다. 높이는 최대 K까지 깎을 수 있으므로 0~K 만큼 깎아본 경우를 모두 따져본다. 코드 import java.io.BufferedReader; import java.io.IOException;..