본문 바로가기

분류 전체보기229

백준 - 경비원 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/2564 [문제 설명] 상점까지 모서리를 따라 가는 최소거리의 합 [접근 방법] 문제를 보자마자 떠오른 건 BFS였는데 읽어보니까 모서리를 따라서 가야한다는 조건이 있다. 처음엔 단순히 X좌표 Y좌표끼리 연산을 하면 모든 경우의 수를 처리할 수 있을 줄 알았는데 맞은 편에 있을 때만 성립한다는 걸 알았다. 따라서, 맞은 편에 있을 때와 나머지 경우의 수로 나눠서 풀어야 한다. 이 문제를 풀면서 아쉬웠던 점이, 맞은 편에 있는 조건을 하드코딩으로 짰다는 게 아쉽다. .. 2022. 1. 17.
백준 - 랜선 자르기(Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1654 [문제 설명] 전형적인 이분탐색을 이용하는 문제 [접근 방법] 딱 봐도 이분탐색이라 자신 있게 접근했다가, 부족함을 알게해준 문제. https://st-lab.tistory.com/269 [백준] 1654번 : 랜선 자르기 - JAVA [자바] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000.. 2022. 1. 17.
백준 - 계란으로 계란치기 (Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/16987 [문제 설명] 문제가 너무 거창하고 길어서 헤메기 좋은 문제입니다. 특히 2번 조건과 3번 조건이 엄청 헷갈렸습니다. 3번 같은 경우 아직도 헷갈립니다. 잡론은 각설하고 문제의 유형은 완전탐색으로 모든 경우의 수를 만드는 것입니다. 시간복잡도는 계란의 개수^계란의 개수라 언뜻 보면 시간 초과가 날것처럼 보이지만 계란의 개수가 최대 8개이므로 8^8 => 2^24으로 16,777,216 => 1600만밖에 되지 않습니다. import java.io.*; i.. 2022. 1. 17.
백준 - 0의 개수(java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/11170 [문제 설명] N부터 M까지 숫자를 쭈욱 썼을 때 0의 총 개수 100,115이면 101,102,103,...,110,111,112,113,114,115 [접근 방법] 규칙이 있어보이지만, 시작 번호가 주어졌다는 점에서 코드가 복잡해질 느낌이 들었다. 그래서 완전 탐색 돌렸다. 숫자는 최대 7자리수이므로 한 숫자에 최대 7번 반복. 테스트 케이스 개수*숫자의 자리수*첫번째숫자부터 끝번 숫자까지 횟수 T*7*(M-N+1) => O(TM) 대략 최대 횟수 연.. 2022. 1. 16.
백준 - 한 줄로 서기(Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1138 [문제 설명] [접근 방법] 완전탐색 태그로 본 문제다 보니, 바로 완전탐색밖에 떠오르지 않았다. 저번에 이렇게 아무 생각도 안하고 풀었다가 시간초과로 호되게 당한 적이 있기 때문에 완전탐색의 시간복잡도를 먼저 구했다. N명의 사람들을 줄 세우는 방법은 O(N!), N은 최대 값이 9이므로 9!이 된다. 따라서 362,880이다. 여기서 끝나는 게 아니라 입력 받은 배열들이 세워진 줄과 조건이 일치하는지 확인해야한다. 첫번째 입력 예시로 들면 2,1,1,0.. 2022. 1. 11.
백준 - 수강신청 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/13414 [접근 방법] 단순하게 NM하면 무조건 시간 초과. Hash 함수를 이용하여 다시 접근할 때 O(1)이어야 가능. 따라서 HashMap 사용함. [Java 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Main { public static void main(String[] args) .. 2022. 1. 9.

티스토리툴바