알고리즘/백준

알고리즘 공부 중 내가 정렬에 익숙하지 않다는 걸 알아냈다! comparator도 기억이 잘 안났고, 이름은 오름차순 정렬하면서 성적은 내림차순 정렬하는 등 두 번 이상 정렬하는 것도 헷갈렸다. 그래서 이번에 소팅관련 문제를 싹 풀고 익숙해져보려고 한다! 2757 세수정렬(브론즈4) https://www.acmicpc.net/problem/2752 2752번: 세수정렬 정수 세 개가 주어진다. 이 수는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 수는 모두 다르다. www.acmicpc.net 세 개의 수를 정렬하는 방법을 찾는다 그냥 sort쓰면 될듯 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 체스를 안한 지 오래돼서 퀸이 갈 수 있는 곳이 기억안났음. 구글링 해봤다 딱히 규칙이 보이지 않음. visit배열과 백트래킹을 사용해야겠다고 생각함. 1행의 모든 칸에 대해 퀸이 놓였다고 생각하고 다음 놓을 수 있는 자리에 퀸을 놓기 (visit = true) 퀸이 놓인 행은 올킬이니까 다음 행부터 빠르게 찾기(가지치기) 행마다 한 개씩 안놓이면 N개의 queen을 놓을 수 없음 -> 가지치기 풀이 public..

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 정도의 경우의 수면... 다 비교하는 게 나쁘지 않을 지도 모르겠다. 완전제곱수인지 판별하는 방법은..

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://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..

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..

브루트포스로 문제를 풀어야만 하는 경우에 다른 방법을 시도하다 시간을 낭비한 적이 많다. 아직 브루트포스 방식에 익숙하지 않기 때문이라고 생각한다. 그래서 해당 풀이법과 관련있는 문제들을 많이 풀어보려고 한다.! 브루트 포스(bruteforcing) brute: 짐승 같은, 난폭한 brute-force: (정제되지 않은) 난폭한 힘, 폭력 이론적으로 가능한 모든 경우의 수를 찾아보는 방법 시간과 자원이 많이 드는 무식한 방법 가장 확실하면서 정확도 100%를 보장함 1837 암호제작 브론즈3 https://www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키..