본문 바로가기

전체 글657

[leetcode][1492] The kth Factor of n 문제 : leetcode.com/problems/the-kth-factor-of-n/ 양수 n, k가 주어질 때, n으로 나누어 떨어지는 정수들을 오름차순 정렬했을 때, k번째로 나오는 수를 구하라. 1부터 루트 n 만큼 반복문을 돌면서 k를 감소시킨다. 만약 n이 탐색 중인 수 i 으로 나누어 떨어졌을 때 배열에 n/i를 저장한다. 탐색 중에 k가 0이 된다면 i가 정답이 된다. 만약 i의 제곱이 n이라면 반복문 중에 k를 한 번 소모하는데 벌써 사용이 되었으므로 배열에 저장하지 않는다. 탐색이 끝났을 때 배열 크기보다 k가 크다면 정답이 없는 경우이므로 -1을 반환한다. 정답이 있는 경우 배열의 뒤에서 k번째에 있는 수가 정답이 된다. 시간복잡도는 O(루트n). 소스코드 : github.com/fpd.. 2020. 12. 5.
[201201] 운전면허증 발급 오늘은 월요일. 출근 전에 중요하게 할 일이 있쥐. 기상 후 황급히 준비 후 용인면허시험장으로 향했다. 열체크 후 파란색 스티커 손에 붙이고 들어가서 면허 발급 번호표를 뽑았다. 사람이 별로 없어서 내 차례는 금방왔다. 합격증 제출. 하고 영문 이름 추가한다고 하니까 2천원이 추가로 든다고 해서 2천원이랑 신분증을 제출하면 끝. 영문 이름도 적어서 낸다. 여권 이름이랑 동일하게 쓰기! 근데 여기서 중요한게.. 여권사진을 제출안한다. 여권사진 제출하라고 해서 여권사진 재출력한건데..! 수험증 작성시 제출한 여권사진과 다른 사진을 면허증에 쓰고 싶은 경우 제출해야 하는건가...? 이유를 알 수 없다. 여튼 서류 처리를 다 해주셨으면 앉아서 잠깐 기다리라고 하신다. 면허증은 3번 창구에서 받는데 창구 위에 전.. 2020. 12. 4.
[201130] 도로주행시험 도로주행 시험 치기 전날. 긴장과 패닉. 아무것도 손에 잡히지 않았다. 자기 전에 준비물 챙겨놔야지 하고 여권사진을 찾았는데 찾을 수 없었다. 분명.. 예전 증명사진이랑 같이 둔 것 같았는데.. 40분 가량을 찾고 쓰레기통이라도 뒤질까하다가 그냥 다시 찍기로 마음먹고 불끄고 침대에 누웠다. 그 시각이 새벽 3시. 머리속에서 A, B, C, D 코스를 패스 경로인 것마냥 화살표로 그리고 또 그렸다. 그러다보니 어느새 3시반.. 불면증이 있던 때에 유튜브에서 듣던 효과좋은 ASMR을 오랜만에 켰다. 백그라운드 재생을 위해 해지했던 유튜브 프리미엄에 다시 가입했다. 그렇게 겨우 잠들 수 있었다. 도로주행 시험일.. 오후 시험이었기 때문에 시험치기 전에 사진 찍었던 사진관에 가서 여권사진을 재출력했다. 그리고 .. 2020. 12. 4.
[leetcode] [239] Sliding Window Maximum 문제 : leetcode.com/problems/sliding-window-maximum/ 정수배열 nums 이 주어지고 슬라이딩 윈도우 크기 k가 주어진다. 배열의 맨 왼쪽부터 k개를 유지하면서 오른쪽으로 탐색하는 슬라이딩 윈도우가 있을 때 슬라이딩 윈도우가 오른쪽으로 한 칸 씩 이동할때마다 해당 슬라이딩 윈도우에 있는 요소들 중 가장 큰 값을 가지는 숫자를 배열에 저장해서 반환하라. 우선순위 큐에 요소들을 저장한다. 이 때, nums 요소와 인덱스를 같이 저장한다. 우선순위는 nums 요소(정수)로 판단한다. 만약 탐색 시 탐색 중인 nums 인덱스가 k이상일 때, 우선순위 큐를 탐색하면서 큐의 top에 있는 인덱스 정보를 현재 탐색 중인 인덱스와 비교한다. 큐의 top에 있는 인덱스 정보와 현재 탐.. 2020. 11. 29.
[leetcode][416] Partition Equal Subset Sum 문제 : leetcode.com/problems/partition-equal-subset-sum/ 양의 정수로 이루어진 nums 배열이 주어질 때, 동일한 배열 합을 가지는 두 개의 배열로 분리시킬 수 있는지 구하라. nums 배열의 합을 구한다. 동일한 배열 합을 가질 수 있다는 뜻은 배열 합이 짝수라는 뜻이다. 따라서 만약 홀수라면 false를 반환한다. 배열 합 / 2를 nums 배열을 탐색하면서 요소들의 합으로 만들 수 있는지 판단하고 만들 수 있으면 true, 아니면 false를 반환한다. nums 배열 요소들의 합으로 sum/2 를 구할 수 있는지는 배낭 문제로 풀 수 있다. dp[i][j] = nums[0~i]개의 요소들로 부분집합을 만들 때, 그 요소들의 합으로 j를 만들 수 있는지 여부... 2020. 11. 28.
[DP] 배낭 문제(Knapsack Problem) 다이나믹 프로그래밍 DP의 대표 문제 중 하나인 물건을 넣느냐 빼느냐를 선택하는 0/1 배낭문제. 물건의 개수가 N이고 배낭에 담을 수 있는 최대 무게가 W이다. 물건은 종류별로 1개씩 있다. d[i][j] = 물건을 i번째 까지 배낭에 넣는다고 가정했을 때, 무게 j를 초과하지 않으면서 배낭에 넣을 수 있는 물건들의 가격의 총합의 최대값 d[i][j] = d[i - 1][j] (j = w[i]인 경우, i번째 물건을 넣을 수 있는 경우) d[i - 1][j - w[i]] : i-1번째 물건을 이용, j - w[.. 2020. 11. 28.

티스토리툴바