개인 공부/코딩테스트102 [C++][백준] 14502번 연구소 :: seoftware 소스코드 BFS, 브루트포스 #include #include using namespace std; int N, M; int map[8][8]; int temp[8][8]; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; int answer = 0; //temp에 기존 map을 복사하는 함수 void copyMap(int (*from)[8], int (*to)[8]) { for (int n = 0; n < N; n++) { for (int m = 0; m < M; m++) { to[n][m] = from[n][m]; } } } //[BFS] 벽을 3개 세운 후 바이러스를 퍼뜨리고 전염되지 않은 곳을 세준다. void spreadVirus() { int r.. 2020. 4. 10. [C++][leetcode] Middle of the linked list :: seoftware 소스코드 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* middleNode(ListNode* head) { int sz = 0; ListNode *cur = head; while(cur != NULL){ sz++; cur = cur->next; } sz /= 2; cur = head; for(int i = 0; inext; } return cur; } }; head가 포인터이므로 cur도 포인터로 선언해야 한다! 2020. 4. 9. [c++][leetcode] Counting Elements :: seoftware 소스코드 class Solution { public: int countElements(vector& arr) { int answer = 0; unordered_map cnt; for(int i : arr){ cnt[i]++; } for(int i = 0; i 0 && cnt[i+1] > 0){ answer += cnt[i]; } } return answer; } }; unordered_map을 이용하여 arr에 있는 값을 인덱스(i)로 하여 cnt[i] 를 ++해준다. 2020. 4. 7. [c++][leetcode] Group Anagrams :: seoftware 소스코드 class Solution { public: vector groupAnagrams(vector& strs) { unordered_map map; vector answer; int idx = 0; for(string s : strs){ sort(s.begin(), s.end()); map[s].push_back(strs[idx]); idx++; } for(auto m : map){ answer.push_back(m.second); } return answer; } }; 새롭게 알게된 tip 1. string도 sort를 사용할 수 있다. → sort(str.begin(), str.end()); 2. hash_map 또는 unordered_map을 사용하면 string을 인덱스로 사용할 수 있다. .. 2020. 4. 7. [C++][DP][백준] 2×n 타일링 2 :: seoftware 문제 접근 2020/04/07 - [IT/코딩테스트] - [C++][백준] 11726번 2×n 타일링 :: seoftware [C++][백준] 11726번 2×n 타일링 :: seoftware 문제접근 다이나믹 프로그래밍, DP 가로의 길이가 n인 직사각형을 타일로 채우는 방법은 가로의 길이가 n-1인 직사각형을 타일로 채운 상태에서 2*1 타일을 1개 붙이는 방법과 가로의 길이가 n-2인 직사각형을 타.. seoftware.tistory.com 이전 문제랑 매우 유사하다. 둘 다 이전까지 구한 값을 바탕으로 관계식을 세워서 푸는 다이나믹프로그래밍 문제이다. 다만 다른 점은 이 전에는 n-2에서 n이 되는 경우가 한 가지, n-1에서 n이 되는 경우가 1가지 였는데, 이 문제에서는 n-2에서 n이 되는 .. 2020. 4. 7. [C++][백준] 11726번 2×n 타일링 :: seoftware 문제접근 다이나믹 프로그래밍, DP 가로의 길이가 n인 직사각형을 타일로 채우는 방법은 가로의 길이가 n-1인 직사각형을 타일로 채운 상태에서 2*1 타일을 1개 붙이는 방법과 가로의 길이가 n-2인 직사각형을 타일로 채운 상태에서 1*2 타일을 2개 붙이는 방법이 있다. 따라서 가로의 길이가 n인 직사각형을 타일로 채우는 관계식은 다음과 같다. ( 가로의 길이가 n인 직사각형을 타일로 채우는 방법의 수 ) = ( 가로의 길이가 n-2인 직사각형을 타일로 채우는 방법의 수 ) + ( 가로의 길이가 n-1인 직사각형을 타일로 채우는 방법의 수 ) 소스코드 #include using namespace std; int dp[1001]; int main(void) { int N; cin >> N; dp[1] =.. 2020. 4. 7. [C++][leetcode] Best Time to Buy and Sell Stock II :: seoftware 문제 접근방법 prices의 한 원소가 다음 원소와의 차이를 계산하여 양수이면 더해주고 음수이면 넘어간다. 양수이면 가격이 오르는거니까 현재 원소가 buy 가격, 다음 원소가 sell 가격이 된다. 소스코드 class Solution { public: int maxProfit(vector& prices) { int answer = 0; if(prices.size() 0) answer += (prices[i+1] - prices[i]); } return answer; } }; 1. prices의 원소가 1개 이하인 경우에는 buy 와 sell 을 진행하지 않으므로 0을 리턴한다. (이 조건 없으면 런타임 에러) 2. 0부터 전체개수 -1 까지의 모든 가격을 바로 다음 가격과 비교한다. 만약 양수이면 ans.. 2020. 4. 5. [C++][leetcode] Move Zeros :: seoftware 문제 접근방법 1. 0이 아닌 숫자들은 배열의 앞에서부터 채워나가고 0이면 넘어간다. 2. 1번을 하고 남은 배열의 인덱스는 모두 0으로 채운다. 소스코드 class Solution { public: void moveZeroes(vector& nums) { int idx = 0; for(int i : nums){ if(i != 0) { nums[idx] = i; idx++; } } for(int i =idx; i 2020. 4. 5. [C++][leetcode] Maximum Subarray :: seoftware 문제 접근방법 다이나믹 프로그래밍을 사용하려고 했는데 굳이 새로운 배열을 만들 필요는 없을것 같아서 max 값을 계속 업데이트 해주는 방식으로 접근! 소스코드 class Solution { public: int maxSubArray(vector& nums) { int max = 0; bool all_negative = true; for(int i = 0; i 0){ int tmp = 0; all_negative = false; for(int j = i; j max) max = tmp; } } } if(all_negative) { max = nums[0]; for(int i : nums){ if(max < i) max = i; } } return max; } }; 빨리 풀라고 시작이 양수인 것만 subar.. 2020. 4. 3. 이전 1 2 3 4 5 6 7 ··· 12 다음
