목록분류 전체보기 (250)

잡다한 IT 지식

백준 - 계란으로 계란치기 (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. 03:34
백준 - 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. 16:38
백준 - 한 줄로 서기(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1138 [문제 설명] [접근 방법] 완전탐색 태그로 본 문제다 보니, 바로 완전탐색밖에 떠오르지 않았다. 저번에 이렇게 아무 생각도 안하고 풀었다가 시간초과로 호되게 당한 적이 있기 때문에 완전탐색의 시간복잡도를 먼저 구했다. N명의 사람들을 줄 세우는 방법은 O(N!), N은 최대 값이 9이므로 9!이 된다. 따라서 362,880이다. 여기서 끝나는 게 아니라 입력 받은 배열들이 세워진 줄과 조건이 일치하는지 확인해야한다. 첫번째 입력 예시로 들면 2,1,1,0..
알고리즘 문제 풀이/완전탐색 2022. 1. 11. 00:44
백준 - 수강신청

본 알고리즘 풀이는 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. 22:46
백준 - Contact(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1013 [문제 설명] 주어진 조건에 맞는 문자열인지 파악하고 주어진 조건에 맞으면 YES를 출력. 맞지 않으면 NO를 출력. [접근 방법] 카테고리를 고르고 푼 문제가 아니라서, 처음에 정규식 문제인줄 몰랐다. 딱 봐도 조건이 어려워 보여서 이거 엄청 오래 풀겠네 생각했는데 +가 1개 이상에서 이상한 느낌이 들었다. 정규식이랑 비슷하네 했는데, 문제를 끝까지 읽어 보니까 그냥 정규식을 대놓고 줘놓고 푸는 문제였다. 문제에서 제공한 정규식 (100+1+ | 01)+..
알고리즘 문제 풀이/문자열 2022. 1. 5. 15:20
백준 - 수열의 합(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1024 [문제 설명] 1인 등차를 가진 배열의 합이 N이고 길이가 N이상인 것을 찾으시오 [접근 방법] 등차수열식으로 첫항을 유도하기 a는 첫항, d는 등차, n은 수열의 순서라고 할 때 An = a+(n-1)d Sn(1번부터 n번까지 수열의 총합) = (첫항+끝항)/2*전체개수 = ((2a+(n-1)d)/2)*n == N 현재 우리에게 주어진 조건은 N과 L a에 대한 식으로 만들자 (2a+n-1)*n = 2N => (2a+n-1) = 2N/n => 2a = 2..
알고리즘 문제 풀이/수학 2022. 1. 4. 22:59
이전 Prev 1 ··· 23 24 25 26 27 28 29 ··· 42 Next 다음