TIL | 11.17.목 [Algorithm]

- Algorithm

Programmers 코딩테스트 문제 기반 : 기초 개념

 

 

- 문제 관련 개념

 

[두정수사이의합]

• 정수 사이? → a와 b 대소 비교 필수!

---

 

[정수 내림차순으로 배치하기]

→ 정수? 문자? 등 나오면 반환하는 자료형이 뭔지 중간중간 확인해주기

 

• #1. str → for문 돌리기 👉 문자열은 for문을 통해 문자열 하나하나 불러올 수 있다.
• s = 'hello' for a in s: print(a) ''' h e l l o '''

 

• #2. join() 함수
  • 리스트(배열)의 각 요소들을 하나로 합치는 것은 join() 함수로 할 수 있습니다. 그냥 하나로 합칠 수도 있고, 각 엘레멘트 사이에 구분자를 넣어서 합칠 수도 있습니다.
  • 그냥 하나로 합치기 s = "".join(food) → 출력 결과: food속 원소들이 띄어쓰기 없이 합쳐짐
  • 요소들 사이에 구분자 넣기 s = ", ".join(food) → 출력 결과: food속 원소들이 ,로 구분되면서 합쳐짐
•  

---

 

 

[나머지가1이되는수찾기-월간코드챌린지시즌3]

• break → 조건 만족시 블록문을 빠져나갈 수 있는 코드

 

 

---

 

[예산 - Summer/Winter Coding(~2018)]

• greedy 방식과 유사 : ex)거스름돈

 

---

 

[K번째수 - 정렬]

• 2차원 배열 / 여러개의 배열
  • index를 주석으로 표기하기!
  • ~번째 수 != index
• slicing → [index시작 : index-1끝남]

 - 1번 풀이

# 인덱스 풀이 

def solution (array, commands) :
	answer = []
	for i, j, k in commands:
        ar = []
        ar = array[1-i:j] # 인덱스 주의
        ar.sort ()
        answer.append(ar[k-1]) # 인덱스 주의
	return answer

 

 - 2번 풀이

# 번째수 풀이

def solution(array, commands) :
    answer = []

    for i in range (len(commands)) :
        new_array = array[commands[i][0]-1:commands[i][1]]
        new_array.sort()

        answer.append(new_array[commands[i][2]-1])

    return answer

 

 

• ↓ 정렬 유사문제 풀어보기 ↓

문제

 

---

 

[실패율 - 2019 KAKAO BLIND RECRUITMENT]

• 문제가 길땐 변수의 역할 정의 + 변수를 이용해 내가 구할 수 있는 것들을 파악하기

 

 - 단계별 풀이

1. N= 전체 스테이지의 개수
2. stages= 게임을 이용하는 사용자가 멈춰 있는 스테이지 번호 배열 
   • ↓ stages를 통해 내가 추가로 얻을 수 있는 정보들 ↓
   • •len(stages)= 전체 사용자 수
     • 해당 스테이지를 클리어한 사람
     • 해당 스테이지에서 막힌 사람
3. 전부 stages에서 도출할 수 있다.
4. 구해야 하는 것=실패율이 높은 스테이지 번호부터 내림차순 배열

 

 - 1번 풀이 : stages를 index로 정의해 풀어준다

def solution (N, stages):
    answer = []
    total = len (stages)
    stage_ppl = []
    
    for i in range(1, N+1):
    	num = stages. count (i)
    	if num == 0:
    		stage_ppl.append (0)
    	else:
    		stage_ppl.append(num/total)
    		total -= stages.count (i)
            
    for i in range (N):
    	pop_idx = stage_ppl.index (max (stage_ppl))
    	answer. append (pop_idx + 1)
    	stage_ppl[pop_idx] = -1
        
    return answer

 

 - 2번 풀이 : 딕셔너리를 이용해 풀어준다

def solution(N, stages):
    fail = {}   # 아래의 fail[key] = value 로 저장되고 있음
    all_user = len(stages) # 전체 이용자 수

    # 스테이지 레벨 만큼 반복 : i는 stage 레벨을 말함
    for i in range(1, N+1):
        this_user = stages.count(i) # 해당 스테이지 user수

        if this_user == 0:  # 해당 스테이지 user가 없으면 실패율 = 0 
            fail[i] = 0
        else:
            fail[i]= this_user / all_user  # 해당 스테이지의 실패율
            all_user -= this_user   # user가 없으면 전체 사용자에서 빼줄 필요 없으므로 else 이후 부분에서만 this_user수를 빼줌

    # 딕셔너리 정렬 : value 기준으로 정렬할 때 key 값만 얻는 목적
    s_fail= sorted(fail, key=fail.get, reverse=True)    # 이부분은 https://gomgomkim.tistory.com/26  참고함!

    return s_fail

 

 

---

 

 

[소수 만들기 - Summer/Winter Coding(~2018)]

• 문제의 point는 → 리스트 쏙 원소를 3개씩 조합을 해야하고, 소수인지 아닌지 판별해야한다.
• 조합
  • from itertools import product
    • 두개 이상의 리스트에서 모든 조합을 계산해야 한다면, product를 사용

  # import 필수!!from itertools import product
  
  items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]
  random_items = list(product(*items))
  
  # [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]
  

  • from itertools import permutations or combinations
    • 하나의 리스트에서 모든 조합을 계산을 해야 한다면, permutations, combinations을 사용

  from itertools import combinations
  
  nums = [1, 5, 8, 9, 6]
  random_nums = list(combinations(nums, 3))# nums에서 3개씩 뽑아 새로운 조합을 만들어# [(1, 5, 8), (1, 5, 9), (1, 5, 6), (1, 8, 9), (1, 8, 6), (1, 9, 6), (5, 8, 9), (5, 8, 6), (5, 9, 6), (8, 9, 6)]
  

  👉 코딩 테스트 사기템 : itertools

---

 

• 소수
  • 소수란? 1과 자기자신만을 약수로 가지는 자연수 N
    
    • + 추가로, 소수는 1부터 100까지의 수 가운데 총 25개 이다
    • 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
  • python에서의 소수 활용
    
    • 자연수 N이 소수인지 아닌지 비교할때
      • 한 번 소수의 특징을 다시 생각해보자. 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다. 👉 이를 이용해서 i * i ≤ n 일 때까지만 비교하면 된다.
    • 어떤 값이 소수인지 여부를 판단하는 간단한 함수

 

 

# 1def is_prime_number(num):
    if num==0 or num==1:
        return False
    else:
        for n in range(2, (num//2)+1):
            if num % n == 0:
                return False
        return True

# 2def is_prime_number(num):
    if num==0 or num==1:
        return False
    else:
        for n in range(2, num-1):
            if num % n == 0:
                return False
        return True

•