알고리즘

https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 규칙도 전혀 없고, 계산하다 중간에 멈추고 가지치기할 만한 규칙도 보이지 않는다. 그냥 다 구해서 완전제곱수를 찾아 최대인지 비교하는 게 최선일 것 같다. 최대 9x9 배열이고 -> 81 step은 최대 -8부터 8까지 될 수 있음 -> 최대 1~8 81 x 8 x 8 = 5184 5184 정도의 경우의 수면... 다 비교하는 게 나쁘지 않을 지도 모르겠다. 완전제곱수인지 판별하는 방법은..

1005 파스칼의 삼각형(D2) https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5P0-h6Ak4DFAUq&categoryId=AV5P0-h6Ak4DFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나의 위의 2개를 어떻게 찾아낼건지가 관건이다. 0 0 0 0 0 0 0 0 0 0 배열로..

https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 가장 먼저 떠오른 방법은 갈 수 있는 길 중 k개를 선택하는 것이었다. 하지만 해당 선택한 길이 이어지는지도 체크해야하는 번거로움이 있었기 때문에 다른 방법을 사용하기로 하였다. 선택한 방법은 백트래킹이고, 가지치기 조건은 다음과 같다. k보다 커지면 가지치기 T를 지나는 경우 가지치기 dfs로 visit배열을 채워가면서 백트래킹하는 방식으로 구현하였다. 백..

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 날짜 최대 개수는 1000000이고, 매매가는 최대 10000이다. 그러면 최대 1000000*10000 정도의 결과가 나..

https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 문제풀기 전 생각 물건을 쪼개서 넣을 수 있다면 그리디 문제이지만, 사람을 쪼갤 수 없으니 완전탐색이다 최대 가치의 물건을 넣는 배낭문제로 생각할 수 있고 완전탐색 백트래킹 방법으로 생각할 수 있다 배낭문제로 생각하면 배낭의 크기가 체력의 크기(100)이므로, 크지 않은 숫자라서 배낭문제로 풀기 적합하다 세준이의 체력은 최소 1까지만 줄어들 수 있고, 0이나 음수가 되면 안되는거 고려 백트래킹으..

완전 탐색해야하는 문제! 백트래킹을 사용한다 dfs방식으로 해를 찾고, visit 배열을 되돌리는 방법을 사용 시간복잡도 문제로 꼭 가지치기를 해줘야한다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; //[baekjoon] java-1058 public class Main { private static int min = 3001; //(5*3*200) private static int size; private static int[][] arr; private static boolean[][] visit; public stati..

모든 쌍 최단 경로 문제를 푸는 알고리즘 모든 쌍 최단 경로 문제 각 쌍의 점 사이의 최단 경로를 찾는 문제 풀이방법 다익스트라 알고리즘 O(n³) 플로이드 워샬 알고리즘 O(n³) 플로이드 워샬 알고리즘(Floyd-Warshall) 동적계획법 알고리즘 매우 간단하여 다익스트라 알고리즘보다 효율적 음의 간선이 존재해도 모든 최단 경로를 구할 수 있음 (다익스트라는 안됨) 귀납법으로 증명이 가능하다 간단한 원리 어떤 점을 경유하는 거리와 다이렉트 경로 중 작은값을 선택하여 갱신함 D[2,3] 이라는 2부터 3의 거리가 있다면 1을 경유하는 거리 D[2, 1] + D[1,3] 원래거리 D[2,3] D[2,3] = min( D[2,3], D[2,1] + D[1,3] ) 1을 경유하는 거리 비교 후 갱신, 2를..

https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net bfs를 사용한 풀이(내 풀이) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; //[baekjoon] java-1058 public cla..

https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 내 풀이 설명 나올 수 있는 가장 짧은 경우는 짝수길이일 때: 짝수길이 팰린드롬으로 만들어지는 경우 (ex. baab) 홀수길이일 때: 홀수길이 팰린드롬으로 만들어지는 경우 (ex. bbabb) 문자열 길이가 L이라면 L/2 - 1 인덱스부터 짝수길이 팰린드롬/ 홀수길이 팰린드롬을 만들어보고 인덱스를 하나씩 늘려가면서 비교한다 L/2 - 1 인덱스가 가장 짧은 경우이고 인덱스가 하나씩 늘어날수록 팰린드..

브론즈 문제는 너무 쉬워서 바로 실버를 푸는 것도 괜찮을 것 같은 브루트포스 문제! 실버문제들을 풀어보려고 한당 1476 날짜제작 실버5 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer..