평생 공부하며 나아가기 평생 공부하며 나아가기

Algorithm/구현(Brute force, Back tracking, etc.)

• [Codility - Counting Elements] PermCheck

  Algorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 17. 15:30

  https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/ PermCheck coding task - Learn to Code - Codility Check whether array A is a permutation. app.codility.com - 리뷰하기도 조금 민망한 문제.. N은 100,000이하이므로 O(NlogN)이하의 알고리즘을 구현해야 한다. function solution(A) { let N = A.length A.sort((a,b)=>a-b) for(let i = 0; i < N; i++){ if(A[i] !== i+1) return 0 } return 1 } - 1부터 N까지의 숫자 중 비어있는 숫자가 1..

  Read More
• [Codility - Arrays] TapeEquilibrium

  Algorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 17. 14:57

  https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ TapeEquilibrium coding task - Learn to Code - Codility Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|. app.codility.com - Array의 element 최대 수는 200,000이다. 따라서, O(N^2)의 풀이법을 하면 당연히 시간초과가 날 것이다. function solution(A) { let answer = Number.MAX_SAFE_INTEGER for(let i = 0; i < A.length; i++){ let candid..

  Read More
• [Codility - Arrays] PermMissingElem

  Algorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 16. 15:25

  https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/ PermMissingElem coding task - Learn to Code - Codility Find the missing element in a given permutation. app.codility.com - 1부터 N+1까지의 N개의 숫자 중 누락된 숫자를 찾는 문제 - Array 객체를 만들고, 0으로 채워준다. 그 후, A를 순환하면서 해당 수를 index로 활용하여 새로 만들 배열의 해당 index값에 ++를 해준다. ( 이 부분은 Array 객체를 0이 아닌 true로 초기화 해 준 후 false로 바꾸는 로직도 좋다.) - Array 객체..

  Read More
• [Codility - Time Complexity] FrogJmp

  Algorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 16. 10:22

  https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/ FrogJmp coding task - Learn to Code - Codility Count minimal number of jumps from position X to Y. app.codility.com - X,Y,D의 범위는 10억이 넘어간다. 따라서, 시간복잡도를 잘 신경써야한다. 보통 연산횟수가 1억이 넘어가면 시간초과가 뜬다. - Y가 X보다 작아질 때 까지 Y-D를 계속 하는 방법은 시간초과가 떠버리고 만다. - 따라서, Y-X를 D로 나눈 몫을 구하고 (answer에 대입), 만약 Y-X를 D로 나눈 나머지가 0이 아니면, Y에 도달하기 위해 추가로 1번을 더 ..

  Read More
• 백준 17140 이차원 배열과 연산

  Algorithm/구현(Brute force, Back tracking, etc.) 2021. 3. 4. 17:11

  while문을 통해 answer= 열의 갯수 시 'r연산' 적용 0. 가장 먼저, vector 벡터를 만든다.(한 개의 행마다 진행할 것임) 1. for문 통해 해당 행에 있는 숫자 갯수 조사 후(index 사용) pair쌍을 벡터에 push_back 2. 내가 정해둔 기준에 따라 벡터를 정렬한다. (second 먼저 비교하고 그 다음 first 순으로 오름차순 정렬) 3. 벡터를 for문으로 돌리면서 arr를 최신화. 이 때 size 비교하면서 max 조사한다. max * 2가 결국 다음 col 값이 된다. 4. index 초기화 후 다음 행 진행 5. 만약 모든 행 연산 완료시 col 최신화 2. else 'c연산' 적용 0. 가장 먼저, vector 벡터를 만든다.(한 개의 열마다 진행할 것임) 1..

  Read More