본문 바로가기

알고리즘 문제 풀이207

백준 - 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.
백준 - Contact(Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1013 [문제 설명] 주어진 조건에 맞는 문자열인지 파악하고 주어진 조건에 맞으면 YES를 출력. 맞지 않으면 NO를 출력. [접근 방법] 카테고리를 고르고 푼 문제가 아니라서, 처음에 정규식 문제인줄 몰랐다. 딱 봐도 조건이 어려워 보여서 이거 엄청 오래 풀겠네 생각했는데 +가 1개 이상에서 이상한 느낌이 들었다. 정규식이랑 비슷하네 했는데, 문제를 끝까지 읽어 보니까 그냥 정규식을 대놓고 줘놓고 푸는 문제였다. 문제에서 제공한 정규식 (100+1+ | 01)+.. 2022. 1. 5.
백준 - 수열의 합(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.
백준 - 숫자 카드 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/10815 [문제 설명] 카드가 있으면 1을 출력, 없으면 0을 출력. [접근 방법] 1.딱 봤을 땐 O(NM) 문제. 연산횟수 50만*50만 => 좋지 않은 선택 2.이분탐색 O(NlogN) 문제. 연산횟수 50만*log50만 => 할만해보임 3.해싱을 이용하면 O(N) + O(M). 연산횟수 50만+50만 => 최고 [이분탐색] import java.io.BufferedReader; import java.io.IOException; import java.io.I.. 2022. 1. 4.

티스토리툴바