전체 글 (229) 썸네일형 리스트형 NN 단표 문제구구단표처럼 NN단표를 만들었다.NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다. 입력첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같고, 10,000,000,000보다 작거나 같은 자연수이다. 출력K번째 원소를 출력한다. 예제 입력3 7 예제 출력6 풀려고 고민하다.. 숫자 개수 세기 문제n개의 숫자가 주어지고, q개의 질문이 주어진다. 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다. q개의 질문에 모두 답하는 프로그램을 작성하시오. 입력첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 주어지는 q개의 질문은 모두 1000이하이다. 출력각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다. 예제 입력10 4 1 3 4 3 2 3 1 2 5 10 1 3 9 10 예제 출력2 3 0 1 이 문제가 너무너무너무 안풀려서 며칠동안 고민한 결과 겨우겨우 세번째 시도만에 풀게 되었다.입력이 10만개 이기 때문에 .. 이진탐색 (binary search) (1) 재귀적 구현 이진탐색은 처음부터 끝까지 한개씩 확인하면서 찾는 선형탐색의 시간복잡도 보다 훨씬 빠른 의 시간복잡도를 가지고 있는 함수다. 하지만 이진탐색의 시간복잡도가 의 성능을 가지려면 전제조건이 필요한데, 배열이 정렬 되어있어야 한다. 이진탐색은 정렬되있는 배열에서 중간값을 확인하여 중간값보다 작으면 작은쪽을, 크면 큰쪽에서 다시 이진탐색을 수행하는 탐색이다. 이진탐색의 재귀적과 비재귀적 두가지 방법으로 구현할 수 있는데, 여기에선 재귀적으로 구현을 해볼것이다. 이미지 출처 : https://anster.tistory.com/152 위의 사진에서 만약에 내가 찾는 숫자가 76이라고 가정해보자. 1. 처음에 중간값 47을 찾고 47은 내가 찾는 76보다 작기 때문에 오른쪽에서 다시 이진탐색을 한다. 47보다 작은 .. 퀵정렬 (quick sort) 퀵정렬도 합병정렬과 마찬가지로 시간복잡도가 으로 빠르게 정렬할 수 있는 효율적인 정렬이다. 이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=hero1014&logNo=20191727330&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dimages%26cd%3D%26ved%3D2ahUKEwjX0NO0upzgAhUx7GEKHbbxC8AQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252Fhero1014%252F20191727330%26psig%3DAOvVaw2SoIOMtqZXX83.. 합병정렬 (merge sort) 선택, 삽입, 버블정렬의 시간 복잡도는 이지만 합병정렬의 시간 복잡도는 으로 더 빠르게 정렬할 수 있다. 합병정렬의 절차를 그림으로 보게 되면 이렇게 된다. 이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=itperson&logNo=220833815418&categoryNo=89&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dimages%26cd%3D%26ved%3D2ahUKEwitzbP5upzgAhWXMt4KHYBVCpQQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252FP.. 이전 1 ··· 26 27 28 29 다음
