전체 글
-
[Baekjoon] 1912번 - 연속합(JAVA)Baekjoon/Silver 2024. 7. 22. 10:09
https://www.acmicpc.net/problem/1912조건 체크조건은 간단하다, 입력으로 주어진 n개의 정수중에서 연속된 수의 합 중 가장 큰 값을 고르면 된다.예제에서는10 -4 3 1 5 6 -35 12 21 -1 이 주어졌고,이중에서 12 21을 더한 33이 가장 크다.풀이동적프로그래밍으로 문제를 접근하면 간단하게 풀 수 있는 문제이다.주어진 입력을 저장하는 배열과, 합을 저장하는 배열만 존재하면 된다.max 값으로 첫번째 인덱스 값을 저장하고 1번째 인덱스부터 for문을 통해 현재 인덱스와 이전 연속합중 큰 값을 해당 인덱스 연속합으로 저장하고,해당 인덱스 연속합과 max값을 비교해 큰값을 max에 저장하면 된다.import java.io.*;import java.util.StringT..
-
[Baekjoon] 1254번 - 팰린드롬 만들기(JAVA)Baekjoon/Silver 2024. 7. 5. 08:25
https://www.acmicpc.net/problem/1254조건 체크"문자열 S로 만들 수 있는 가장 짧은 문자열" 을 만들어야 하고, 앞에서 읽으나 뒤에서부터 읽으나 같은 문자열이어야 한다.예를들면 토마토 같은...예제에서 주어진 간단한 식에는 abab => ababa 등의 형태로 가운데 문자 a를 기준으로 ab, ba가 있는 형태도 있지만, abba도 팰린드롬이다.풀이입력으로 주어진 S가 팰린드롬인지부터 확인하고, 팰린드롬으로 만들 수 있는지 체크하도록 한다.예를들어 abcdefghi라는 입력이 왔을때, 문자열 길이는 9이므로, (팰린드롬의 최대길이는 입력 문자열 S*2 이다.)for문을 9/2 q부터 9까지 반복문을 통해 찾으면 된다.S = abcdefghi 일때, S에서 9/2(4.5인데 i..
-
[Baekjoon] 3019번 - 테트리스(java)Baekjoon/Silver 2024. 6. 20. 09:33
https://www.acmicpc.net/problem/3019조건 체크"블록이 떨어졌을 때, 블록과 블록 또는 블록과 바닥 사이에 채워져 있지 않는 칸이 생기면 안 된다"위 조건을 생각해보면위 처럼 두었을 때는 블록과 블록 사이에 채워져있지 않은 빨간 네모박스 위치가 존재하기에 해당 방법은 블록을 떨어뜨리는 방법의 수에는 포함되지 않는다.또한, 1번과 2번 3번의 경우에는 0도와 180도, 90도와 270도가 모양이 같기 때문에 중복으로 체크할 필요가 없다.풀이각 모양에서 블록 혹은 테트리스 필드 바닥과 닿는 부분의 높이만 구해주면 브루트 포스를 이용해 문제를 해결할 수 있다.1번 -> 0 / 0, 0, 0, 02번 -> 0, 03번 -> 0, 0, 1 / 1, 04번 -> 1, 0, 0 ..
-
[Baekjoon] 2659번 - 십자카드 문제 (java)카테고리 없음 2024. 6. 4. 11:58
https://www.acmicpc.net/problem/2659조건 체크주어지는 숫자는 0을 제외한 1 ~ 91121가 포함된 십자카드의 시계수는 1112풀이시계수의 최소값은 1이 네개인 1111이고, 최대값은 9가 네개인 9999이다. 그러므로, boolean 배열을 만들어 네자리수의 값이 시계수 일 때, true를 넣고, 중복되는 값을 체크하기 위해 map을 사용했다.예를들어 1112의 값은 1112, 1121, 1211, 2111 중 최소값인 1112만 시계수이기 때문에 boolean[1112] = true 이고, 네개의 값 모두 map에 put한다.위와 같이 1111부터 9999까지 브루트포스를 이용해 시계수 값만 true로 변경해주고, true 값이 몇번째에 나오는지 확인하면 된다.소스코드im..
-
[JAVA] 동적 계획법(Dynamic Programming)IT/Algorithm 2024. 5. 22. 10:28
Dynamic Programming(DP, 동적 계획법)1. 개요DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경쓰지 않아도 된다.큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다.2. DP를 쓰는 이유일반적인 재귀(Native Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있..
-
[JAVA] 다익스트라(Dijkstra) 알고리즘IT/Algorithm 2024. 5. 22. 10:23
다익스트라(Dijkstra) 알고리즘다익스트라 알고리즘이란BFS와 DP를 활용한 최단경로 탐색 알고리즘이다다이나믹프로그래밍인 이유는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다.다익스트라 알고리즘의 특징그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단경로를 알려준다.그래프의 간선(Edge)마다 가중치가 존재할 때 사용한다. 이 점이 BFS를 활용한 최단 경로 구하기와 다른 점이다.간선의 음의 가중치는 존재하지 않는다. 음의 가중치가 하나라도 있으면 다익스트라를 사용할 수 없다.음의 가중치가 존재하지 않기 때문에 현실세계에 사용하기 적합한 알고리즘이다.(ex. GPS, 네비게이션)출발노드, 도착노드로 구성된 이차원 배열 활용 구현..
-
[Baekjoon] 1074번 - Z (java)Baekjoon/Silver 2024. 5. 22. 09:44
https://www.acmicpc.net/problem/1074조건 체크1 0 N풀이기본적으로 Z 모양은 2x2 크기의 2차원배열에서 탐색하는 과정이다, 문제에 나와있듯 N > 1 인 경우, 배열의 크기를 2N-1 x 2N-1로 4등분 한 후 재귀적으로 방문하는것도, 2x2 크기의 2차원 배열로 탐색하기 위함이다.이를 바탕으로 N > 1보다 클 때 r과 c의 값이 2x2 크기의 2차원 배열에서 어떤 위치에 속하느냐를 찾으면 되는 것이다.예를 들어N = 3 이고, r, c가 5일 경우23 은 8이고 이를 22 크기의 배열로 4등분 했을 때, 5,5는 네번째 위치에 속해있기 때문에 앞 순서에 위치한 4x4 크기의 2차원 배열을 모두 탐색한 후라서 (4x4) x 3 을 count 에 추가해주고, 22 크기의..
-
[Baekjoon] 15998번 - 카카오머니 (java)Baekjoon/Gold 2024. 5. 16. 09:27
https://www.acmicpc.net/problem/15998조건 체크입출금 로그에서 입금 혹은 출금의 값은 2-1018 ~ 21018 의 범위이고 0이 아닌 값이다.잔액은 0보다크거나 같고 21018 보단 작은 값이다.로그가 두개 이상일 때, 이전 로그의 잔액보다 출금 금액이 클 경우 충전이 일어난다.(최소 충전 금액)충전이 한번일 경우 출력 조건에 의해 충전금액의 약수 중 아무거나 출력하면 정답이다. (두번 이상일 경우 각 충전 금액의 약수를 구하면 됨)충전을 했을 경우 잔액은 충전금액보다 작아야 한다.입출금로그에 모순이 생기는 경우도 체크해야한다. 예를들어서 잔액이 10000 인데, 5000을 출금했는데 잔액이 5000이 아닌 값이 들어오거나, 입금을 했는데 잔액이 적어지거나 너무 많아지거나 ..