일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 10430번
- Fatal Python error: init_fs_encoding: failed to get the Python codec of the filesystem encoding
- 파이썬 클래스
- 99클럽 #99일지 #코딩테스트 #개발자스터디 #항해 #til
- 개발자스터디
- not a git repository
- 파이썬
- 코딩테스트
- 파이썬 sep
- print sep
- 주니어개발자멘토링
- EnvCommandError
- 백준
- 99일지
- 파이썬 map 함수
- MomentumParameters
- 항해플러스
- 항해
- Til
- print("""
- cp949
- 항해99
- 코딩부트캠프후기
- 99클럽
- 파이썬 int()
- vscode cp949
- fatal:not a git repository
- 파이썬 |
- 개발자사이드프로젝트
- 주니어개발자역량강화
- Today
- Total
선발대
[스파르타] 자료구조, 알고리즘 1주차 (완강) 본문
1. 수업 후기
- 강의 개수: 11개
- 총 강의시간: 1시간 23분
- 수업 목표:
- 1. 개발자들에게 알고리즘 공부가 필요한 이유를 이해한다.
- 2. 알고리즘을 학습하기 위한 기본 코드 구현력을 높인다.
- 3. 시간 복잡도, 공간 복잡도에 대해 배운다.
프로그래밍 공부를 시작하기 전부터 알고리즘, 코딩 테스트 이런 이야기들을 듣다가 처음으로 수업을 들었는데, 결론은 어려웠다. 1주차 강의 개념을 이해하고 아 이런 거구나~ 하고 이제 문제를 풀어보려면 시작을 어떻게 해야 할지 감도 안 잡혔다. 강의는 짧은 호흡으로 초보자를 위해 간단하게 진행되지만, 내가 기초 지식이 너무 없어서 그런지 도중에 강의를 멈추고 꽤 오랫동안 생각한 다음에 넘기게 된다. 수학 문제처럼 답이 나올 때까지 붙잡고 있어야 하는 건지, 아니면 넘어가서 정답을 보고 풀이를 이해해야 하는지 공부방법도 잘 모르겠다.
풀이할 때 어떻게 접근해야 될까? 특히 알고리즘 문제를 풀 때 나는 너무 복잡하고 길게 쓰게 되는데 막상 정답을 보면 엄청 간단해서 공부를 많이 해야겠다고 생각했다. 심지어 풀이를 봐도 한참 붙잡고 있어야 이해하는 경우도 있었다. 강의시간은 1시간 반 정도이지만, 내용 정리하고, 복습, 직접 실습해보고 하는 시간 다 합쳐보니 총 수강시간은 거의 7시간정도 걸린 것 같다. 이렇게 또 하루가 갔다. 앞으로 알고리즘 수업은 이전 수업을 토대로 진행된다고 하는데 조금 걱정된다. 일단 이해는 어떻게 한 것 같은데, 손가락 사이로 흩어지는 모래처럼 지금 내 지식들도 빠르게 흩날리는 중이다.
그래도 한참 들여다보다가 궁금해하던 걸 해소하고 나면 뭔가 후련해진다. 혼자서 아무리 생각해도 이해를 못 해서 결국에는 해설이 잘못됐나?라는 생각도 했던 문제가 있었는데, 팀원들한테 물어보니 빠른 시간 내에 친절하게 해결해줬다. 아직 내가 제일 왕초보라서 어리바리한 것 같다. 어쨌든 어찌어찌 왕초보로서 1주차 강의는 완강했으니, 어서 기초 강의들을 끝내고 다양한 문제들을 접해봐야겠다. 일지가 아니라 푸념 글이 된 것 같은데 여전히 아직도 공부할 건 많다. 아자 파이팅~
2. 수업내용 정리
0-1. 수강환경 튜토리얼
02. Python 설치
03. PyCharm Community 설치
04. Slack 설치
- Window OS 필수사양 확인: 컴퓨터 설정 > 시스템 > 정보
- 권장사양(최소사양):
- 1. Window 버전: 10 (7)
- 2. RAM: 4G 이상
- 3. CPU: i5 이상 (i3)
- 4. 64bit 필수
0-2. 슬랙 & 즉문즉답 튜토리얼
0-3. 개발일지 튜토리얼
- 개발일지: 이번주에 내가 배운 것을 글로 기록하는 것
- 개발일지의 장점:
- 1. 배운 것들을 다시 정리하여 복습할 수 있음
- 2. 나의 생생한 감정과 고민들을 남길 수 있음
- 3. 포트폴리오로써 자기 PR로 활용할 수 있음
- 개발일지 플랫폼: 티스토리, 미디엄, 벨로그 등
1-1. 오늘 배울 것
01. 알고리즘이란
- 알고리즘: 어떤 문제가 있을 때, 그것을 해결하기 위한 여러 동작들의 모임
02. 알고리즘을 공부해야 하는 이유
- 좋은 개발자는 좋은 프로그램은 만듦.
- 좋은 프로그램: 적은 공간을 이용해서 빠른 속도로 수행되는 프로그램. '효율'
- 막연히 개발만 하면 좋은 코드 만들지 못함. 자료구조와 알고리즘에 대한 공부가 필요함.
- 좋은 회사에 취업하려면 코딩테스트를 해결해야 함. 기초 지식과 적절한 사고방식을 가져야 함.
- (실제 현업에는 이미 잘 만들어진 알고리즘이 있기 때문에, 그걸로 사용하면 됨)
03. 1~5주 차에 배우는 것들!
- 1주차: 시간/공간 복잡도, 알고리즘 구현력 기르기
- 2주차: 어레이, 링크드 리스트, 이분탐색, 재귀
- 3주차: 정렬, 스택, 큐, 해쉬
- 4주차: 힙, BFS, DFS, Dynamic Programming
- 5주차: 종합 알고리즘 문제 풀이
1-2. 필수 프로그램 설치 안내
01. Python 다운로드
02. PyCharm Community 다운로드
1-3. 파이참으로 코딩하기
01. 새 프로젝트 만들기
- 가상환경(virtual environment): 프로젝트별로 패키지들을 담을 공구함
02. 디렉토리 관리하기
- 개발자처럼 파일 관리하는 방법:
- 1. 어떤 역할을 하는 폴더와 파일인지 한눈에 파악할 수 있게.
- 2. 다른 사람들과 협업할 때는 정한 규칙대로 관리.
- 폴더 / 파일이 어떤 내용인지 파악할 수 있게 적기:
- 1. 이름짓기(naming) 매우 중요함.
- 2. 파일, 폴더 이름은 영어로.
- 3. 특수문자는 _ 만 사용하기. (띄어쓰기도 자제)
03. 파이썬 파일 만들고 실행하기
1-4. 알고리즘과 친해지기 (1)
01. [실습] 최댓값 찾기
# 중복 반복문 사용
# python의 for ~ else문은 for문에서 break가 발생하지 않았을 때의 동작을 else문에 제시
def find_max_num(array):
for num in array:
for compare_num in array:
if num < compare_num:
break
else
return num
# 가장 큰 수 저장한 변수와 비교
def find_max_num(array):
max_num = array[0]
for num in array:
if max_num < num:
max_num = num
return max_num
1-5. 알고리즘과 친해지기 (2)
01. [실습] 최빈값 찾기
- str.isalpha(): 해당 문자열이 알파벳인지 확인 가능. 파이썬 내장함수. str에 문자열 들어감.
- ex) print("a".isalpha()) # True
- ord(): 실제 문자를 아스키 코드 번호로 변환. ord('a') # 97
- chr(): 아스키 코드 번호를 실제 문자로 변환. ex) chr(97) # 'a'
# 알파벳 빈도수 세기
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26 # 길이가 26인 초기화 리스트
for char in string:
if not char.isalpha(): # 알파벳이 아니라면
continue # 반복문에서 다음 인덱스로 넘어감
arr_index = ord(char) - ord('a')
# a의 아스키코드를 기준으로 1씩 커지니까, 인덱스 알기 위해 뺄셈
alphabet_occurrence_array[arr_index] += 1
# 해당하는 알파벳에 1씩 더해주기
return alphabet_occurrence_array
print("정답 = [3, 1, 0, 0, 2, 0, 0, 0, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Hello my name is sparta"))
print("정답 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Sparta coding club"))
print("정답 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("best of best sparta"))
# 가장 빈도수가 높은 알파벳 출력하기
# 첫 번째 방법
def find_max_occurred_alphabet(string):
# 알파벳 전부 입력한 배열을 기준으로 주어진 입력과 비교함.
alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
"t", "u", "v", "x", "y", "z"]
max_occurrence = 0
max_alphabet = alphabet_array[0]
for alphabet in alphabet_array:
occurrence = 0
for char in string:
if char == alphabet:
occurrence += 1 # 알파벳 1개로 빈도수 측정
if occurrence > max_occurrence: # 최대 빈도수보다 큰 알파벳이 나오면 교체
max_alphabet = alphabet
max_occurrence = occurrence
return max_alphabet
result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
# 두 번째 방법
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a')
alphabet_occurrence_array[arr_index] += 1 # 여기까지는 초반과 동일
max_occurrence = 0
max_alphabet_index = 0
for index in range(len(alphabet_occurrence_array)): # 0 ~ 25까지 나옴. 인덱스 길이로 사용.
alphabet_occurrence = alphabet_occurrence_array[index] # 위의 알파벳별 빈도수 옮기기
if alphabet_occurrence > max_occurrence: # 최대보다 크면 교체
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a')) # 아스키코드에서 다시 알파벳으로
result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
1-6. 시간 복잡도 판단하기
01. 시간 복잡도란?
- 시간 복잡도: 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계
- ex) 입력값이 2배로 늘어났을 때 문제해결시간은 몇 배로 늘어나는지
- 좋은 알고리즘: 입력값이 늘어나도 문제해결시간은 덜 늘어나는 알고리즘
02. 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기
## 첫 번째 방법
def find_max_num(array):
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return max_num
- 각 줄이 실행되는 것을 1번의 연산이 된다고 생각하고 계산함.
- 위에서 연산된 것: array 길이 X array 길이 X 비교연산 1번
- array(입력값) 길이는 보통 N으로 표현하므로, 위의 식은 N X N = N^2 로 표현.
- 위의 함수는 N^2만큼의 시간이 걸렸다고 표현.
- 입력값: 함수의 크기가 변경될 수 있는 값. ex) 위에서의 배열
- N에 숫자를 대입하는 것이 아니라, 수식으로 표현해야 함.
- 이유: (시간 복잡도: N의 크기에 따른 시간의 상관관계), N=40 이면 1600 보다 40 X 40이 적합.
def find_max_num(array):
max_num = array[0] # 대입 연산 1번 실행
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행
return max_num
- array의 길이를 N이라고 하면, 이 함수는 1 + 2 X (1 + 1) = 2N + 1 만큼의 시간이 걸림.
- 첫 번째와 두 번째를 비교하면 얼마나 효율적인지 정량비교 가능. 작을수록 효율적.
- 보통 상수는 신경쓰지 말고, N(입력값)에 비례해서 얼마나 증가하는지 파악하면 됨.
- 2N + 1과 N^2의 비교에서 N의 지수만 확인하는 것처럼.
- 모든 코드를 실행 단위 살펴보면서 몇 번의 연산이 발생하는지 확인하는 건 불가능.
- 즉, 첫 번째 풀이(2N + 1)는 N 만큼의 연산량이 필요함.
- 두 번째 풀이(N^2)는 N^2만큼의 연산량이 필요함.
- 상수의 연산량은 1만큼 필요함.
1-7. 공간 복잡도 판단하기
01. 공간 복잡도란?
- 공간 복잡도: 입력값과 문제를 해결하는데 걸리는 공간과의 상관관계
- ex) 입력값이 2배로 늘어났을 때 문제를 해결하는데 걸리는 공간은 몇 배로 늘어나는지
- 좋은 알고리즘: 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘
02. 최빈값 찾기 알고리즘의 공간 복잡도 판단해보기
- 공간복잡도 계산: 저장하는 데이터 양이 1개의 공간을 사용함.
## 첫 번째 방법 (공간복잡도: 29)
def find_max_occurred_alphabet(string):
alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]
# 26개 공간 사용
max_occurrence = 0 # 1개
max_alphabet = alphabet_array[0] # 1개
for alphabet in alphabet_array:
occurrence = 0 # 1개
for char in string:
if char == alphabet:
occurrence += 1
if occurrence > max_occurrence:
max_alphabet = alphabet
max_occurrence = occurrence
return max_alphabet
## 두 번째 방법 (공간복잡도: 30)
def find_max_occurred_alphabet(string):
alphabet_occurrence_list = [0] * 26 # 26개, 인덱스의 요소 하나하나도 1개로 취급
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a') # 1개
alphabet_occurrence_list[arr_index] += 1
max_occurrence = 0 # 1개
max_alphabet_index = 0 # 1개
for index in range(len(alphabet_occurrence_list)):
alphabet_occurrence = alphabet_occurrence_list[index] # 1개
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a'))
- 29, 30 둘 다 상수라 큰 상관 X. 시간 복잡도로 비교해야 함.
- 대부분 문제에서는 알고리즘 성능이 공간에 의해 결정되지 않음. 공간복잡도 희생해라.
## 첫 번째 방법 (시간복잡도: 52N + 104)
# 26 * (1 + 2*N + 3) = 52N + 104
for alphabet in alphabet_array: # alphabet_array의 길이(26)만큼 실행
occurrence = 0 # 대입 연산 1번 실행
for char in string: # string(입력값: N)의 길이만큼 실행
if char == alphabet: # 비교 연산 1번 실행
occurrence += 1 # 대입 연산 1번 실행
if occurrence > max_occurrence: # 비교 연산 1번 실행
max_alphabet = alphabet # 대입 연산 1번 실행
max_occurrence = number # 대입 연산 1번 실행
## 두 번째 방법 (시간복잡도: 3N +106)
# N*(1+2) + 2 + 26*(1+3) = 3N + 106
for char in string: # string의 길이만큼 아래 연산이 실행
if not char.isalpha(): # 비교 연산 1번 실행
continue
arr_index = ord(char) - ord('a') # 대입 연산 1번 실행
alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행
max_occurrence = 0 # 대입 연산 1번 실행
max_alphabet_index = 0 # 대입 연산 1번 실행
for index in range(len(alphabet_occurrence_list)): # alphabet_array의 길이(26)만큼 실행
alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행
if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행
max_occurrence = alphabet_occurrence # 대입 연산 1번 실행
max_alphabet_index = index # 대입 연산 1번 실행
- 52N + 104, 3N + 106은 N^2에 비해 터무니없이 부족함.
- 공간복잡도보다는 시간복잡도를 신경써야 함.
- 시간복잡도에서 입력값은 N으로 표기하고, for문은 * 계산, if문, 비교, 대입 연산은 + 로 계산함.
1-8. 점근 표기법
01. 점근 표기법이란?
- 점근 표기법 (asymptotic notation): 알고리즘의 성능을 수학적으로 표기하는 방법
- 알고리즘 '효율성'을 평가하는 방법임.
- 사전적 정의: 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
- 어떤 함수는 N 정도의 시간, 공간이 걸리겠구나 하고 분석하는 것도 점근 표기법의 일종. (위에서 한 것)
- 점근 표기법 종류:
- 1. 빅오(Big-O)표기법: 최악의 성능이 나올 때의 연산량 표기. ex) O(N)
- 2. 빅 오메가(Big-Ω)표기법: 최선의 성능이 나올 때의 연산량 표기. ex) Ω(1)
- ex) a 입력값은 10분 걸리는 반면, b 입력값은 300분이 걸림
02. [실습] 배열에서 특정 요소 찾기
## 시간복잡도: N * 1 = N
def is_number_exist(number, array):
for element in array: # array 길이(입력값: N)만큼 실행
if number == element: # 비교 연산 1번 실행
return True
return False
- 운 좋으면 한 번에 찾을 수 있지만, 그렇지 않다면 N번의 연산 후에 찾을 수 있음.
- 알고리즘 성능은 항상 동일하지 않고, 입력값 및 입력값 분포에 따라 변화.
- 빅오 표기법: O(N), 빅 오메가 표기법: Ω(1) 시간복잡도를 가진 알고리즘임.
- 대부분의 알고리즘은 거의 빅오 표기법으로 분석.
- 이유: 최선의 입력값일 가능성은 낮고, 항상 최악의 경우(빅오 표기법)를 대비해야 하기 때문.
- 최종 정리:
- 1. 입력값에 비례해서 연산량이 얼마나 늘어날지 파악. (N의 지수가 중요)
- 2. 중요도: 공간복잡도 << 시간복잡도
- 3. 빅오 표기법(최악의 경우)에 대해 고민하라. (앞으로 알고리즘은 빅오 표기법의 시간복잡도 분석)
1-9. 알고리즘 더 풀어보기 (1)
01. [실습] 곱하기 or 더하기
- 0, 1은 더하고, 나머지는 곱하기로 계산해야 함.
- 페이스북 기출문제임.
- 시간복잡도: O(N)만큼 걸린다. 그냥 1차 반복문 나왔는데, array 길이만큼 반복되니 N으로 생각.
def find_max_plus_or_multiply(array):
multiply_sum = 0
for number in array:
if number <= 1 or multiply_sum <= 1:
# 초기 합계가 0이므로, 요소가 0, 1뿐만 아니라 합계가 0, 1일 때도 더하기 해줘야 함.
# 합계 0: 완전 초기 상태이므로 더하기
# 합계 1: 초기에서 1을 더한 것이므로 다음 요소와 더하기
multiply_sum += number
else:
multiply_sum *= number
return multiply_sum
1-10. 알고리즘 더 풀어보기 (2)
01. [실습] 반복되지 않는 문자
def find_not_repeating_first_character(string):
alphabet_occurrence_array = [0] * 26
# 앞에서 초기화 리스트에 알파벳 빈도수 찾은 것을 이용. 빈도수 1이면 반복 X. 이거 찾기.
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord("a")
alphabet_occurrence_array[arr_index] += 1
not_repeating_character_array = []
for index in range(len(alphabet_occurrence_array)):
alphabet_occurrence = alphabet_occurrence_array[index]
# 빈도수가 1인 알파벳 찾기
if alphabet_occurrence == 1:
not_repeating_character_array.append(chr(index + ord("a")))
# 다시 원래의 문자로 돌려주기
for char in string:
if char in not_repeating_character_array:
return char
# 입력값과 빈도수가 1인 알파벳 일치하는지 확인하고 출력
return "_"
result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))
- 시간복잡도: 이중 반복문이 없고 1차 반복문만 있는데, array(입력값) 길이만큼 반복하므로 O(N).
1-11. 끝 & 숙제 설명
01. [실습] 소수 나열하기
## 소수 나열하기 답안
# 2, 3으로 나머지 0이 아니면 합성수(6)로도 나눠떨어지지 않음. 아래에 개선된 버전.
input = 20
# 소수는 약수가 자기 자신과 1뿐.
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1): # n: 2 ~ 20(number), 얘네들 소수인지 판별
for i in range(2, n): # 2 ~ 19(number-1)
if n % i == 0:
break # 1과 자기 자신이 없는데 나머지가 0? 그러면 소수가 아니야
else: # break문이 한번도 발생하지 않았다면
prime_list.append(n) # 리스트에 추가
return prime_list
result = find_prime_list_under_number(input)
print(result)
## 소수나열하기 1차 개선
input = 20
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1): # n: 2 ~ 20
for i in prime_list: # i: 2 ~ 19(n: 2 ~ 19(number-1)) 사이의 소수
if n % i == 0:
break
else: # n = 2 일때, 바로 이쪽으로 온다
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)
## 소수 나열하기 2차 개선
# 주어진 자연수 N이 소수이기 위한 필요 충분 조건은 N이 N 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않음.
# 나눗셈에서 몫과 나누는 수 둘 중 하나는 반드시 N의 제곱근 이하임.
# prime_list에서도 N = 20일때 소수인 19로 나눠줄 필요가 없음.
input = 20
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1):
for i in prime_list:
if n % i == 0 and i * i <= n: # 여기 조건이 추가됨, i는 2 3 5만 있으면 됨
break
else:
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)
02. [실습] 문자열 뒤집기
- 알고리즘 문제풀이 팁:
- 1. 바로 코드 작성하지 말고, 문제의 다른 예시들로 규칙성 파악하기. ex) 00000의 최소횟수는?
- 2. 배웠던 자료구조 활용하기 ex) 스택, 큐
- 3. 문제의 특징을 하나씩 글로 써보기 ex) 문자열 뒤집는데 0, 1 중 고민됨. 초기 0, 1도 횟수와 연관.
## 답안 코드
# 고려해야 할 것: 1) 뒤집어 질 경우, 2) 첫 번째 원소가 0인지 1인지
# 위의 두 개를 계산하면 모두 0으로 만드는 횟수, 모두 1로 만드는 횟수 구함.
# 이 중 최솟값을 반환해주면 해결.
input = "011110"
def find_count_to_turn_out_to_all_zero_or_all_one(string):
count_to_all_zero = 0 # 0 -> 1 전환되는 순간에 += 1
count_to_all_one = 0 # 1 -> 0 전환되는 순간에 += 1
if string[0] == '0':
count_to_all_one += 1
elif string[0] == '1':
count_to_all_zero += 1
for i in range(len(string) - 1):
if string[i] != string[i + 1]: # 1 -> 0, 0 -> 1
if string[i + 1] == '0': # 1 -> 0: 앞의 수를 전부 0으로 변환시켜야 됨
count_to_all_one += 1
if string[i + 1] == '1':
count_to_all_zero += 1
return min(count_to_all_one, count_to_all_zero) # 최솟값 반환
result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)
03. 문자열 요약해보기
'스파르타코딩클럽 > 강의 정리' 카테고리의 다른 글
[스파르타] 웹 프로그래밍 A-Z 기초 5주차 (완강) (0) | 2021.12.16 |
---|---|
[스파르타] 웹 프로그래밍 A-Z 기초 4주차 (완강) (0) | 2021.12.16 |
[스파르타] 웹 프로그래밍 A-Z 기초 3주차 (완강) (0) | 2021.12.15 |
[스파르타] 웹 프로그래밍 A-Z 기초 2주차 (완강) (0) | 2021.12.15 |
[스파르타] 웹 프로그래밍 A-Z 기초 1주차 (완강) (0) | 2021.12.13 |