IT Room IT Room

분류 전체보기

• Lesson 3 - TapeEquilibrium

  알고리즘/codility사이트 2021. 6. 28. 03:28

  문제 input : 배열 A output : 차이의 minimum 값 배열 A는 [-1000,,1000]범위 안의 숫자를 포함하고 2~100,000크기를 가진다. A를 각 기준점으로 자르고 기준점의 왼편의 숫자들의 합, 오른편의 숫자들의 합의 차이의 절댓값들 중 가장 작은 값을 return해라. 기준점은 0

  Read More
• Lesson3 - PermMissingElem - with Counting Sort

  알고리즘/codility사이트 2021. 6. 28. 02:37

  문제 input : 배열 A output : int형 숫자 배열 A는 하나의 숫자를 빼고 1부터 N+1까지의 숫자가 들어가 있다. 배열에서 제외된 숫자를 찾아서 출력하라. ex) A[0] = 2, A[1] = 3, A[2] = 1, A[3] = 5 풀이 누가 쫒아오는 것도 아닌데, 정답률 90%를 맞았다. why? 문제에서 A에 들어갈 수 있는 숫자 범위가 [1~(N+1)]까지고 N(배열의 크기)의 범위는 [0~100000]이다. 따라서 N이 100000일 경우를 고려해주지 않았다. 코드에서 number배열의 크기를 +1 해주면 해결될 문제일 것 같다. 생각보다 약 10만이라는 작은 숫자를 가지기 때문에 알고리즘은 계수 정렬을 이용했다. 따라서 시간복잡도는 O(N)이라고 예상한다! 각각의 숫자를 담아줄 ..

  Read More
• Lesson3 - FrogJmp

  알고리즘/codility사이트 2021. 6. 27. 21:15

  문제 input : 현재 개구리의 위치 X, 목표 위치 Y, 개구리가 뛰는 fixed 된 거리 D output : Y보다 더 멀리 혹은 Y 에 도착하기 위해서 뛰어야 하는 jump 수 X, Y, D가 10억 이하이고 X

  Read More
• Lesson2 - OddOccurrencesInArray - with unordered_map

  알고리즘/codility사이트 2021. 6. 26. 21:56

  문제 input : 홀수 크기의 배열 A output : pair를 갖지 못한 값 배열 A의 각각의 값은 index 순서대로 같은 값을 가지면 pair를 맺는다. 그중 pair를 맺지 못한 배열 안의 값을 구하라. 풀이 시간복잡도는 N크기만큼 for문을 돌고 for문안에 unordered_map의 find작업만 해서 O(N) * O(1) => O(N)으로 예상한다. A의 값을 모두 조사하기 위해서 for문을 호출한다. A[i] 의 map의 key값으로 설정하고, key값으로 임의로 지정한 boolean value값이 있는지 찾는다. -> O(1) key값이 나온 적이 없는 경우 OddOccurrences의 후보. key값이 나온적이 있는 경우 pair를 맺고 map에서 제외시킨다. 문제에서 하나를 제외하..

  Read More
• Lesson2 - CyclicRotation - with Array

  알고리즘/codility사이트 2021. 6. 26. 21:09

  문제 input = vector A, 회전 횟수 K output = vector target A를 K만큼 회전시킨다음 A를 출력해라 풀이 굉장히 간단한 문젠데, 87% 정답률을 가졌다. => 최댓값만 신경 쓰느라 배열의 크기가 0의 값을 가지고 K값이 0일 수도 있다는 가정은 무시했다! 배열의 값들을 회전시키는 rotate함수를 만들어서 K만큼 호출시킨다. 임시 값을 저장하는 tmp변수 2개를 이용해서 각 배열에서 값들을 옮겨준다. A의 값을 계속해서 input으로 넣어줄 수 있었지만, 메모리를 생각해서 전역 변수로 target 배열 선언! 정답률 87% 코드 #include #include using namespace std; vector target; void rotate(){ int size = t..

  Read More
• Lesson1 - Binary Gap - with Bit

  알고리즘/codility사이트 2021. 6. 26. 20:34

  문제 binary gap을 출력하는 함수를 완성해라 binary gap이란? 1로 둘러싸인 0의 최대 길이. => ex) 10001000100001의 binary gap은? 3 vs 3 vs 4 -> 4 input으로는 int형의 숫자가 주어지고 binary gap을 가지는 대상은 input을 bit형으로 바꾼 값이다. 풀이 1. 비트를 하나씩 출력해서 만드는 기능이 먼저 필요하다. 참고한 사이트는 https://steemit.com/kr-dev/@codingman/c-17--1562807878836 요기. 적당한 자릿수를 가지는 숫자 flag가 1이 될때까지 flag = flag /=2를 해주고 (bit 수를 shift >>1 해주는 것과 동일) flag의 비트수는 EX) 10000-> 1000 -> ..

  Read More
• codility에서 문제 풀어보기(short&fast project)

  알고리즘/codility사이트 2021. 6. 26. 19:59

  최근 코딩테스트를 보다가 어이없는 실수를 했다. (문제를 제대로 읽어보자 제발!) 파일형식으로 인풋을 제공하는 방식을 처음 접해서 코드에 fstream 라이브러리를 추가하고 앉아 있었다,, 그땐 그냥 예시로 인풋 형식을 보여주는 파일이었는데 너무 이입을 해버렸나 다음에 비슷한 형식을 가진 코딩테스트를 봤고 그때 접속한 사이트가 바로 codility 근데 곧 또 다른 기업의 코테를 codility사이트에서 보는데 짧은 기간동안 문제를 풀면서 적응부터 좀 하고, 코테 보고 나서 여기 문제들도 풀어봐야겠다.(지금 풀고 있는 문제는..?) (6/26~6/28)까지 문제 풀이 시작! ※ 그리고 가입하는 과정에서 엄청 해맸는데 codility사이트 그대로 들어가기보단 여기로 들어가는게 제일 빠른 루트인것 같다. h..

  Read More