본문 바로가기

분류 전체보기351

[leetcode 4] Median of Two Sorted Arrays Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. Follow up: The overall run time complexity should be O(log (m+n)). Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2: Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] an.. 2020. 11. 7.
[백준 1182] 부분수열의 합 www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 벡터를 사용하지 않고 풀어보기! s=0일 경우 하나도 안더했을 때도 포함되므로 빼줘야 한다. 왜냐면 부분 수열의 크기가 양수이기 때문이다. #include using namespace std; int arr[21]; int n, s, answer; void dfs(int idx, int sum) { if (idx > n - 1) { if (sum == s) { answer++.. 2020. 11. 5.
[백준 9663]N-Queen www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 평소에 푸는 방법과 다른 풀이방법을 알아냈다. 각 row당 queen은 한개만 존재해야하므로 row는 무조건 1씩 증가한다. col과 왼쪽 오른쪽 대각선을 고려해주는데 왼쪽 대각선을 보면 각 대각선의 row + col 좌표 합이 일정함을 알 수 있다. 오른쪽 대각선은 row-col이 일정함 이 때 row-col은 음수이므로 offset처리를 해줘야 해서 n-1을 더해준다. // 대각선을 사용하자 #include using na.. 2020. 11. 5.
[leetcode 142] Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Notice that you should.. 2020. 11. 5.

티스토리툴바