본문 바로가기

알고리즘_개념 및 문제풀이

(42)
BOJ/C++/DFS/BFS 문제풀이1/#2331(반복수열)/#9466(텀프로젝트)/ C++언어로 모두 작성하였으니 참고하길 바란다. 1. #2331/반복수열 https://www.acmicpc.net/problem/2331 DFS/Directed Non-Weight Graph/Adjacency list, 수열을 Directed non-weight Graph 자료구조로 옮겨서 먼저 생각하자. 방향의 근거로는 수열은 1차원 상에서 한 방향으로 수가 계속해서 나열되는 구조이기 때문이다. 각 수열의 원소는 정점, 그것들을 간선으로 수열의 진행 순서대로 이어준다.그래프를 담을 자료구조로는 딱히 Adj list나 Matrix를 사용하지 않고 Hash map을 사용했다. DFS, BFS중에선 DFS를 사용한다. 그래프 자료구조로 담아서 DFS로 계속 수열을 증가시키면서(다음 노드, 그리고 그 다음노..
BOJ 그리디 문제 모음2/C++/30(#10610)/병든나이트(#1783)/NMK(#1201) 모두 C++로 작성하였음을 유의하자. 1. 30 (#10610) https://www.acmicpc.net/problem/10610 30 = 3 * 10 이다. 3과 동시에 10으로도 나누어 떨어져야 하므로, 우선 0이 하나 들어가야하고, 0을 제외한 나머지 숫자들의 합이 3의 배수가 되어야 30의 배수도 동시에 만족할 수 있다. 나는 먼저 string 을 순회하면서, 0이 있을때마다 카운트 해서 zeros 에 저장했고, 각 자리수의 합을 check에 더해나가는 방식으로 마킹했다. -> 이후 zeros 가 0 이거나 check이 3으로 나눠떨어지지 않는 경우는 예외처리를 해줬다. 다만, 주의할 점은 받을 N이 10^5개의 숫자로 구성되있다는 점이다. 즉, 자리수가 nnnnnn...........nnnn ..
BOJ 그리디 문제 모음1/#11047동전0/#1931회의실배정/#11399ATM/#1541잃어버린 괄호/#1744수 묶기/#2875대회or인턴 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 먼저, 그리디는 이 순간 가장 좋은 부분만을 고려해서 연산하는 것이 최적의 해가 되는 문제이다. 이게 말은 쉬운데, 증명이 어렵다. 물론, 쉬운 문제들은 굳이 증명하지 않아도 이게 그리디로 풀었을 때 최적해라는 것을 직관적으로 알 수 있다. 하지만, 문제가 어려워지면.. 아래와 같은 어려움이 따른다.. 이게 그리디로 푸는게 최적해인지..
카카오/코딩테스트 기출/추석트래픽/2018 Blind Recruitment 1차/cpp(C++)풀이 cpp(C++)로 풀었으니 참고. 카카오 기출을 한 번 풀어야겠다고 마음 먹고 처음 접한 문제다. 그냥 이름 재밌어보이는거로 잡았는데 하필이면 난이도: 상 짜리.. 눈물나게 고민하고 풀었다. 하루종일 생각했다. 솔직히 처음에 감이 안잡혀서 카카오 공식 홈페이지에 해설을 간단하게 읽어본 후 많은 고민 끝에 구현할 수 있었다.. (그러니까 후딱 안풀린다고 절대 좌절하지 말자!) 크게 아래와 같은 로직으로 생각했다. 대전제로 먼저 모든 시간은 millisecond 단위로 변환하자. 그렇다고 해도 int 범위안에 넉넉하게 담을 수 있으니 ok 각 로그 문자열마다 순회를 하면서 먼저 string을 시간으로 변환한다. 아래는 각 로그 문자열string처리 로직이다. 로그 문자열의 종료 시간(endTime)을 먼저 ..
리트코드(Leetcode)/Word_Ladder https://leetcode.com/problems/word-ladder/ Word Ladder - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 내 첫번째 코드이다. 시간복잡도는 word_length = L , size of list = M 이라 했을 때, Time Complexity 가 O(M^2 * L)이다. BFS를 잘 수행했다고 하는데, 계속해서 시간초과..... 단 1개만 다른 char를 찾을 수 있는 더 효율적인 방법을 찾아봐야겠습니다.. clas..
리트코드/leetcode/maxsubarray/부분최대합수열 Divide And Conquer.. int removeDuplicates(vector& nums) { int length = 0; if(nums.size()==1){ return 1; } if(nums.empty()){ return 0; } for(int i = 0; i < nums.size() - 1; i++){ if(nums[i] != nums[i+1]){ length += 1; nums[length] = nums[i+1]; } } nums = vector(nums.begin(), nums.begin()+length+1); return length+1; } Collapse https://leetcode.com/problems/maximum-subarray/ int solution(vector & n..
leetcode/plusone https://leetcode.com/problems/plus-one Plus One - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com vector plusOne(vector& digits) { vector answer; for(int i = digits.size()-1; i >= 0; i--){ if(digits[i] < 9){ digits[i] = digits[i] + 1; break; } else{ if(i == 0){ digits[i]=1; digits...
리트코드/Leetcode/부분수열의 최댓값 https://leetcode.com/problems/maximum-subarray Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Divide and Conquer / Time Complexity: O(nlogn) int solution(vector & nums, int l, int r){ if(l==r) return nums[l]; int m = (l+r)/2; int left_sum = nums[m]; int sum = 0;..

티스토리툴바