[코딩테스트 후기] 첫번째 코딩테스트, 문제 유형

 나의 첫 코딩테스트였다. 

 어제 메일을 받고, HackerRank 사이트에서 하는 거길래 여러가지 찾아보다가 HackerRank 사이트에서 연습을 할 수 있다는 것을 알게되었고, 그래서 어제부터 코딩테스트 연습 겸 티스토리 블로그를 시작하게 되었다. 

 

 그리고 오늘 코딩 테스트를 직접 해보았다. 12문제이고, 165분 (2시간 45분) 동안 진행되는 테스트였고, 노트북으로 진행했는데 카메라가 켜져있어야 한다. 처음에 카메라가 켜지지 않고 까맣게만 보여서 뭐지 어떻게 하는거지 하면서 찾아보다가 시간이 좀 지났고 어쨋든 잘 해결해서 시험 시작 !

 

 문제는 대충 이랬다. 

1. Ad Rotation 

주어진 10진수를 바탕으로 현재 모든 광고의 표시 상태를 나타내는 이진 표현을 구한 후, 가장 높은 자릿수의 1 비트 위치에서 시작하여 그 비트를 부정하고, 0에서 1 또는 1에서 0으로 변경해야 합니다. 결과로 얻어진 값을 10진수로 반환하는 문제

ex)

• 50을 입력하면 13 출력
  • 50을 2진수로 변환하면 00110010 즉, 110010
  • 110010을 부정하면 001101 이므로 1101
  • 이를 다시 10진수로 변환하면 13
• 100을 입력하면 27 출력
  • 100을 2진수로 변환 : 01100100 즉, 1100100
  • 이를 부정하면 0011011 이므로, 11011
  • 이를 다시 10진수로 변환하면 27

 

 

2. Vowel Substring 

주어진 문자열에서 모음만으로 이루어진 연속된 글자중, a, e, i, o, u가 하나씩이라도 나오는 조합의 개수를 구하는 문제

즉, 모음만으로 이루어진 연속된 글자 중에서 a, e, i, o, u가 각각 최소한 한 번씩 나타나는 부분 문자열의 수를 계산하는 문제 

각 모음의 위치를 파악하고, 모음이 포함된 구간을 찾아 가능한 모든 부분 문자열을 생성하여 그 수를 세는 방식

  ex)

• "aaeiouxa" 입력 시 출력은 2
  • aaeiou
  • aeiou
• " aeioaexaaeuiou" 입력 시 출력은 4
  • aaeuiou
  • aaeuio
  • aeuiou
  • aeuio

 

 

3. 이진트리와 노드와 리프의 관계식(선택형)

포화 이진 트리(Full Binary Tree)의 속성을 묻는 문제이다. 

이진 트리에는 각각 두 개의 자식이 있는 L개의 잎과 K개의 내부 노드가 있을 때, L과 K의 관계는 무엇인지 선택하는 문제 

L = K + 1

포화 이진 트리는 모든 내부 노드(Internal Node)가 두 개의 자식 노드를 가지고 있으며, 이때 리프 노드(Leaf Node)와 내부 노드 간의 관계식이 성립한다. 

즉, 리프 노드의 개수는 내부 노드의 개수보다 하나 더 많다. 이 관계는 이진 트리의 기본적인 성질 중 하나이다. 

 

 

4. 연결리스트 삽입(선택형)

연결리스트를 사용하여 큐를 구현, 여기에는 앞과 뒤의 포인터가 2개 있다. 큐 길이가 n인 경우 이 큐에 요소를 삽입하는 데 필요한 시간은 얼마인지 구하는 문제 

O(1)

연결 리스트 기반의 큐에서 삽입은 큐의 뒤쪽(rear)에 새로운 요소를 추가하는 작업입니다. 이때 rear 포인터를 사용하여 리스트의 끝을 가리키고 있으므로, 새 노드를 만들고 이 노드를 rear에 연결한 후, rear 포인터를 새 노드로 갱신하는 작업만 필요합니다.

이러한 작업은 리스트의 길이와는 무관하게 항상 일정한 시간에 수행

 

 

5. 연결리스트 검색의 시간 복잡도(선택형)

길이가 n인 연결리스트에서 요소를 찾는 데 걸리는 시간 복잡도를 구하는 문제 

O(n)

연결 리스트는 인덱스를 사용하여 직접 접근할 수 없고, 첫 번째 노드부터 순차적으로 탐색해야 한다. 따라서 원하는 요소를 찾기 위해서는 최악의 경우 리스트의 끝까지 탐색해야 할 수 있으므로 시간 복잡도는 리스트의 길이에 비례하게 된다. 

 

 

6. 이진 탐색 트리 탐색의 시간 복잡도(선택형)

n개의 요소를 가진 이진 검색 트리에서 요소를 찾는 데 드는 평균 시간 복잡도를 구하는 문제 

O(log₂ n)

이진 검색 트리는 요소가 균형 있게 분포된 경우, 검색 시마다 탐색 범위가 절반으로 줄어들기 때문에 평균적으로 log₂ n의 시간 복잡도를 가지게 된다. 

 

 

7. 코드의 복잡도(선택형)

int a= 1;

while (a<n){
    a = a*2;
}

위 코드의 복잡성을 구하는 문제 

O(log₂ n)

초기값 a는 1이다. while 루프는 a가 n보다 작을 동안 계속 실행된다. 루프 내부에서 a는 매 반복마다 2배씩 증가한다. 

a는 처음에 1이고, 루프가 한 번 실행될 때마다 2, 4, 8, ... , 2^k가 된다. 루프는 a가 n보다 작을 때까지 실행되므로, 마지막 반복에서 2^k ≥ n 이 되어야 한다. 이를 로그 형태로 표현하면 , k ≥ log⁡2(n) 이다. 따라서, 루프는 대략 log₂ n 번 실행된다. 

 

 

 

8. 데이터 구조의 속성(선택형)

주어진 요소를 집합에 삽입하고, 그 집합을 리스트로 변환하고 오름차순으로 정렬하는 문제

[1, 2, 3, 4, 5, 7, 9]

ex)

• 요소 : 1, 2, 9, 1, 2, 3, 1, 4, 1, 5, 7 
• 집합에 삽입 : {1, 2, 3, 4, 5, 7, 9} 
  • 집합은 중복을 허용하지 않기 때문에, 중복된 요소는 한 번만 저장
• 리스트로 변환 : [1, 2, 3, 4, 5, 7, 9]
• 정렬 : [1, 2, 3, 4, 5, 7, 9]
  • 리스트는 이미 오름차순으로 정렬되어 있으므로 정렬을 수행한 후에도 결과는 같다. 

 

 

9. 로그에서 의심스러운 활동

로그와 임계값이 주어지면 임계값보다 같거나 많은 거래가 있는 사람을 출력하는 문제

즉, 로그 데이터에서 의심스러운 활동을 탐지하는 문제

ex) 

• logs = ["1 2 50", "1 7 70", "1 3 20", "2 2 17"], 임계값 threshold=2 이 주어진다.
• 그러면 출력 값은 1, 2 이다. 
  • 이때 3개의 항목 중 0번째는 보낸 사람, 1번째는 받는 사람, 2번째는 거래 금액이다. 금액은 무시해도 된다. 
  • 0번째와 1번째 항목인 거래를 한 사람들의 ID는 1, 2, 7, 3이고 각각의 거래량은 3, 2, 1, 1 이다. 
    • 마지막 "2 2 17" 과 같은 경우 즉, 보내는 사람과 받는 사람이 일치할 경우는 그 거래의 거래량은 1이다. 
  • 이때 임계값이 2 이므로 2보다 같거나 큰 거래량은 3, 2 이다. 그리고 이 거래를 한 사람의 ID는 1, 2 이므로 1, 2 출력
• logs =["9 7 50", "22 7 20", "33 7 50", "22 7 30"], 임계값이 3 이 주어진다. 
• 그러면 출력값은 7 이다. 
  • 0번째와 1번째 항목인 거래를 한 사람들의 ID는 9, 7, 22, 33 이고, 각각의 거래량은 1, 4, 2, 1 이다. 
  • 이때 임계값이 3 이므로 3보다 큰 4번의 거래를 한 사람의 ID인 7이 출력된다. 

 

 

10. 문자열 순열 계산

주어진 규칙에 따라 문자열의 가능한 순열을 계산하는 문제

모음의 규칙과 이웃한 모음에 대한 제약을 고려하여, 유효한 순열의 수를 구하는 알고리즘을 구현해야한다. 

규칙은 다음과 같고, 주어진 길이의 문자열의 수를 구해야 한다. 

• 각 글자는 모음입니다. 즉, {a, e, i, o, u} 집합에 속합니다.
• 문자 a 뒤에는 문자 e 만 올 수 있습니다.
• e 뒤에는 a 또는 i 만 올 수 있습니다.
• i 는 다른 i 옆에 있을 수 없습니다.
• o 뒤에는 i 또는 u 만 올 수 있습니다.
• u 뒤에는 a 만 올 수 있습니다.

ex)

입력으로 1이 입력된다면 분석할 문자열의 길이 n = 1인 것이고, 이에 해당하는 출력은 5이다.

왜냐하면 길이가 1인 문자열이 5개 있으며, 각 문자열에는 모음이 하나씩 들어 있기 때문이다. (a, e, i, o, u)

5 mod(10^9 + 7 ) = 5

 

입력으로 2가 입력된다면 분석할 문자열의 길이가 2인것이고 출력 값은 10이다.

길이가 2인 문자열이 10개이기 때문이다. (io, iu, oi, ou, ua, ae, ea, ei, ia, ie)

10mod(10^9 + 7 ) =10

 

 

 

11. 규정 준수 우선순위

우선 순위를 재할당하는 문제

즉, 규정 준수와 관련된 문제로, 주어진 규정 목록에 대한 우선순위를 설정하는 문제

규정은 다음과 같다 

• 최대 우선순위 값이 최소화되는 동안 상대적인 우선순위는 유지된다. 
• 우선순위가 주어지면, 재정렬하지 않고 재할당된 우선순위 갑을 포함하는 목록을 반환한다. 

ex) 

아래와 같이 입력된다. 

4
1
3
7
3

그러면 4개의 요소가 주어진다는 것이고, 배열 요소는 [1, 3, 7, 3] 이 된다. 

그러면 출력되는 값은 다음과 같다. 

1
2
3
2

 

예시 하나를 더 든다면, 

5
2
9
3
2
3

이렇게 입력이 되면, 5개의 요소가 주어지고, 배열 요소는 [2, 9, 3, 2, 3] 이 된다. 

그러면 출력되는 값은 다음과 같다. 

1
3
2
1
2

 

 

12. 최댓값의 빈도

주어진 리스트에서 최댓값의 빈도를 구하는 문제였습니다. 리스트의 모든 요소를 탐색하여 최댓값을 찾고, 해당 값의 발생 빈도를 계산하는 알고리즘을 구현했습니다. 데이터 구조에 대한 이해가 필요했습니다.