[WEEK01] 컴퓨팅 사고로의 전환(1)

✨ 이번 주 핵심 키워드 ✨
: 배열, 문자열, 반목문, 재귀함수, 계산복잡도(수학), 정렬, 완전탐색, 정수론

week00 팀 프로젝트가 끝나고 본격적인 정글 커리큘럼이 시작됐다.
week01~04는 '컴퓨팅 사고로의 전환'이라는 주제로 팀별로 백준 알고리즘 문제를 풀게된다.

이번 주에 다시 새로운 조 배정을 받았는데, 이번엔 두 명이서 팀을 하게 되었다.
새로운 동료는 아주 차분하고 똑똑한 친구여서 한 주 내내 도움을 많이 받았다.
이미 알고리즘 문제를 여럿 풀었던 친구라 문제도 쓱쓱 잘 풀고, 코드 리뷰때도 눈으로 쓱 보고 바로 이해하는걸 보고 속으로 엄청 놀랐다. 난 언제쯤 저렇게 될까!

정글 오기전에 파이썬 문법만 간신히 보고와서 그런지 따라가기가 조금 벅차다.
문제의 정답 코드 이해하는 것도 한참 걸려서 관련된 이론까지 파고들기가 힘들었다.
다행히 주변에 다른 동료들이 열띤 토론을 종종 해줘서 내용을 눈치껏 주워듣고 머리에 쑤셔박고 있는 중이다.
정말 고맙고 앞으로도 내 주변에서 토론해줬음 좋겠다ㅋㅋ

첫 시험은 3문제 중 2개를 맞았다.
틀린 문제는 재귀함수로 풀었어야 했는데, 끝까지 알고리즘을 짜내지 못했다. 어떻게 짜야할지 감이 안오더라.
00주차에 같은 팀이었던 동료들이 3문제를 전부 맞은 걸 보고 아주 슬펐다...ㅎ
그 중 한 명이 '누님 수학을 좀 더 공부하셔야 겠는데요?'라고 뼈를 때렸는데 아직도 안 나았다.
다음 주엔 시험 치기 전에 기절시킬까 고민 중이다.

이번 주 키워드를 완벽하게 공부했다고는 결코 말할 수 없지만,
각 키워드별로 몰랐던 부분과 더 공부해야할 부분들을 기록으로 남기고 추후에 계속 공부할 생각이다.
다음 주도 화이팅 하자!

1. 입출력, 조건문, 반복문, 배열, 함수, 문자열

• map(function, iterable 자료형) : iterable 자료형을 하나씩 함수를 적용시켜 반환해줌. 주로 리스트로 감싸서 사용한다.
• print(f'{변수:.3f}') : f스트링 내에 ':.3f' 식으로 소수점 아래 표시하고 싶은 자릿수를 넣어줌.
• print(문자열, sep='/') : sep은 구분자를 의미. 문자열 사이에 /를 넣어서 반환한다.
• print(문자열, end='') : end를 사용하면 그 뒤의 출력값이 줄바꿈이 되지 않는다.
• ord(문자) : 문자를 아스키 코드로 변환
• chr(숫자) : 숫자를 아스키 코드로 변환
• split() : 문자열 분리, 특정 기호를 지정해 그것을 기준으로 분리할 수도 있다.

2. 계산복잡도(수학)

• 앞으로 달팽이는 나무에 올라가지 않기로 하자.
• import math : math 모듈은 수학 관련 함수들은 모아둔 모듈
• .ceil(), .floor() : math모듈의 함수 중 하나로, 각각 올림과 내림하여 정수로 반환
• 에라토스테네스의 체 : 소수를 찾는 방법 중 하나.
  1) 2부터 차례대로 모든 자연수를 나열
  2) 그 중 가장 작은 수인 2를 선택하고, 나머지 2의 배수들은 모두 제거
  3) 남아있는 수 중에서 가장 작은 수인 3을 선택하고, 나머지 3의 배수들은 모두 제거
  4) 위 과정을 반복하여 남아있는 수가 소수.
• 골드바흐의 수 : 2부다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
• 골드바흐 파티션 : 짝수를 두 소수의 합으로 나타내는
• for문 안의 언더스코어(_ ) : 더미변수로 사용됨. 변수의 이름을 생략하고 정해진 반복횟수만큼 반복.

3. 재귀함수

• math.factorial(변수) : math 모듈 안에 팩토리얼 함수 존재
• itertools 모듈 : 반복 가능한 iterable 객체들에 대한 다양한 연산 수행 가능
  1) combination(문자열, n) : 조합 함수. 문자열에서 n개의 요소로 이루어진 모든 조합 생성
  2) permutation(문자열, n) : 순열 함수. n개의 요소로 이루어진 순열 조합 생성.
• global : 변수를 전역 스코프에서 사용할 수 있도록 함. 함수 내에서 global을 사용해 변수를 선언하면, 해당 변수는 전역스코프에서 유효해지며, 함수 외부에서도 사용 가능.
• Scope : 변수가 어디서부터 유효한지를 나타내는 개념.(어느 범위 내에서 유효한지) 파이썬에서 변수의 스코프는 변수가 정의된 위치에 따라 결정됨(4가지 종류 : 전역/지역/함수중첩/내장 스코프)
• 재귀함수 쓸 때, if-return문으로 탈줄 조건을 명확히. 변수로는 현재위치, 방문한위치, 방문갯수 등을 고려해보면 더 알고리즘 짜기 쉬울 수 있음.
• Nqueen과 Z는 종종 다시 풀어보자. 재귀 알고리즘 짜는게 너무 서툴다.

4. 정렬

• import sys, sys.stdin.readline() : 파이썬의 표준 라이브러리인 sys를 사용하면 input으로 입력받을 때보다 더 빠르고 적은 메모리를 사용한다.
• 도수정렬(=카운팅정렬=계수정렬) : 비교기반 정렬 알고리즘이 아닌 정수들의 개수를 세는 방식으로 동작하는 알고리즘(대소관계를 판단하지 않고 빠르게 정렬)
  1) 주어진 배열 a 안에 있는 요소들을 모두 순회하며 각 요소가 몇 번 등장하는지를 세고, 그 결과를 이용해 정렬된 배열을 생성.
  2) 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단게로 이루어짐
• set() : 파이썬 내장 기본 함수. 중복삭제
• words.sort(key=lambda x : (len(x), x))
  1) sort의 key 옵션을 사용하여 정렬 기준을 지정.
  2) lambda 함수를 사용하여 두 가지 정렬 기준 제시. (len(x)와 x)
  3) 두 기준 중 x는 말 그대로 오름차순을 의미
• sorted와 sort : 두 가지 모두 리스트를 정렬하는 파이선 내장 함수
  1) sorted는 기존 리스트를 변경하지 않고 새로운 정렬된 리스트를 반환(원본 유지)
  2) sort는 기존 리스트를 정렬하여 변경(원본 변경)

5. 완전탐색

• 완전탐색 : 모든 경우의 수를 전부 체크해서 정답을 찾는 방법
• brute force 기법 : 조건문을 활용해 모두 테스트하는 방법, 시간 복잡도가 높음.
• 재귀 호출 : 자기자신을 계속해서 호출
• 비트마스크 : 비트연산을 이용하여 부분집합을 나타내는 기법.
  1) 비트연산을 사용하여 간단하게 집합을 표현(Z문제에서도 비슷한 개념을 사용했었음)
  2) 사용시 비트연산의 우선순위와 오버플로우 등의 문제, 가독성이 떨어진다는 점 주의
  3) 오버플로우 : 변수에 저장(표현) 가능한 범위를 넘어서는 현상
• BFS : 그래프 탐색 알고리즘(너비 우선 탐색)
  1) 시작점에서 거리가 가까운 점부터 우선적으로 탐색하는 방법
  2) 큐(queue)자료구조를 사용,
• DFS : 그래프 탐색 알고리즘(깊이 우선 탐색)
  1) 시작점에서 한 경로를 따라 끝까지 탐색한 후, 다시 돌아와서 다른 경로를 탐색하는 방법
  2) 모든 경로를 탐색하지 않기 때문에 최단경로 문제 해결에는 적합하지 않음
  3) 스택(stack)자료구조 혹은 재귀함수를 사용하여 구현 가능
• 백트래킹 : 모든 경우의 수를 탐색하며 문제를 해결하는 알고리즘
  1) 일반적으로 재귀적인 방법을 사용하여 구현되며, 대부분의 경우 DFS 알고리즘과 함께 사용됨
  2) DFS는 현재 위치에서 다음 위치로 이동하는 방법을 찾아가며 탐색을 진행하는데,
  3) 만약 현재 위치에서 더 이상 탐색할 수 있는 경로가 없다면 이전 단계로 돌아가서 다른 가능한 경로를 찾음.
  4) 이러한 과정을 반복하면서 문제의 조건에 맞는 결과를 찾아내는 것이 백트래킹 알고리즘의 핵심.
  5) 하지만 백트래킹은 모든 가능한 경우의 수를 탐색하므로 실행시간이 길어질 수 있어 효율적인 알고리즘을 설계하는 것이 중요.
• abs() : 절대값 반환
• 다이나믹 프로그래밍(동적계획법) : 복잡한 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 기법
  1) 문제를 작은 하위 문제로 분할, 각 하위 문제를 한 번만 풀고 그 결과를 저장, 저장된 결과를 이용하여 원래 문제를 해결

추가 공부 필요
: 그리디 알고리즘, DFS, BFS... 아직도 이해가 잘 안간다...

+++ 정글 docs에 동료들의 개발일지 링크 목록이 올라왔다.
왜... 내 링크가 가장 위에 있는가.... 부디 다들 실수로 들어오더라도 흐린 눈으로 보고 지나가줬으면 좋겠다...