TIL | 11.10.목 [Algorithm]

- Algorithm

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

 

 

- 문제 관련 개념

 

[숫자 문자열과 영단어 - 2021 카카오 채용연계형 인턴십]

• 이 문제는 ‘in’과 ‘.replace( , )’ 사용

 

---

 

 

[체육복 - 탐욕법(Greedy)]

→ Greedy 문제풀이 : 단순무식 + 때론 효율적

• 중요 조건
  • “바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.” + “ 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.”
• list vs set 차이점 : 중복허용여부
  • list : 중복 O
  • set : 중복 X (set(a)-set(b) : a에만 속해 있는 원소를 구하고 싶을때 쓰는 ‘set -’)
• 단계별 풀이
  • 1단계 - 일단 진짜 빌려줄 수 있는 아이를 구해야됨
  • 2단계 - 진짜 도난 당한 사람을 남겨
  • 3단계 - 진짜 빌려줄 수 있는 애 중에 -1인 아이 제거
  • 4단계 - 체육복을 구한 애 +1인 아이 제거
  • 5단계 - (전체 학생 수 - 제거 된 남은 아이들의 수) == 답
• ↓ greedy 관련 문제 풀어보기 ↓

            문제 - 1 페이지

 

 

 

 

---

 

[비밀지도 - 2018 KAKAO BLIND RECRUITMENT]

• 코딩테스트 문제에서 가장 중요한 힌트는 "그림"이다
• 필요개념
  • 비트연산 
  • binary : 2진수 변환 코드 =  bin()[2:0] (앞에 붙는 2진수라는 표기인 0b를 지워주기 위해 슬라이싱 사용해서 잘라준다.)
  • or , format(숫자, 'b') 쓰면 슬라이싱 안 해줘도 됨
  • 자릿수를 채워주는 코드 ‘.zfill(몇자릿수로 채울지)’

 

 

---

 

 

 

[약수의개수와덧셈-월간코드챌린지시즌2]

• for 문의 range 활용 + range(에서 범위 설정 잘 해주기)
• 약수 갯수 구하기

for n in range(1, i+1):
	if i % n == 0: 
    	count += 1

 

 

---

 

 

[없는숫자더하기-월간코드챌린지시즌3]

• not in 구문 사용

 

---

 

 

 

[완주하지 못한 선수 – 해시]

→ 정확성과 효율성을 모두 만족해야 됨

• 동명이인이 있을 수 있다! 라는 조건이 함정!!
• 외부 모듈을 이용해서 풀 수 있음 : collections.Counter → ‘import collections’ 필요!
• ↓ 해시관련 문제 풀어보기 ↓

          문제 - 1 페이지

 

 

 

 

---

 

 

 

- 추가 개념

 

[.keys() / .sort() / .sorted() 등의 method 많이 사용됨]

• .keys() : 키와 값의 쌍으로 이루어진 데이터 타입인 딕셔너리에서 키(key)만 뽑아 내고 싶을 때 '.keys()' 라는 함수를 사용해서 키만 뽑아 낼 수 있다. 

>>> a = {'name': 'pey', 'phone': '0119993323', 'birth': '1118'}
>>> a.keys()
dict_keys(['name', 'phone', 'birth'])

 

• .sort() vs .sorted()

some_list = [5, 7, 2, 3, 1]

print(sorted(some_list))
>>>>> [1, 2, 3, 5, 7]

print(some_list.sort())
>>>>> None

 

some_list = [5, 7, 2, 3, 1]

sorted(some_list)
print(some_list)
[5, 7, 2, 3, 1]

# sorted는 원래 존재하던 some_list에 아무 영향을 끼치지 않는다.

 

some_list = [5, 7, 2, 3, 1]

some_list.sort()
print(some_list)
[1, 2, 3, 5, 7]

# 반면에 sort 메소드는 some_list 자체를 정렬해버린다.

 

---

[for]

• 한 함수에 for 문은 3개이상 지양
• + for 속, 비교문구가 있다면 for문 2개이상 금지

 

---

 

 

[in / not in]

해당 Key가 딕셔너리 안에 있는지 조사하기(in)

>>> a = {'name':'pey', 'phone':'0119993323', 'birth': '1118'}
>>> 'name' in a
True
>>> 'email' in a
False

'name' 문자열은 a 딕셔너리의 Key 중 하나이다. 따라서 'name' in a를 호출하면 참(True)을 돌려준다. 반대로 'email'은 a 딕셔너리 안에 존재하지 않는 Key이므로 거짓(False)을 돌려준다.

 

 👉 위와 같은식으로 in과 not in은 그 자체로써 활용할 수 있다.

 

 

---

 

 

- 참고자료

 

https://wikidocs.net/16#key-valueget

02-5 딕셔너리 자료형