[ASAC 4일차] 알고리즘의 시작

3월 26일의 기록

---

오늘 오전에는 과거의 카카오 기출 문제를 풀면서 시간을 보냈다. 겨우 풀긴 했는데, 조건문을 너무 길게 써서 코드가 더러워보이는 것 같다.

내눈에 그게 느껴지니, 어떻게 개선할 수 있을까라는 고민을 많이 해봐야겠다는 생각이 든다.

 

나중에 매니저님의 코드를 보았더니 key pad의 형태로 좌표값을 미리 딕셔너리로 저장하고 사용하니코드의 길이가 현저히 줄어들고 가독성이 높아지는 좋은 효과가 있어 보였다.

 

0. 목차

---

1. 카카오 인턴십 문제 풀이(거리 및 좌표 계산 관련)
2. 리스트 리뷰
3. 정렬
   1. 선택 정렬
   2. 삽입 정렬
4. 정렬 연습문제

 

1. 카카오 인턴십 문제 풀이

---

 

참고) 카카오 2020년 인턴십 문제

프로그래머스

 

1-1. 문제 해석

---

• 엄지 손가락만을 사용해서 버튼을 클릭
• 특수문자는 누르지 않으며, 숫자만 누른다.
• 초기 위치
  • 왼손 : *
  • 오른손 : #
• 누르는 경우
  • 1, 4, 7을 누를 땐 ⇒ 왼손 고정
  • 3, 6, 9을 누를 땐 ⇒ 오른손 고정
  • 2, 5, 8, 0을 누를 땐 거리가 가까운 손으로
    • 여기서 만약 거리가 같은 경우 ‘왼손 잡이’는 왼손, ‘오른손 잡이’는 오른손
• 이동 방식
  • 상하좌우, 1번에 1칸씩

1-2. 내 풀이 코드

---

def distance(a, b):
    return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**(1/2)
    # 두 점간의 거리를 구하기 위해 유클리드 거리 계산을 이용

def solution(numbers, hand):
    answer = ""
    #hand가 right, left로 들어와서 이를 L,R로 변경
    
    if hand == "right": 
        hand = "R"
    elif hand == "left":
        hand = "L"
        
    #왼손과 오른손의 초기 위치 설정
    left_hand = [1,1]
    right_hand = [3,1]

# answer 문자열에 이동 계획에 따라 L,R 문자 삽입
# +  각 숫자 케이스 별로 왼손, 오른손의 위치 갱신
    for i in numbers:
        if i == 1:
            left_hand[0], left_hand[1] = 1,4
            answer+="L"
        elif i == 4:
            left_hand[0], left_hand[1] = 1,3
            answer+="L"
        elif i == 7:
            left_hand[0], left_hand[1] = 1,2
            answer+="L"

        elif i == 3:
            right_hand[0], right_hand[1] = 3,4
            answer+="R"
        elif i == 6:
            right_hand[0], right_hand[1] = 3,3
            answer+="R"
        elif i == 9:
            right_hand[0], right_hand[1] = 3,2
            answer+="R"
## 만약, i가 2,5,8,0 인 경우에 어떤 상황에서 거리가 더 가까운지 
## 조건을 따져서 왼손이 가까우면 왼손, 오른손이 가까우면 오른손이며
## 거리가 동일할 떄는 hand에 저장된 손잡이 정보에 따라 결정

        elif i == 2:
            if distance(left_hand,[2,4]) < distance(right_hand, [2,4]):
                left_hand[0], left_hand[1] = 2,4
                answer+="L"
            elif distance(left_hand,[2,4]) > distance(right_hand, [2,4]):
                right_hand[0], right_hand[1] = 2,4
                answer+="R"
            else:
                if hand == "R":
                    right_hand[0], right_hand[1] = 2,4
                    answer+= hand
                elif hand == "L":
                    left_hand[0], left_hand[1] = 2,4
                    answer+= hand
                

        elif i == 5:
            if distance(left_hand, [2,3]) < distance(right_hand, [2,3]):
                left_hand[0], left_hand[1] = 2,3
                answer+="L"               
            elif distance(left_hand, [2,3]) > distance(right_hand, [2,3]):
                right_hand[0], right_hand[1] = 2,3
                answer+="R"
            else:
                if hand == "R":
                    right_hand[0], right_hand[1] = 2,3
                elif hand == "L":
                    left_hand[0], left_hand[1] = 2,3
                answer+= hand
        
        elif i == 8: 
            if distance(left_hand, [2,2]) < distance(right_hand, [2,2]):
                left_hand[0], left_hand[1] = 2,2
                answer+="L"      
            elif distance(left_hand, [2,2]) > distance(right_hand, [2,2]):
                right_hand[0], right_hand[1] = 2,2
                answer+="R"      
            else:
                if hand == "R":
                    right_hand[0], right_hand[1] = 2,2
                    answer+= hand
                elif hand == "L":
                    left_hand[0], left_hand[1] = 2,2
                    answer+= hand
                
        elif i == 0:
            if distance(left_hand, [2,1]) < distance(right_hand, [2,1]):
                left_hand[0], left_hand[1] = 2,1
                answer+="L"
            elif distance(left_hand, [2,1]) > distance(right_hand, [2,1]):
                right_hand[0], right_hand[1] = 2,1
                answer+="R"    
            else:
                if hand == "R":
                    right_hand[0], right_hand[1] = 2,1
                    answer+= hand
                elif hand == "L":
                    left_hand[0], left_hand[1] = 2,1
                    answer+= hand
    return answer

test_numbers = [1,3,4,5,8,2,1,4,5,9,5]
test_numbers_2 = [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]
test_hand = "right"
test_hand_2 = "left"

print(solution(test_numbers, test_hand))

## 풀긴했는데, if문을 계속 중첩해서 사용해서 불편함...
## 샘플 케이스에서는 통과했는데, 어딘가에서 틀려있었음.

 

1-3. 에러 처리

---

 

1. 샘플 케이스에서는 문제없이 작동, 그러나 프로그래머스에 제출하였을 때는 틀렸다...
   • 여러가지 방법을 확인해본 결과 내가 거리를 구하는 공식이 유클리드 거리 계산 방식으로 써서 생긴 문제였다.
   • 유클리드 거리는 두 점사이의 직선 vs 맨해튼 거리는 두 점의 좌표평면 상의 가로 세로의 합
   • 이 두 공식의 차이로 인해 실제 테스트 케이스에 섞여있는 상황에서 가까움을 인지하는 것에 차이가 나면서 생기는 문제였다.

맨하탄과 유클리드 거리의 차이

해결 코드

공식을 다시 맨해튼 거리 공식으로 변환하여 계산하여 문제를 해결하였다

 

1-4. 참고) 다른 해결 코드

---

• 내가 해결했던 방법에는 if 를 모든 케이스에서 나눠서 진행하다보니 코드가 길고 각 경우를 체크하기 복잡했다.
• 수업 시간에 매니저님이 보여준 코드에서는 각 키패드의 좌표 값을 딕셔너리 형태로 저장하여 이를 활용하였는데, 이를 통해 효과적으로 코드 길이를 줄이고 가독성이 높아졌다.

 

▶ 전체 코드는 아래에서 확인할 수 있다.

# 입력 : 2개 키패드( 눌러야할 키패드 번호, 현재 손 위치)
# 출력 : 2개의 절대값 직선 거리
# --> 1-2, 2-1 : 양수로 계산을 해야 함!!!!! 구글링 |1-2| , |2-1|
#     검색해서 abs()함수를 찾아서 하거나,,
#     검색못하거나, 불가능한 상황 : 빼는 숫자가 크면 - 부호처리 예외 처리 구현!!!
# ==> 모른다고, 까먹었다고 못푸는게 아니라..
#     없거나 모르면 그냥 구현하면 됨!!단 , 귀찮을 뿐;;;;;

def get_distance(number, pos):
    # number, pos변수는 오로지 인 get_distance 함수 내에서만 존재!!!!
    key_pad = {"1" :[0,0], "2":[0,1], "3":[0,2],"4" :[1,0], "5":[1,1], "6":[1,2],"7" :[2,0], "8":[2,1], "9":[2,2],"*" :[3,0], "0":[3,1], "#":[3,2]}
    # 명시적으로 눌러야 할 버튼/위치 버튼 : 키값--> 문자(설계에 따라서 생략가능)
    number = str(number)
    pos = str(pos)
    # 1) 눌러야 할 버튼의 좌표값!!!!!! : 파이썬의 멀티할당!!!
    x_number, y_number = key_pad[number] # key_pad["#"] ==> [3,2]
    # x_number = key_pad[number][0]
    # y_number = key_pad[number][1]

    # 2) 손의 위치에 대한 좌표값!!!!!
    x_pos, y_pos = key_pad[pos]

    # 3) 1하고 2의 절대값 거리계산!!!! ==> 각 좌표의 차이의 절대값 : abs
    abs_distance = abs(x_number-x_pos) + abs(y_number-y_pos)

    # 최종 출력
    return abs_distance

## ---> 큰 틀 : 입력으로 받은 numbers를 돌려가면서,: for
# case1) 1,4,7 : 왼손
# case2) 3,6,9, : 오른손
# case3) 2,5,8,0 ==> 왼손과 거리, 오른손과 거리 :get_distance()
#                    D_L = get_distance()
#                    D_R = get_distance()
#        case3-1) D_L != D_R : 가까운손!!!! --> 부등식!!!
#        case3-2) D_L == D_R : hands의 정보 처리!!


# --> 위에서 이미 거리 구하는 함수 정의를 했다고 가정하고,,,,

def solution(numbers, hand):
    answer = ''
    ###########
    # 1-1) 필요한 변수 세팅!!!!! ---> 왼손, 오른손 위치 세팅!!!!
    left_pos = "*"
    right_pos = "#"
    # 1-2) 필요한 변수 세팅 ---> 무슨손 잡이 --> 간략 출력용으로 변경!!!!!
    # right --> R, left --> L로 변경!!!!
    if hand == "right":
        hand = "R"
    elif hand =="left":
        hand = "L"
    ############

    #2) 본격적인 눌러야할 버튼들 롤링!!!! ==> for
    for num in numbers:
        # 2-1) 무조건 왼손 : 1,4,7
        if num in [1,4,7]: # num==1 or num==4 or num==7
            #answer = answer + "L"
            answer += "L"
            # 왼손의 위치도 변경!!!!!!
            left_pos = num
        # 2-2) 무조건 오른손 : 3,6,9
        elif num in [3,6,9]: # num==3 or num==6 or num==9
            anwser += "R"
            # 오른손의 위치 변경!!!
            right_pos = num
        # 2-3) 선택 : 2,5,8,0
        elif num in [2,5,8,0]:
            dis_left = get_distance(num, left_pos)
            dis_right = get_distance(num, right_pos)
            # 2-3-1) 거리가 다를 때
#            if dis_left != dis_right:
            # 2-3-2) 거리가 같을 때

            #2-3-11) 거리가 왼쪽 짧음
            if dis_left > dis_right:
              answer += "L"
              left_pos = num
            #2-3-12) 거리가 오른쪽 짧음
            elif dis_left < dis_right:
              answer += "R"
              right_pos = num
            #2-3-13) 거리 같음
            elif dis_left == dis_right:
              answer += hand
              # -- 무슨 손 잡이냐에 따라 어느 손 갱신할지 선택해야함.
              if hand == "R":
                right_pos == num
              elif hand == "L":
                left_pos == num


    ###########
    return answer

 

 

2. 리스트 자료형의 리뷰

문제)  a = ["A","B","A","O","AB","AB","O","A","B","AB"]
이러한 혈액 형 데이터를 가지고 있을 때, 각 혈액형별로 몇 명인지 총 인원을 구하라.

 

방법 1) 그냥 리스트 돌리면서 작성하기

if 조건문을 사용해보기, Dict을 활용해서 돌려보기

방법 2) 리스트 컴프리핸션 사용

리스트 컴프리핸션으로 사용해보기

 

3. 정렬

---

기본 내용

• 정렬: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미
• 정렬 알고리즘은 매우 다양하다
• 어떠한 것들이 기준이 될까? : (포지션, 값의 크기, 알파벳, 성적순 ...etc)
• 어떤 방법이 있을까?
• 파이썬을 가지고 기본적으로 정렬할 때는  2가지 방법이 있다.
  1. sort() 메서드 : 원본이 변경된다.
  2. sorted() 함수는 원본이 유지가 된다.
  • 이 둘의 사용법은 동일하다

구현 시 꼭 알아야 하는 swap

• 참고) swap → 아래와 같이 하면, 중간에 temp라는 변수를 사용하지 않고 할 수 있음.

#### 일반적으로 swap를 하기위해서는 
### 아래와 같은 temp를 사용해서 처리를 해야한다.

arr = [3,10]
print(arr)
print("--------")
temp = arr[0]
arr[0] = arr[1]
arr[1] = temp
print(arr)

# temp 없이 바로 바꾸기 위해서는 아래와 같은 형식을 사용을 함!!!!!
arr = [3, 10]
print(arr)
print("------")
arr[0], arr[1] = arr[1], arr[0]
print(arr)

1. 선택정렬

---

• 기초 아이디어: 정렬되지 않은 그룹에서 하나씩 들어다가 다른 곳으로 옮기는 과정에서 순서에 맞게 중간중간 삽입을 하는 방법!
• key: 기준에 맞는 것으로 해서 차례대로 제일 부합하는 것을 찾아 → 차례대로 하나씩 하게 되면 자연히 정리가 된다.

일단 주어진 것에서 제일 작은것 or 제일 큰 값을 먼저 찾기!!!

→ 그 값을 맨 앞의 값과 교환해서 가서 제일 작은 것 배치 완료(제일 큰것, 맨 오른쪽) → 남은 것들을 대상으로 다시 제일 작은 or 제일 큰 것을 찾아서 반복 수행!!!

기본 과정 : 작은 순서대로 진행

시간복잡도

• N개의 원소가 있을 때, 우리는 N-1번 만큼의 가장 작은 수들을 계속 찾아서 앞으로 보내야 한다.
  • 즉, (N개 원소 중 작은거) + (N-1개 원소 중에서 작은거) + ... + (2개 원소 중에서 작은거) ⇒ N + (N-1) +.. + 2 = (N ) (N+1)/ 2정도의 연산을 수행을 하게 된다.
• 선택정렬은 기본적인 N^2의 시간 복잡도를 가진다.
• 선택정렬은 간단히 주어진 것들에 대해서 정리하는건 용이하지만,
  시간의 복잡도는 제곱으로 늘어나므로 원소의 수가 늘어날 때 시간이 기하 급수적으로 증가한다.

 

2. 삽입정렬

---

• 기본 개념 : 1개를 꺼내어서 적당한 위치에 집어 넣는다는 것이 기본 개념!

기본 과정

아래의 그림과 같은 배열에 대해 정렬

• step1: 가장 앞에 있는 9는 일단 정리가 되었다라고 판단 → 2번째 있는 5를 가지고와서 일단 정리가 된 9를 기준으로 앞? 뒤? 인지 판단을 해서 위치를 결정해준다.
  • 새로운 5가 9보다 더 작으므로 둘의 위치를 스왑한다.
  • 현재 = [5, 9, 1, 4, 3]

• step 2: 3번째에 있는 1로 → 이미 정리된 5,9에서 비교를 한다. → 우선 바로 앞에 있었던 9와 비교해보니 9가 더 크므로 3번째 자리에 9를 넣어서 자리를 바꾸고 그 앞의 5에 대해서 비교하면 5보다 작으니 2번째 자리에는 5를 주고 맨 앞에 1을 끼워넣는다.
  • 현재 : [ 1, 5, 9, 4, 3]
• step 3: 3개가 이미 정리되었으니 4를 가져와서 앞의 9와 비교하고 4가 더 작으니 4자리에 9, 5비교하고 5가 더 크니 5와 바꾸고, 다시 그 앞의 1과 배교해보니 1보다 4가 크니 그 위치에 그대로 둔다.
  • 현재 : [1, 4, 5, 9, 3]
• step 4: 다음 3을 가져와서 동일하게 반복
  • 현재 [1, 3, 4, 5, 9]

구현

---

특이사항

• 시작할 때 앞에서 0번째 원소는 이미 정리되었다 가정하므로, 1번째(실은 2번째) 원소를 가져와서 비교한다.
  • for문에서 맨 앞이 아닌 2번째에서 부터 돌려야한다는 뜻!
  • ex) for in range(0, len(arr))이 아니라 for i in range(1, len(arr))로 변경한다
• 비교를 할 때 바로 앞부터 하나씩 앞으로 가면서 비교한다.

시간 복잡도

• 2중 포문을 사용하면서 O(N^2) 이다 → 선택 정렬과 마찬가지로 속도에서의 문제점은 원소의 수가 늘어날 때 시간의 소비가 제곱으로 늘어난다.
• 1+2+3+….+(N-1)의 연산으로 앞의 선택정렬과 동일하다.

4. 연습문제) 2019 kakao blind recruitment 실패율 문제

---

참고) 2019 kakao blind recruitment 실패율 문제

프로그래머스

 

풀이 방법

 

처음 코드를 작성하고 문제를 제출해보았을 때 테스트케이스에서 중간에 문제가 생겼었다.

문제 분석

하나씩 살펴보다 보니 매 스테이지마다 도전자가 0명일 수 있었다. 예를 들어 3단계에서 모든 유저가 통과하지 못했을때 4단계에는 도전자가 0명인 상황이다.

이때, temp_dic[i] = stages.count(i)/(len(stages)-temp)  이 부분에서 len(stages)-temp(도전자가 0명인 상황) 이므로이 값이 0이 될 때, 나눗셈이 불가능해지면서 생기는 이슈였다.

해결 코드

매번 스테이지에 도전하는 사람이 없을 때는 그냥 0으로 값을 고정하였다.

최종 코드

def solution(N, stages):
    temp_dic = {}
    temp = 0

    for i in range(1,N+1,1):
        if (len(stages)-temp)> 0: 
            temp_dic[i] = stages.count(i)/(len(stages)-temp)
            temp += stages.count(i)
        else:
            temp_dic[i] = 0
            temp += stages.count(i)

    fail_list = sorted(temp_dic.items(), key = lambda x: (-x[1], x[0]))

    answer = [i[0] for i in fail_list]

    return answer