$$config title: 디지털스마트부산아카데미 5기 PCCP keywords: - IT $$ # 수업자료 ## 강사 연락처 - [강사 오픈톡](https://open.kakao.com/o/swKTT78e) ## 성장과 취업을 위한 팁 - 블로그를 만드세요. - 블로그에 메모용 글을 많이 쓰세요. - 블로그에 알고리즘 풀이를 자주 쓰세요. ## 수업페이지 - [수업페이지 - slog.gg/p/13750#f](https://www.slog.gg/p/13750#f) - [프로그래머스 클래스 - 학생 - https://campus.programmers.co.kr/app/courses/24670](https://campus.programmers.co.kr/app/courses/24670) - [excalidraw](https://excalidraw.com/) ## 기초수련 - [프로그래머스 파이썬 입문](https://programmers.co.kr/learn/courses/2) - [프로그래머스 - 파이썬을-파이썬답게](https://school.programmers.co.kr/learn/courses/4008/4008-파이썬을-파이썬답게) - [프로그래머스 - 알고리즘, 레벨 0](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=0&languages=python3&page=1) - [프로그래머스 - 알고리즘, 레벨 1](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=1&languages=python3&page=1) - [프로그래머스 - 알고리즘, 레벨 2](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=2&languages=python3&page=1) - [프로그래머스 - 알고리즘, 레벨 3](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=3&languages=python3&page=1) - [개발자용 블로그 플랫폼 - 벨로그](https://velog.io/) - [점프 투 장고 - 서비스를 만들면서 공부하기 좋은 자료](https://wikidocs.net/book/4223) ## 관련자료 - [repl.it - 새 파이썬 개발환경 - https://replit.com/new/python3](https://replit.com/new/python3) - [mycompiler - python](https://www.mycompiler.io/ko/new/python) - [파이썬 비주얼라이저 - https://pythontutor.com/render.html#mode=edit](https://pythontutor.com/render.html#mode=edit) - [파이썬 비주얼라이저 - https://cscircles.cemc.uwaterloo.ca/visualize](https://cscircles.cemc.uwaterloo.ca/visualize) - [파이참 에디터 다운로드](https://www.jetbrains.com/ko-kr/pycharm/download) ![img](https://i.imgur.com/4jmu5rs.png) # 1주차 ## 가입해야 하는 사이트 - [개발자용 블로그 플랫폼 - 벨로그](https://velog.io/) - [repl.it - 새 파이썬 개발환경 - https://replit.com/new/python3](https://replit.com/new/python3) ## 알고리즘 공부 팁 - 알고리즘 공부를 절대로 효율적으로 하려고 하지마세요. - 재미를 따라가세요. - 쉬운문제를 많이 푸세요. - 백준 안풀어도 됩니다. 프로그래머스만으로 충분합니다. - 나중에 풀 문제 큐를 만드세요. ## 기초수련 자료 설명 - 알고리즘은 꾸준함이 중요합니다. 기초가 부족하시다면 보충자료를 잘 활용해주세요. - 관련자료에 유용한 기능들이 많이 있습니다. 이를 활용하시면 부족한 부분을 채울 수 있습니다. - 프로그래머스 파이썬 입문은 5회 이상, 파이썬 답게는 1회 이상 풀어주세요. - 프로그래머스 알고리즘 레벨 0, 1, 2 문제를 전부 다 풀어주세요 - 하루에 코드메모용 글을 무조건 하나 이상 작성해주세요. 나중에 정말 엄청난 힘이 됩니다. - 알고리즘 공부가 흥미가 떨어지고 힘에 부친다면 간단한 웹 서비스를 구현해보세요. 장고로 웹 사이트를 구현하면 자연스럽게 논리력이 향상됩니다. - [개발자용 블로그 플랫폼 - 벨로그](https://velog.io/) ## velog 코드 메모용 글 템플릿 글 템플릿 ### 템플릿(#은 무시하세요.) ```` [제목](참조url) ```py # 소스코드 ``` ```` ### 예시 ```` [문제링크 - 프로그래머스 - 두 수의 차](https://school.programmers.co.kr/learn/courses/30/lessons/120803?language=python3) ```py def solution(num1, num2): answer = 0 return answer ``` ```` ## 생각하는 힘을 기르는 방법 - [영상 - 생각할 줄 모르는 아이, 이렇게 연습시키세요!!(황농문 교수)](https://www.youtube.com/watch?v=4QSl6r6hzYU) - 우리 두뇌는 목표 지향적으로 설계 되어 있습니다. 즉, 무얼 원하느냐에 따라서 관련 시냅스가 발달하게 됩니다. - 개발자는 논리사고력이 기본 코어가 탄탄해야 합니다. 쉽게 말해 생각하는 힘이 있어야 합니다. 이를 기르기위해선 수학적 문제를 풀어야합니다.(알고리즘) - 이때 성장을 위해선 본인이 풀 수 있는 문제에서 조금 어려운 문제를 선택해야 합니다. 그리고 절대로 정답을 봐서는 안됩니다. 한문제를 붙들고 일주일 혹은 한달을 고민해도 좋습니다. 스스로 풀어낼 때까지 도전 하세요. - 왜냐면 사고력은 어떤문제를 해결할때 도무지 어떻게 해야할지 모르겠다는 그순간부터 생각할때 성장하기 때문입니다. - 다만, 초심자 입장에서는 쉬운 난이도로 성공경험을 10번 정도 만들고 시작하는 걸 추천합니다. 결국 재미가 있어야 꾸준히 할 수 있습니다. ## 검색 팁 - chatGPT 와 구글링은 힌트나 개념 이해 용도로만 사용하셔야 합니다. - [크롬 익스텐션, 트랜스 오버](https://chrome.google.com/webstore/detail/transover/aggiiclaiamajehmlfpkjmlbadmkledi) ## 빠르게 보는 기초문법 # 연산자, 조건문, 반복문 ## 개념 - 연산자 종류 - 대입연산 : - `=` : 넣는다. - 사칙연산 - `+` : 더하기 - `-` : 빼기 - `*` : 곱하기 - `/` : 나누기 - 논리연산 - `==` : 같다 - `!=` : 다르다 - `>` : 크다(초과) - `<` : 작다(미만) - `>=` : 크거나 같다(이상) - `<=` : 작거나 같다(이하) - `and` : 그리고(and) - `or` : 또는(or) - 소스코드의 5대 구성 요소 - 변수 - 변수선언 : a = 10 - `a`를 변수명이라고 한다. - `a라는 변수를 만들겠습니다. 그리고 이 안에 숫자 10을 넣겠습니다.` 라는 뜻이다. - 변수의 값은 바꿀 수 있다. - 변수는 값을 넣을 때 빼고는 값(자신이 가지고 있는) 취급을 해야 한다. - 값 - 종류 - 숫자(1, 2, 3.14) - 문자열("a", "", "abc", "\n") - 논리형/Boolean(True, False, 1 == 1) - 함수 - 종류 - 내장함수 - 사용자정의 함수 - 조건문 - if - elif - if 뒤에 붙을 수 있다. - 역할 : 여러 if문을 한 덩어리로 만들어준다. - else - if나 elif 뒤에 붙을 수 있다. - 역할 : 위에서 모든 경우가 실패했을 때 실행된다. - 반복문 - for - while ## 문제 ### 변수 - [문제 : 안녕하세요. 10번 출력(개념 : print)](https://repl.it/@jangka512/TurboCrimsonClasses) - [정답](https://repl.it/@jangka512/AltruisticWillingFunctions) ### 조건문 - [문제 : 나이에 따른 올바른 말이 나오도록 해주세요.(개념 : 조건문, if문)](https://repl.it/@jangka512/YummySubduedDriver) - [정답](https://repl.it/@jangka512/OnerlookedSelfreliantRouter) - [문제 : 실행되는 출력문에는 `참` 그렇지 않으면 `거짓` 이라고 적어주세요.(개념 : 조건문, if문)](https://repl.it/@jangka512/FrigidMildCell) - [정답](https://repl.it/@jangka512/DamagedDependentBackticks) # 조건문과 반복문 ## 개념 - i = i + 1 => i의 값을 1 증가 시킨다. - i += 1 => i의 값을 1 증가 시킨다. - i = i - 3 => i의 값을 3 감소 시킨다. - i -= 3 => i의 값을 3 감소 시킨다. - 10 % 3 == 1 => `%`는 몫이 아닌 나머지를 반환한다. - i % 2 == 0 => `참` 이라면 i는 짝수라는 뜻 이다. - 소스코드의 4대 구성 요소 - 변수 - 값 - 조건문 - if문 - 반복문 - while문, for 문 - 반복문안에 또 반복문을 넣을 수 있다. ## 문제 ### while - [문제 - 1부터 300까지 출력해주세요.(개념 : while)](https://repl.it/@jangka512/TediousLoudDonateware) - [문제 - 정답](https://repl.it/@jangka512/KnottyAncientTranslations) - [문제 - 1부터 100 사이의 짝수만 출력해주세요.(개념 : while, if, %)](https://repl.it/@jangka512/PowerlessHumongousFlashdrives) - [문제 - 정답](https://repl.it/@jangka512/DescriptiveTriangularSoftware) - [문제 - 1부터 5까지의 합을 출력해주세요.(개념 : while)](https://repl.it/@jangka512/MulticoloredBigSpellchecker) - [정답](https://repl.it/@jangka512/GrowlingDistantGenerics) - [문제 - 1부터 100까지의 수 중에서 짝수의 합을 출력해주세요.(개념 : while, if, %)](https://repl.it/@jangka512/NormalEminentVariety) - [정답](https://repl.it/@jangka512/EasyKhakiAbstractions) ### for - [개념 : for 문](https://repl.it/@jangka512/CoolShoddyMicroprogramming) - [문제 : for문으로 1부터 100까지 출력](https://repl.it/@jangka512/TastyUsefulDisplaymanager) - [문제 - 정답](https://repl.it/@jangka512/SafeJealousCallback) - [문제 : for문으로 100부터 1까지 출력](https://repl.it/@jangka512/OrderlyGiddySystemresource) - [문제 - 정답](https://repl.it/@jangka512/FrivolousGloriousApplicationpackage) - [문제 : for문으로 1부터 100 사이의 짝수만 출력](https://repl.it/@jangka512/ExtrovertedSelfassuredShareware) - [문제 - 정답](https://repl.it/@jangka512/TwinForkedPlots) - [문제 : for문으로 100부터 1 사이의 짝수만 출력](https://repl.it/@jangka512/WryFocusedRedundancy) # 함수 ## 개념 - 함수 - 자주 사용되는 코드를 별도의 독립적인 공간으로 격리시킨 것 - 함수의 매개변수 - 함수의 데이터 투입구 - 여러개 가능 - 함수의 리턴 - 함수의 데이터 배출구 - 이게 실행되면 함수가 그 즉시 종료 ## 문제 - [문제 - 5칙연산을 수행하는 함수를 만들어주세요.(개념 : 함수, 리턴)](https://repl.it/@jangka512/AgilePositiveDatabases) - [문제 - 정답](https://repl.it/@jangka512/LateImpartialCoins) - [문제 - 온도단위 섭씨를, 화씨로 바꿔주는, 함수 c_to_f 를 구현해주세요.](https://repl.it/@jangka512/GuiltyMiniConversion) - [문제 - 정답](https://repl.it/@jangka512/UniqueOldlaceMozbot) - [문제 - 입력받은 정수의 모든 약수의 합을 리턴하는 함수를 구현해주세요.(개념 : 함수, 반복문, 리턴)](https://repl.it/@jangka512/LegitimateAdmiredSoftware) - [문제 - 정답](https://repl.it/@jangka512/UnsungDeficientDoom) - [문제 - 입력받은 정수가 소수인지 아닌지 알려주는 함수를 구현해주세요.(개념 : 함수, 반복문, 리턴)](https://repl.it/@jangka512/OldfashionedAuthenticSdk) - [문제 - 정답](https://repl.it/@jangka512/StudiousIckyNanotechnology) - [문제 - 1부터 1000사이에 존재하는 소수들의 개수를 출력해주세요.(개념 : 함수, 반복문, 리턴)](https://repl.it/@jangka512/WhisperedBreakableAnimatronics) - [문제 - 정답](https://repl.it/@jangka512/CloudyMindlessTransformation) # 리스트 ## 문제 - 리스트 시작 - [개념 : 객체와 리스트](https://repl.it/@jangka512/RecklessEnviousClasslibrary) - [문제 : 리스트에 순서대로 2, 1, 5, 6, 7를 한번에 담아주세요.](https://repl.it/@jangka512/SecondaryMediumorchidLogic) - [문제 - 정답](https://repl.it/@jangka512/PepperyAcidicMacroinstruction) - [문제 : 비어있는 리스트를 만들고, 순서대로 2, 1, 5, 6, 7를 하나씩 담아주세요.](https://repl.it/@jangka512/AlienatedOriginalCurrencies) - [문제 - 정답](https://repl.it/@jangka512/InformalSteelPaintprogram) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 '토', '일' 을 순서대로 추가해주세요.](https://repl.it/@jangka512/WholeWrathfulRouter) - [문제 - 정답](https://repl.it/@jangka512/MajesticDryDatabase) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 '토', '일' 을 담은 리스트를 만들고 2개의 리스트 합쳐서 새로운 리스트를 만들어주세요.](https://repl.it/@jangka512/RelevantRequiredConditional) - [문제 - 정답](https://repl.it/@jangka512/MeanCreativePort) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 '+=' 연산자를 이용해서 '토', '일' 을 한번에 추가해주세요.](https://repl.it/@jangka512/TriangularPurpleNotification) - [문제 - 정답](https://repl.it/@jangka512/WoodenSlategrayDoom) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 가장 처음 요소를 출력해주세요.](https://repl.it/@jangka512/WavySparseTruespace) - [문제 - 정답](https://repl.it/@jangka512/UncommonActiveHypertalk) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 가장 마지막 요소를 출력해주세요.](https://repl.it/@jangka512/HeartfeltUnknownBetaversion) - [문제 - 정답](https://repl.it/@jangka512/WhisperedEllipticalDeadcode) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 가장 마지막에서 2번째 요소를 출력해주세요.](https://repl.it/@jangka512/LegitimateAdeptTriggers) - [문제 - 정답](https://repl.it/@jangka512/CultivatedAliceblueProfessional) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 while문을 이용해서 요소 전부 출력해주세요.](https://repl.it/@jangka512/LumpyButteryRuntimes) - [문제 - 정답](https://repl.it/@jangka512/RoundDefenselessInterfaces) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 그리고 while문을 이용해서 요소 전부 역순으로 출력해주세요.](https://repl.it/@jangka512/UnitedUnkemptGraphics) - [문제 - 정답](https://repl.it/@jangka512/WirelessSpicyLevel) - [문제 : 리스트에 순서대로 2, 1, '오', 6, 7를 한번에 담아주세요. 그리고 리스트 안에 있는 '오'를 정수 5로 변경해주세요.](https://repl.it/@jangka512/ImmaterialJauntyProtocol) - [문제 - 정답](https://repl.it/@jangka512/WoefulFailingDowngrade) - [문제 : 리스트에 순서대로 2, 1, '오', 6, 7를 한번에 담아주세요. 그리고 리스트 안에 있는 '오'를 제거해주세요.](https://repl.it/@jangka512/ShimmeringFondUtilities) - [문제 - 정답](https://repl.it/@jangka512/KlutzyPromotedIntelligence) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. '화'가 리스트 안에 들어있는지 알려주세요.](https://repl.it/@jangka512/JampackedEvergreenAssociate) - [문제 - 정답](https://repl.it/@jangka512/WholeVillainousDifference) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. '화'가 리스트 안에서 몇 번째 데이터 인지 알려주세요.](https://repl.it/@jangka512/BoilingSoulfulModem) - [문제 - 정답](https://repl.it/@jangka512/WiseBusyPrograms) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. '화'가 리스트 안에 있는지 if문으로 체크 후, 있다면 삭제해주세요.](https://repl.it/@jangka512/BubblyGigaQuotes) - [문제 - 정답](https://repl.it/@jangka512/TechnologicalAlarmingThings) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. '토'가 리스트 안에 있는지 if문으로 체크 후, 있다면 삭제해주세요.](https://repl.it/@jangka512/StridentPoliteMegabyte) - [문제 - 정답](https://repl.it/@jangka512/OurFocusedAnalysts) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 리스트에 있는 '금'을 삭제하는 3가지 방법을 보여주세요.](https://repl.it/@jangka512/PricklyBuzzingAutoresponder) - [문제 - 정답](https://repl.it/@jangka512/CompetentIncrediblePassword) - [문제 : 리스트에 순서대로 '월', '화', '수', '목', '금'을 한번에 담아주세요. 리스트에 있는 '금'을 안전하게 삭제하는 2가지 방법을 보여주세요.](https://repl.it/@jangka512/UprightCuddlyBusinesses) - [문제 - 정답](https://repl.it/@jangka512/SandybrownNeedyCharactercode) - [문제 - 1부터, 10까지 리스트로 묶어주세요](https://repl.it/@jangka512/EnormousMedicalModes) - [문제 - 정답](https://repl.it/@jangka512/RareWholePixel) - 리스트 끝 ## 문자열 - [개념 : 문자열, 문자, 자르기](https://repl.it/@jangka512/DarkgreenSaltyBinarytree) - [문제 : 문자열 기초 종합 문제 1](https://repl.it/@jangka512/QualifiedExcitedMatter) - [문제 - 정답](https://repl.it/@jangka512/LightgreyAntiqueProtocol) - [문제 - 문장에서 a~f만 제거하고 다시 출력해주세요.](https://repl.it/@jangka512/RelevantStripedRuntime) - [문제 - 정답](https://repl.it/@jangka512/GhostwhiteUnevenVoxels) ## 알고리즘 문제 - [알고리즘 레벨 1 : 직사각형 별찍기](https://programmers.co.kr/learn/courses/30/lessons/12969?language=python3) - [문제 - 정답](https://repl.it/@jangka512/SnappyPeskyCones) - [알고리즘 레벨 1 : 평균 구하기](https://programmers.co.kr/learn/courses/30/lessons/12944?language=python3) - [문제 - 정답](https://repl.it/@jangka512/JitteryNeglectedTransformation) - [알고리즘 레벨 1 : 약수의 합](https://programmers.co.kr/learn/courses/30/lessons/12928?language=python3) - [문제 - 정답](https://repl.it/@jangka512/AustereFrequentComma) - [알고리즘 레벨 1 : 두 정수 사이의 합](https://programmers.co.kr/learn/courses/30/lessons/12912?language=python3) - [문제 - 정답](https://repl.it/@jangka512/TubbyRobustArguments) - [알고리즘 레벨 1 : 수박수박수박수박수박수?](https://programmers.co.kr/learn/courses/30/lessons/12922?language=python3) - [문제 - 정답](https://repl.it/@jangka512/ExpertGratefulServerapplication) - [알고리즘 레벨 1 : 서울에서 김서방 찾기](https://programmers.co.kr/learn/courses/30/lessons/12919?language=python3) # 2주차 ## 역대 네카라쿠배 출제유형 빈도 | 빈도 | 유형 | | -- | -- | | 19% | DFS/BFS | | 19% | 문자열 | | 16% | 단순구현 | | 13% | 해시 | | 06% | 완전탐색 | | 06% | DP | | 06% | 다익스트라 | | 03% | 재귀함수 | - [출처 - 네카라쿠배 코딩 테스트 유형과 준비 방법](https://youtu.be/mIf-ZqfK4EA) ## 코테 준비 - 적은 지식 + 많은 경험 => DFS, BFS, 재귀, DP 기초 재료 + 많은 문제 풀기 - 문제 푸는 갯수에 대한 욕심을 버리고, 문제푸는 과정에서 재미를 찾으세요. 알고리즘 실력은 J자 커브로 성장합니다. - 정답 안보고 자력으로 프로그래머스 알고리즘 파이썬3, 레벨 0, 1, 2 풀기 (약 한달) - 3일 이내에 안풀리면 정답을 살짝 보고 체크 후 며칠 후 다시 도전 ## 재귀함수 = 종료조건 + 재귀식(점화식) ### 개념 - 재귀함수 = 종료조건 + 반복되는 패턴(점화식) - 먼저, A에게 100만원을 빌려달라고 부탁합니다. A는 자신이 가진 돈을 쓸 수 있는 만큼 써서 부족한 부분을 옆사람 B에게 빌립니다. - 하지만 B는 A에게 필요한 돈 전부를 제공하지 못할 수도 있습니다. 그럼 B는 자신이 가진 돈을 쓸 수 있는 만큼 써서 부족한 부분을 옆사람 C에게 빌립니다. - 이러한 과정이 계속 반복됩니다. B가 C에게, C가 D에게, D가 E에게, E가 F에게 돈을 빌리는 식으로 말이죠. 각 사람은 자신이 가진 돈을 쓸 수 있는 만큼 쓰고, 부족한 부분을 옆사람에게 빌립니다. - 만약 F까지 가서도 돈이 부족하다면, A는 100만원을 빌릴 수 없습니다. 하지만 F가 충분한 돈을 빌려준다면, 그 돈은 역순으로 E, D, C, B, A로 돌아가면서 각 사람이 빌렸던 돈을 청산하게 됩니다. - 이렇게 각 사람이 자신의 돈을 쓴 후 부족한 부분을 옆사람에게 빌리고, 빌린 돈을 역순으로 청산하는 과정이 바로 재귀의 개념입니다. - [영상 - 재귀함수가 뭔가요? (Feat. 하노이의 탑)](https://youtu.be/aPYE0anPZqI) ## 재귀로 팩토리얼 구현 ### 팩토리얼 ```py def factorial(n): if n == 0 or n == 1: return 1 else: fac_n_minus_1 = factorial(n-1) result = n * fac_n_minus_1 return result print(factorial(5)) ``` - [문제 - 팩토리얼](https://school.programmers.co.kr/learn/courses/30/lessons/120848) ## 재귀로 피보나치 구현 ### 피보나치 ```py def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: fib_n_minus_2 = fibonacci(n-2) fib_n_minus_1 = fibonacci(n-1) result = fib_n_minus_2 + fib_n_minus_1 return result print(fibonacci(10)) ``` - [문제 - 피보나치](https://school.programmers.co.kr/learn/courses/30/lessons/12945) ## 재귀로 1부터 100까지의 합 구현 ### 1부터 100까지의 합 ```py def recursive_sum(n): if n <= 1: return 1 else: return n + recursive_sum(n-1) result = recursive_sum(10) print(result) # 결과: 55 ``` - [문제 - 콜라문제](https://school.programmers.co.kr/learn/courses/30/lessons/132267) ## 재귀로 문자열 뒤집기 ### 문자열 뒤집기 ```py def reverse_string(s): if len(s) == 1: return s else: last_one = s[-1] rest = reverse_string(s[:-1]) return last_one + rest print(reverse_string("hello")) ``` - [문제 - 문자열 밀기](https://school.programmers.co.kr/learn/courses/30/lessons/120921) ## 재귀로 이진탐색 구현 ### 이진탐색 ```py def binary_search(arr, low, high, x): if high >= low: mid = (high + low) // 2 if arr[mid] == x: return mid elif arr[mid] > x: return binary_search(arr, low, mid - 1, x) else: return binary_search(arr, mid + 1, high, x) return -1 # 정렬된 리스트와 찾고자 하는 값을 설정합니다. nums = [2, 3, 4, 10, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 700, 800, 1000, 1115] x = 800 # 이진 탐색 함수를 실행합니다. result = binary_search(nums, 0, len(nums)-1, x) if result != -1: print("Element is present at index", str(result)) else: print("Element is not present in array") ``` ### 도전문제 - [문제 - 입국심사](https://school.programmers.co.kr/learn/courses/30/lessons/43238) - [문제 - 징검다리](https://school.programmers.co.kr/learn/courses/30/lessons/43236) ## DFS, 여러 드라마를 볼 때 하나의 드라마를 끝까지 다 보고 다른 드라마를 본다. ### 개념 - DFS = 하나의 드라마를 끝가지 보기 전까지는 다른 드라마는 안본다. - 드라마 A(총 10화), B(총 20화), C(총 30화)가 있을 때, DFS 방식으로 시청하면 다음과 같이 진행됩니다: - 먼저 드라마 A의 첫 번째 에피소드를 시청합니다. - 계속해서 드라마 A의 에피소드를 시청하며, 총 10화를 모두 볼 때까지 반복합니다. (즉, 깊이 우선으로 A 드라마를 정주행합니다) - 드라마 A를 모두 시청하였으므로, 다음으로 드라마 B의 첫 번째 에피소드를 시청합니다. - 마찬가지로 드라마 B의 에피소드를 계속 시청하여, 총 20화를 모두 볼 때까지 반복합니다. - 드라마 B를 모두 시청한 후, 마지막으로 드라마 C의 첫 번째 에피소드를 시청합니다. - 드라마 C의 모든 에피소드를 시청하여, 총 30화를 모두 볼 때까지 반복합니다. - DFS 방식은 위와 같이 한 방향으로 최대한 깊이 들어가서 탐색한 후 - 다음 경로를 탐색하는 방식입니다. 따라서 드라마 시청에 비유하자면, - 한 드라마의 모든 에피소드를 시청한 후 다음 드라마로 넘어가는 순서로 이해할 수 있습니다. ## 그래프는 정점(노드)와 간선의 집합입니다, DFS는 그래프를 탐색하는 방법 중 하나입니다. ### 간단한 그래프(순환 무향 그래프) ![img](https://i.imgur.com/qv9vzY7.png) ```py graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } ``` ### 조금 복잡한 그래프(순환 무향 그래프) ![img](https://i.imgur.com/l3FcySK.png) ```py graph = { 1: [2, 3, 8], 2: [1, 7], 3: [1, 4, 5], 4: [3, 5], 5: [3, 4], 6: [7], 7: [2, 6, 8], 8: [1, 7] } ``` ## DFS 완전탐색, 방문한 순서대로 노드를 출력해주세요, 비순환 유향 그래프 ![img](https://i.imgur.com/OjLcjL7.png) ### 문제 ```py graph = { 1 : [2, 3], 2 : [4], 3 : [], 4 : [] } sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ### 정답 ```py graph = { 1 : [2, 3], 2 : [4], 3 : [], 4 : [] } def dfs(graph, node): print(node) for nei_node in graph[node]: dfs(graph, nei_node) def sol(graph): dfs(graph, 1) sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ## DFS 완전탐색, 방문한 순서대로 노드를 출력해주세요, 순환 무향 그래프, 이미 방문했는지 체크하는 로직 필수 ![img](https://i.imgur.com/3ksjDHG.png) ### 문제 ```py graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ### 정답 ```py graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } def dfs(graph, visited, node): print(node) # 값이 True 가 아니어도 됩니다. visited[node] = True # for nei_node in graph[node].keys(): 와 아래 코드는 결과가 같습니다. for nei_node in graph[node]: if nei_node in visited: continue dfs(graph, visited, nei_node) def sol(graph): visited = {} dfs(graph, visited, 1) sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ## BFS는 그래프를 탐색하는 방법 중 하나입니다. DFS 와 달리 중심점에서 천천히 탐색범위를 키워갑니다. - BFS = 드라마를 하나 완전히 보기 전에 다른 드라마를 섞어서 봅니다. - 드라마 A(총 10화), B(총 20화), C(총 30화)가 있을 때, BFS 방식으로 시청하면 다음과 같이 진행됩니다: - 먼저 드라마 A의 첫 번째 에피소드를 시청합니다. - 그 다음으로 드라마 B의 첫 번째 에피소드를 시청합니다. - 그리고 드라마 C의 첫 번째 에피소드를 시청합니다. - 그런 다음에 드라마 A의 두 번째 에피소드로 돌아와서 시청합니다. - 그 다음 드라마 B의 두 번째 에피소드를 시청합니다. - 그 후에는 드라마 C의 두 번째 에피소드를 시청합니다. - 이런 방식으로 각 드라마의 모든 에피소드를 돌아가며 시청합니다. 즉, 드라마 A의 모든 에피소드를 보기 전에 드라마 B와 C의 에피소드도 함께 본다는 것입니다. - 이를 시청 순서로 나열하면 다음과 같습니다: A1 -> B1 -> C1 -> A2 -> B2 -> C2 -> ... -> A10 -> B11 -> C11 -> ... -> B20 -> C21 -> ... -> C30 - BFS 방식은 위와 같이 너비 우선으로 각 경로를 동시에 조금씩 탐색하는 방식입니다. - 따라서 드라마 시청에 비유하자면, 여러 드라마를 번갈아가며 시청하는 순서로 이해할 수 있습니다. ## DFS와 BFS 비교, 쇼핑카드 찾기로 설명 ### DFS(깊이 우선 탐색) - 상황: 슈퍼마켓에서 장바구니가 필요합니다. 아무곳에나 놓여 있을 수 있는데, 장바구니를 찾기 위해선 모든 곳을 찾아봐야 합니다. - 사용: 슈퍼마켓의 한쪽 끝에서 시작해서 한 군데씩 꼼꼼히 찾아보며 진행합니다. 물건이 가득 차 있는 막대한 슈퍼마켓이라고 생각하면 됩니다. 한 곳을 완전히 탐색하고 나서야 다음 구역으로 넘어갑니다. - 장점: 가장 먼저 찾은 장바구니는 그 지역에 가장 가까운 장바구니일 가능성이 큽니다. 모든 곳을 찾아보지 않아도 되는 경우에 효율적입니다. - 단점: 다른 지역에 더 가까운 장바구니가 있을 수 있지만, 현재 탐색 중인 지역이 완전히 끝날 때까지 그것을 찾아내지 못합니다. ### BFS(너비 우선 탐색) - 상황: 같은 슈퍼마켓에서 장바구니가 필요합니다. 그런데 이번엔 최대한 빨리 장바구니를 찾아야 합니다. - 사용: 슈퍼마켓의 중앙에서 시작해서, 가까운 곳부터 조금씩 넓혀가며 찾아봅니다. 주변을 동그랗게 확장해나가며 찾는다고 생각하면 됩니다. - 장점: 시작 지점에서 가장 가까운 장바구니를 빠르게 찾을 수 있습니다. - 단점: 한 지역을 꼼꼼히 탐색하는 데에 비해 시간이 더 많이 걸릴 수 있습니다. ### 결론 - 결국, DFS는 탐색 범위를 좁히고자 할 때, BFS는 최소 거리를 찾고자 할 때 주로 사용됩니다. ## 데크 - DFS는 재귀, BFS 큐 or 링크드리스트를 이용하여 구현합니다. - 파이썬의 collections 모듈에서 제공하는 deque (데크, double-ended queue)는 - 양방향에서 요소를 추가하거나 제거할 수 있는 더 유연한 자료형입니다. - 스택과 큐의 역할을 동시에 수행할 수 있습니다. ### 데크 사용법 ```py # 데크 생성 from collections import deque d = deque() # 오른쪽에 요소 추가 d.append('a') print(d) # deque(['a']) # 왼쪽에 요소 추가 d.appendleft('b') print(d) # deque(['b', 'a']) # 오른쪽에서 요소 제거 element = d.pop() print(element) # 'a' print(d) # deque(['b']) # 왼쪽에서 요소 제거 element = d.popleft() print(element) # 'b' print(d) # deque([]) # 요소의 개수 세기 d = deque(['a', 'b', 'a']) print(d.count('a')) # 2 # 오른쪽에 여러 요소 추가 d.extend(['x', 'y', 'z']) print(d) # deque(['a', 'b', 'a', 'x', 'y', 'z']) # 왼쪽에 여러 요소 추가 d.extendleft(['1', '2', '3']) print(d) # deque(['3', '2', '1', 'a', 'b', 'a', 'x', 'y', 'z']) # 데크의 크기 제한 설정 d = deque(maxlen=3) d.append(1) d.append(2) d.append(3) print(d) # deque([1, 2, 3]) # 크기 제한을 초과하는 요소 추가 (오래된 요소 삭제) d.append(4) print(d) # deque([2, 3, 4]) # 데크의 길이 print(len(d)) # 3 # 데크에 요소가 있는지 확인 if not d: print("Deque is empty") # 데크의 모든 요소 제거 d.clear() print(d) # deque([]) # 요소의 위치 찾기 (index는 0부터 시작) d = deque(['a', 'b', 'c']) print(d.index('b')) # 1 # 특정 위치에 요소 삽입 d.insert(2, 'x') print(d) # deque(['a', 'b', 'x', 'c']) # 요소의 존재 확인 if 'x' in d: print("Element found in deque") # 데크 회전 (양수 = 오른쪽, 음수 = 왼쪽) d = deque(['a', 'b', 'c']) d.rotate(1) print(d) # deque(['c', 'a', 'b']) # 데크 뒤집기 d = deque(['a', 'b', 'c']) d.reverse() print(d) # deque(['c', 'b', 'a']) # 리스트를 데크로 변환 l = ['x', 'y', 'z'] d = deque(l) print(d) # deque(['x', 'y', 'z']) # 데크를 리스트로 변환 l = list(d) print(l) # ['x', 'y', 'z'] ``` ### 실습 ```py # 데크 생성 from collections import deque d = deque() # 오른쪽에 요소 추가 print(d) # deque(['a']) # 왼쪽에 요소 추가 print(d) # deque(['b', 'a']) # 오른쪽에서 요소 제거 print(element) # 'a' print(d) # deque(['b']) # 왼쪽에서 요소 제거 print(element) # 'b' print(d) # deque([]) # 요소의 개수 세기 print(d.count('a')) # 2 # 오른쪽에 여러 요소 추가 print(d) # deque(['a', 'b', 'a', 'x', 'y', 'z']) # 왼쪽에 여러 요소 추가 print(d) # deque(['3', '2', '1', 'a', 'b', 'a', 'x', 'y', 'z']) # 데크의 크기 제한 설정 d = deque(maxlen=3) d.append(1) d.append(2) d.append(3) print(d) # deque([1, 2, 3]) # 크기 제한을 초과하는 요소 추가 (오래된 요소 삭제) print(d) # deque([2, 3, 4]) # 데크의 길이 print(len(d)) # 3 # 데크에 요소가 있는지 확인 if not d: print("Deque is empty") # 데크의 모든 요소 제거 print(d) # deque([]) # 요소의 위치 찾기 (index는 0부터 시작) d = deque(['a', 'b', 'c']) print() # 1 # 특정 위치에 요소 삽입 print(d) # deque(['a', 'b', 'x', 'c']) # 요소의 존재 확인 if 'x' in d: print("Element found in deque") # 데크 회전 (양수 = 오른쪽, 음수 = 왼쪽) d = deque(['a', 'b', 'c']) print(d) # deque(['c', 'a', 'b']) # 데크 뒤집기 d = deque(['a', 'b', 'c']) print(d) # deque(['c', 'b', 'a']) # 리스트를 데크로 변환 l = ['x', 'y', 'z'] print(d) # deque(['x', 'y', 'z']) # 데크를 리스트로 변환 print(l) # ['x', 'y', 'z'] ``` ## 시간 복잡도

- O(1) - 상수 시간: 입력 크기와 관계없이 항상 일정한 시간이 걸립니다. 예를 들어, 배열의 첫 번째 요소를 조회하는 작업입니다. 그래프에서 가장 평평한 선입니다. - O(log n) - 로그 시간: 입력 크기가 증가할수록 시간이 매우 느리게 증가합니다. 주로 이진 탐색 알고리즘에서 나타납니다. - O(n) - 선형 시간: 입력 크기에 비례하여 시간이 증가합니다. 배열의 모든 요소를 하나씩 조회하는 작업이 해당합니다. - O(n log n) - 로그 선형 시간: 비교적 빠른 정렬 알고리즘, 예를 들어 병합 정렬이나 퀵 정렬에서 나타나는 시간 복잡도입니다. - O(n²) - 이차 시간: 입력 크기에 따라 시간이 제곱으로 증가합니다. 주로 중첩된 반복문을 사용하는 알고리즘, 예를 들어 버블 정렬이 여기에 속합니다. - O(2^n) - 지수 시간: 입력 크기가 커질수록 시간이 급격하게 증가합니다. 피보나치 수열을 재귀적으로 계산하는 알고리즘이 이 복잡도에 해당합니다. - O(n!) - 팩토리얼 시간: 매우 빠르게 시간이 증가하는 복잡도로, 외판원 문제와 같은 조합적 최적화 문제에서 볼 수 있습니다. ## 데크 비교 ### 리스트와 데크의 비교, - 리스트는 구조적 변경이 느리지만 데이터 접근이 빠르다. 데크는 구조적 변경이 쉽지만 데이터 접근이 느리다. ### 데크의 각 기능별 리스트와의 속도비교 - 리스트가 데이터 접근 속도가 빠르다는 것을 제외하면 나머지는 데크보다 비슷하거나 느리다. ```py # 데크 생성 - 리스트와 동일한 시간 복잡도를 갖습니다. from collections import deque d = deque() # 오른쪽에 요소 추가 - 리스트의 append와 같은 O(1)의 시간 복잡도를 갖습니다. d.append('a') print(d) # deque(['a']) # 왼쪽에 요소 추가 - 리스트보다 빠릅니다. O(1)의 시간 복잡도를 갖습니다. d.appendleft('b') print(d) # deque(['b', 'a']) # 오른쪽에서 요소 제거 - 리스트의 pop와 같은 O(1)의 시간 복잡도를 갖습니다. element = d.pop() print(element) # 'a' print(d) # deque(['b']) # 왼쪽에서 요소 제거 - 리스트보다 빠릅니다. O(1)의 시간 복잡도를 갖습니다. element = d.popleft() print(element) # 'b' print(d) # deque([]) # 요소의 개수 세기 - 리스트와 동일한 O(n)의 시간 복잡도를 갖습니다. d = deque(['a', 'b', 'a']) print(d.count('a')) # 2 # 오른쪽에 여러 요소 추가 - 리스트의 extend와 동일한 O(k)의 시간 복잡도를 갖습니다. d.extend(['x', 'y', 'z']) print(d) # deque(['a', 'b', 'a', 'x', 'y', 'z']) # 왼쪽에 여러 요소 추가 - 리스트보다 빠릅니다. O(k)의 시간 복잡도를 갖습니다. d.extendleft(['1', '2', '3']) print(d) # deque(['3', '2', '1', 'a', 'b', 'a', 'x', 'y', 'z']) # 데크의 크기 제한 설정 - 리스트에는 이 기능이 없습니다. d = deque(maxlen=3) d.append(1) d.append(2) d.append(3) print(d) # deque([1, 2, 3]) # 크기 제한을 초과하는 요소 추가 (오래된 요소 삭제) - 리스트에는 이 기능이 없습니다. d.append(4) print(d) # deque([2, 3, 4]) # 데크의 길이 - 리스트와 동일한 O(1)의 시간 복잡도를 갖습니다. print(len(d)) # 3 # 데크에 요소가 있는지 확인 - 리스트와 동일한 시간 복잡도를 갖습니다. if not d: print("Deque is empty") # 데크의 모든 요소 제거 - 리스트의 clear와 동일한 O(1)의 시간 복잡도를 갖습니다. d.clear() print(d) # deque([]) # 요소의 위치 찾기 (index는 0부터 시작) - 리스트와 동일한 O(n)의 시간 복잡도를 갖습니다. d = deque(['a', 'b', 'c']) print(d.index('b')) # 1 # 특정 위치에 요소 삽입 - 리스트보다 느립니다. O(n)의 시간 복잡도를 갖습니다. d.insert(2, 'x') print(d) # deque(['a', 'b', 'x', 'c']) # 요소의 존재 확인 - 리스트와 동일한 O(n)의 시간 복잡도를 갖습니다. if 'x' in d: print("Element found in deque") # 데크 회전 (양수 = 오른쪽, 음수 = 왼쪽) - 리스트에는 이 기능이 없습니다. d = deque(['a', 'b', 'c']) d.rotate(1) print(d) # deque(['c', 'a', 'b']) # 데크 뒤집기 - 리스트의 reverse와 동일한 O(n)의 시간 복잡도를 갖습니다. d = deque(['a', 'b', 'c']) d.reverse() print(d) # deque(['c', 'b', 'a']) # 리스트를 데크로 변환 - 리스트와 동일한 시간 복잡도를 갖습니다. l = ['x', 'y', 'z'] d = deque(l) print(d) # deque(['x', 'y', 'z']) # 데크를 리스트로 변환 - 리스트와 동일한 시간 복잡도를 갖습니다. l = list(d) print(l) # ['x', 'y', 'z'] ``` ## 데크를 스택처럼 사용하기, 큐처럼 사용하기 ### 데크로 스택 구현 ```py from collections import deque stack = deque() # 스택에 값 추가 stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # 스택에서 값 제거 (LIFO: Last In First Out) print('\nElements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('\nStack after elements are popped:') print(stack) ``` ### 데크로 큐 구현 ```py from collections import deque queue = deque() # 큐에 값 추가 queue.append('a') queue.append('b') queue.append('c') print('Initial queue:') print(queue) # 큐에서 값 제거 (FIFO: First In First Out) print('\nElements dequeued from queue:') print(queue.popleft()) print(queue.popleft()) print(queue.popleft()) print('\nQueue after elements are dequeued:') print(queue) ``` ## 집합을 나타내는 자료구조 Set, Set 안의 요소는 순서가 없고, 중복도 허용되지 않는다. ```py # Set 생성하기 # 빈 set 생성 s = set() print(s) # 출력: set() # 값이 있는 set 생성 s = {1, 2, 3} print(s) # 출력: {1, 2, 3} # Set에 값 추가하기 s.add(4) print(s) # 출력: {1, 2, 3, 4} # Set에서 값 제거하기 s.remove(2) print(s) # 출력: {1, 3, 4} # Set에서 임의의 원소 제거하기 s.pop() print(s) # 출력: {3, 4} # Set의 길이 구하기 print(len(s)) # 출력: 2 # Set에 특정 값이 있는지 확인하기 print(1 in s) # 출력: False print(4 in s) # 출력: True # s == {3, 4} # Set의 합집합, 교집합, 차집합, 대칭차집합 구하기 s1 = {1, 2, 3} print(s1 | s) # 출력: {1, 2, 3, 4} print(s1 & s) # 출력: {3} print(s1 - s) # 출력: {1, 2} print(s1 ^ s) # 출력: {1, 2, 4} # Set의 모든 원소 제거하기 s.clear() print(s) # 출력: set() # Set에서 특정 값 제거하기 (없는 값 제거 시 에러 발생하지 않음) s1.discard(2) print(s1) # 출력: {1, 3} s1.discard(4) print(s1) # 출력: {1, 3} # 두 Set이 같은지 확인하기 s2 = {1, 3} print(s1 == s2) # 출력: True # 하나의 Set이 다른 Set의 부분집합인지 확인하기 s1 = {1, 2} print(s1.issubset(s2)) # 출력: False # 하나의 Set이 다른 Set의 상위집합인지 확인하기 s2 = {1, 2, 3} print(s2.issuperset(s1)) # 출력: True # 두 Set이 서로소인지 확인하기 (공통 원소가 없는지) s3 = {3, 4} print(s1.isdisjoint(s3)) # 출력: True # Set을 리스트로 변환하기 l = list(s1) print(l) # 출력: [1, 2] # 리스트를 Set으로 변환하기 (중복 원소 제거) l = [1, 2, 2, 3, 3, 3] s = set(l) print(s) # 출력: {1, 2, 3} # Set 복사하기 s4 = s.copy() print(s4) # 출력: {1, 2, 3} # Set comprehension 사용하기 s = {i for i in range(10) if i % 2 == 0} print(s) # 출력: {0, 2, 4, 6, 8} # 여러 set의 합집합, 교집합 구하기 s1 = {1, 2, 3} s2 = {3, 4, 5} s3 = {5, 6, 7} print(s1 | s2 | s3) # 출력: {1, 2, 3, 4, 5, 6, 7} s1 = {1, 2, 3, 4} s2 = {2, 3, 4, 5} s3 = {3, 4, 5, 6} print(s1 & s2 & s3) # 출력: {3, 4} # set의 값 업데이트하기 s = {1, 2, 3} s.update({4, 5, 6}) print(s) # 출력: {1, 2, 3, 4, 5, 6} # set에서 여러 값 제거하기 s.difference_update({2, 3}) print(s) # 출력: {1, 4, 5, 6} # set의 원소를 정렬하기 s = {3, 1, 2, 5, 4} sorted_s = sorted(s) print(sorted_s) # 출력: [1, 2, 3, 4, 5] # 문자열을 set으로 변환하기 str = "hello" s = set(str) print(s) # 출력: {'h', 'e', 'l', 'o'} ``` ## 일반 그래프보다 쉬운 트리형태의 그래프를 BFS로 탐색 ![img](https://i.imgur.com/5d9sLTJ.png) ### 문제 ```py from collections import deque def bfs(graph, root): '''구현해주세요''' graph = { 1: [2, 3, 8], 2: [7], 3: [4], 4: [5], 5: [], 6: [], 7: [6], 8: [] } bfs(graph, 1) # 출력 # 1 2 3 8 7 4 6 5 ``` ### 정답 ```py from collections import deque def bfs(graph, root): # 빈 큐를 생성하고, 루트 노드를 큐에 추가합니다. queue = deque([root]) while queue: # 큐의 첫 번째 노드를 꺼냅니다. node = queue.popleft() # 현재 노드를 출력합니다. print(node, end=' ') # 현재 노드의 인접 노드들을 for nei_node in graph[node]: # 큐에 추가합니다. queue.append(nei_node) graph = { 1: [2, 3, 8], 2: [7], 3: [4], 4: [5], 5: [], 6: [], 7: [6], 8: [] } bfs(graph, 1) ``` ## 일반적인 그래프에 적용할 수 있는 BFS 탐색에는 꼭 이미 방문한 노드에 대한 스킵이 있어야 한다. - ![img](https://i.imgur.com/5KC9xMf.png) ### 문제 ```py from collections import deque def bfs(graph, root): '''구현해주세요''' graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } bfs(graph, 1) # 출력 # 1 2 3 4 ``` ### 정답 ```py from collections import deque def bfs(graph, root): # 빈 큐를 생성하고, 루트 노드를 큐에 추가합니다. queue = deque([root]) visited = set() while queue: # 큐의 첫 번째 노드를 꺼냅니다. node = queue.popleft() if node in visited: continue visited.add(node) # 현재 노드를 출력합니다. print(node, end=' ') # 현재 노드의 인접 노드들을 for nei_node in graph[node]: # 큐에 추가합니다. queue.append(nei_node) graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } bfs(graph, 1) # 출력 # 1 2 3 4 ``` ## 실습 문제 - [타켓 넘버](https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3) ### DFS 해설 코드 ```py def dfs(numbers, target, idx, current_sum): # 모든 숫자를 다 사용했을 때 if idx == len(numbers): # 현재까지의 합이 타겟과 같으면 1을 반환 if current_sum == target: return 1 else: return 0 # 현재 숫자를 더하거나 빼는 두 가지 경우를 재귀적으로 탐색 count = 0 count += dfs(numbers, target, idx + 1, current_sum + numbers[idx]) count += dfs(numbers, target, idx + 1, current_sum - numbers[idx]) return count def solution(numbers, target): return dfs(numbers, target, 0, 0) # 예시 실행 numbers = [1, 1, 1, 1, 1] target = 3 print(solution(numbers, target)) # 출력: 5 ``` ### BFS 해설 코드 ```py from collections import deque def solution(numbers, target): # 큐 초기화: (현재 합, 인덱스) 형태로 큐에 넣음 queue = deque([(0, 0)]) # 초기 합은 0이고 인덱스 0부터 시작 count = 0 # 큐가 빌 때까지 반복 while queue: current_sum, idx = queue.popleft() # 모든 숫자를 다 사용했을 때 if idx == len(numbers): # 현재까지의 합이 타겟과 같으면 카운트 증가 if current_sum == target: count += 1 else: # 현재 인덱스의 숫자를 더한 경우와 뺀 경우를 큐에 추가 queue.append((current_sum + numbers[idx], idx + 1)) queue.append((current_sum - numbers[idx], idx + 1)) return count # 예시 실행 numbers = [1, 1, 1, 1, 1] target = 3 print(solution(numbers, target)) # 출력: 5 ``` ## 클래스와 객체 ```py # 간단한 클래스 생성 class MyClass: x = 5 p1 = MyClass() print(p1.x) # 출력: 5 del MyClass, p1 # init 메소드를 이용한 초기화 class Person: def __init__(self, name, age): self.name = name self.age = age p1 = Person("John", 36) print(p1.name) # 출력: John print(p1.age) # 출력: 36 del Person, p1 # 객체 메소드 class Person: def __init__(self, name, age): self.name = name self.age = age def myfunc(self): print("Hello my name is " + self.name) p1 = Person("John", 36) p1.myfunc() # 출력: Hello my name is John del Person, p1 # self 매개변수 class Person: def __init__(mysillyobject, name, age): mysillyobject.name = name mysillyobject.age = age def myfunc(abc): print("Hello my name is " + abc.name) p1 = Person("John", 36) p1.myfunc() # 출력: Hello my name is John del Person, p1 # 객체 속성 변경 class Person: def __init__(self, name, age): self.name = name self.age = age p1 = Person("John", 36) p1.age = 40 print(p1.age) # 출력: 40 del Person, p1 # 상속 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): pass x = Student("Mike", "Olsen") x.printname() # 출력: Mike Olsen del Person, Student, x # 상속 - 자식 클래스의 init 함수 추가 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): def __init__(self, fname, lname): super().__init__(fname, lname) x = Student("Mike", "Olsen") x.printname() # 출력: Mike Olsen del Person, Student, x # 상속 - 속성 추가 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): def __init__(self, fname, lname): super().__init__(fname, lname) self.graduationyear = 2023 x = Student("Mike", "Olsen") print(x.graduationyear) # 출력: 2023 del Person, Student, x # 상속 - 메소드 추가 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): def __init__(self, fname, lname, year): super().__init__(fname, lname) self.graduationyear = year def welcome(self): print("Welcome", self.firstname, self.lastname, "to the class of", self.graduationyear) x = Student("Mike", "Olsen", 2023) x.welcome() # 출력: Welcome Mike Olsen to the class of 2023 del Person, Student, x ``` ## 클래스와 객체 관련 문제 ### 문제 1 Person.introduce ```py class Person(): '''구현해주세요''' p1 = Person("Paul", 22) p2 = Person("Alice", 23) p1.introduce() # 출력 : My name is Paul, I'm 22 years old. p2.introduce() # 출력 : My name is Alice, I'm 23 years old. ``` #### 정답 ```py class Person(): def __init__(self, name, age): self.name = name self.age = age def introduce(self): print("My name is {}, I'm {} years old.".format(self.name, self.age)) p1 = Person("Paul", 22) p2 = Person("Alice", 23) p1.introduce() # 출력 : My name is Paul, I'm 22 years old. p2.introduce() # 출력 : My name is Alice, I'm 23 years old. ``` ### 문제 2 Car.show_info ```py class Car: '''구현해주세요.''' my_car = Car('Toyota', '2020') my_car.show_info() # 출력 # Brand: Toyota # Year: 2020 ``` #### 정답 ```py class Car: def __init__(self, brand, year): self.brand = brand self.year = year def show_info(self): print("Brand: {}".format(self.brand)) print("Year: {}".format(self.year)) my_car = Car('Toyota', '2020') my_car.show_info() # 출력 # Brand: Toyota # Year: 2020 ``` ### 문제 3 Dog 생성자에서 Animal 생성자 호출 ```py class Animal: def __init__(self, name, age): self.name = name self.age = age class Dog(Animal): '''구현해주세요.''' my_dog = Dog('Max', 2, 'Bulldog') print(my_dog.name) # 출력: # Max print(my_dog.age) # 출력: # 2 print(my_dog.breed) # 출력: # Bulldog ``` #### 정답 ```py class Animal: def __init__(self, name, age): self.name = name self.age = age class Dog(Animal): def __init__(self, name, age, breed): super().__init__(name, age) self.breed = breed my_dog = Dog('Max', 2, 'Bulldog') print(my_dog.name) # 출력: # Max print(my_dog.age) # 출력: # 2 print(my_dog.breed) # 출력: # Bulldog ``` ### 문제 4 Rectangle 의 너비 ```py class Rectangle: '''구현해주세요.''' my_rectangle = Rectangle(5, 7) print(my_rectangle.calculate_area()) # 사각형의 너비를 반환 # 출력 : 35 ``` #### 정답 ```py class Rectangle: def __init__(self, width, height): self.width = width self.height = height def calculate_area(self): return self.width * self.height my_rectangle = Rectangle(5, 7) print(my_rectangle.calculate_area()) # 사각형의 너비를 반환 ``` ## 단순한 정렬 ```py # 기본적인 리스트 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] nums.sort() print(nums) # 출력: [1, 1, 2, 3, 4, 5, 6, 9] del nums # sorted 함수를 이용한 리스트 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] sorted_nums = sorted(nums) print(sorted_nums) # 출력: [1, 1, 2, 3, 4, 5, 6, 9] del nums, sorted_nums # 리스트 뒤집기 nums = [1, 2, 3, 4, 5] nums.reverse() print(nums) # 출력: [5, 4, 3, 2, 1] del nums # sort()로 리스트 내림차순 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] nums.sort(reverse=True) print(nums) # 출력: [9, 6, 5, 4, 3, 2, 1, 1] del nums # sorted()로 리스트 내림차순 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] sorted_nums = sorted(nums, reverse=True) print(sorted_nums) # 출력: [9, 6, 5, 4, 3, 2, 1, 1] del nums, sorted_nums # 문자열 리스트를 알파벳 순서로 정렬 strs = ['banana', 'apple', 'kiwi', 'orange'] strs.sort() print(strs) # 출력: ['apple', 'banana', 'kiwi', 'orange'] del strs # 문자열 리스트를 알파벳 역순으로 정렬 strs = ['banana', 'apple', 'kiwi', 'orange'] strs.sort(reverse=True) print(strs) # 출력: ['orange', 'kiwi', 'banana', 'apple'] del strs # 튜플을 원소로 갖는 리스트 정렬 tuples = [(1, 'one'), (3, 'three'), (2, 'two')] tuples.sort() print(tuples) # 출력: [(1, 'one'), (2, 'two'), (3, 'three')] del tuples # 튜플을 원소로 갖는 리스트를 두 번째 요소를 기준으로 정렬 tuples = [(1, 'one'), (3, 'three'), (2, 'two')] tuples.sort(key=lambda x: x[1]) print(tuples) # 출력: [(1, 'one'), (3, 'three'), (2, 'two')] del tuples # 딕셔너리를 값에 따라 정렬 dicts = {'three': 3, 'one': 1, 'two': 2} sorted_dicts = sorted(dicts.items(), key=lambda x: x[1]) print(sorted_dicts) # 출력: [('one', 1), ('two', 2), ('three', 3)] del dicts, sorted_dicts # 딕셔너리를 키에 따라 정렬 dicts = {'three': 3, 'one': 1, 'two': 2} sorted_dicts = sorted(dicts.items(), key=lambda x: x[0]) print(sorted_dicts) # 출력: [('one', 1), ('three', 3), ('two', 2)] del dicts, sorted_dicts # 복합 리스트 정렬 complex_list = [3, 1, 4, [5, 6, 7], 2] complex_list.sort(key=lambda x: x if isinstance(x, int) else x[0]) print(complex_list) # 출력: [1, 2, 3, 4, [5, 6, 7]] del complex_list # 문자열 리스트를 길이에 따라 정렬 strs = ['aaaa', 'bb', 'ccc', 'd'] strs.sort(key=len) print(strs) # 출력: ['d', 'bb', 'ccc', 'aaaa'] del strs # 중복 제거 후 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6, 2, 6] nums = list(set(nums)) nums.sort() print(nums) # 출력: [1, 2, 3, 4, 5, 6, 9] del nums # sorted() 함수로 문자열 정렬 s = 'apple' sorted_s = ''.join(sorted(s)) print(sorted_s) # 출력: 'aelpp' del s, sorted_s # 중첩 리스트 정렬 nested_list = [[3, 2, 1], [6, 5, 4], [9, 8, 7]] nested_list.sort(key=lambda x: x[1]) print(nested_list) # 출력: [[3, 2, 1], [6, 5, 4], [9, 8, 7]] del nested_list # 중첩 리스트 내부 정렬 nested_list = [[3, 2, 1], [6, 5, 4], [9, 8, 7]] for sublist in nested_list: sublist.sort() print(nested_list) # 출력: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] del nested_list # 중첩 리스트 내부와 외부 동시 정렬 nested_list = [[3, 2, 1], [6, 5, 4], [9, 8, 7]] for sublist in nested_list: sublist.sort() nested_list.sort(key=lambda x: x[0]) print(nested_list) # 출력: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] del nested_list # 클래스 인스턴스 정렬 class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('John', 20), Person('Jane', 19), Person('Adam', 21)] people.sort(key=lambda x: x.age) for person in people: print(person) del Person, people ``` ## 문제 ### 문제 1 숫자 리스트 정렬 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py list1 = [2, 7, 9, 2, 4, 3, 8, 6, 1] ``` #### 작업 - 오름차순으로 정렬하고 결과를 출력하세요. - 내림차순으로 정렬하고 결과를 출력하세요. - 중복된 숫자를 제거한 후 오름차순으로 정렬하고 결과를 출력하세요. #### 정답 ```py list1 = [2, 7, 9, 2, 4, 3, 8, 6, 1] # 오름차순으로 정렬하고 결과를 출력하세요. list1.sort() print(list1) # 내림차순으로 정렬하고 결과를 출력하세요. list1.sort(reverse=True) print(list1) # 중복된 숫자를 제거한 후 오름차순으로 정렬하고 결과를 출력하세요. list1 = sorted(set(list1)) print(list1) ``` ### 문제 2 튜플 정렬 - 다음과 같은 튜플 리스트를 활용하여 아래의 작업을 수행해주세요. ```py tuple_list = [ ('apple', 3), ('banana', 2), ('cherry', 1), ('apple', 4), ('banana', 1) ] ``` #### 작업 - 첫 번째 요소 (과일 이름)를 기준으로 오름차순으로 정렬하고 결과를 출력하세요. - 두 번째 요소 (숫자)를 기준으로 오름차순으로 정렬하고 결과를 출력하세요. #### 정답 ```py tuple_list = [ ('apple', 3), ('banana', 2), ('cherry', 1), ('apple', 4), ('banana', 1) ] # 첫 번째 요소 (과일 이름)를 기준으로 # 오름차순으로 정렬하고 결과를 출력하세요. tuple_list.sort() print(tuple_list) # 두 번째 요소 (숫자)를 기준으로 # 오름차순으로 정렬하고 결과를 출력하세요. tuple_list.sort(key=lambda row: row[1]) print(tuple_list) ``` ### 문제 3 문자열 리스트 정렬 - 다음과 같은 문자열 리스트를 활용하여 아래의 작업을 수행해주세요. ``` str_list = ['Python', 'Java', 'C', 'JavaScript', 'Ruby', 'Go'] ``` #### 작업 - 문자열의 길이를 기준으로 오름차순으로 정렬하고 결과를 출력하세요. - 문자열을 알파벳 역순으로 정렬하고 결과를 출력하세요. #### 정답 ```py str_list = ['Python', 'Java', 'C', 'JavaScript', 'Ruby', 'Go'] # 문자열의 길이를 기준으로 오름차순으로 # 정렬하고 결과를 출력하세요. str_list.sort(key=len) print(str_list) # 문자열을 알파벳 역순으로 # 정렬하고 결과를 출력하세요. str_list.sort(reverse=True) print(str_list) ``` ## 정렬 2부, 정렬조건이 2개 이상인 경우 ```py # 숫자 리스트를 절대값 기준으로 정렬하는 예제입니다. nums = [3, -1, 4, -1, -5, 9, 2, -6] sorted_nums = sorted(nums, key=abs) print(sorted_nums) # 출력: [-1, -1, 2, 3, 4, -5, -6, 9] del nums, sorted_nums # 이름과 나이를 가진 사람 객체 리스트를 나이 순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 30), Person('Bob', 30), Person('Charlie', 25), Person('Alice', 20)] people.sort(key=lambda person: person.age) for person in people: print(person.name, person.age) del Person, people # 나이가 같으면 이름으로 추가 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('David', 25), Person('Alice', 25)] people.sort(key=lambda person: (person.age, person.name)) for person in people: print(person.name, person.age) del Person, people # 이름이 같으면 나이가 큰 순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('Alice', 25)] people.sort(key=lambda person: (person.name, -person.age)) for person in people: print(person.name, person.age) del Person, people # 나이로 먼저 정렬하고, 나이가 같으면 이름의 알파벳 역순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('David', 25), Person('Alice', 25)] people.sort(key=lambda person: person.name, reverse=True) people.sort(key=lambda person: person.age) for person in people: print(person.name, person.age) del Person, people # 나이로 먼저 정렬하고, 나이가 같으면 이름의 알파벳 역순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age def __lt__(self, other): if self.age != other.age: return self.age < other.age return self.name > other.name # 이름이 같은 경우, 알파벳 역순으로 정렬합니다. people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('David', 25), Person('Alice', 25)] people.sort() for person in people: print(person.name, person.age) del Person, people ``` ## 정렬 2부 문제 ### 문제 1 절대값 기준 정렬 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py nums = [7, -9, -2, 4, 3, -8, 6, 1] ``` #### 작업 - 절대값 기준으로 오름차순 정렬하고 결과를 출력하세요. - 절대값 기준으로 내림차순 정렬하고 결과를 출력하세요. #### 정답 ```py # 주어진 리스트 nums = [7, -9, -2, 4, 3, -8, 6, 1] # 절대값 기준으로 오름차순 정렬 ascending_sorted_nums = sorted(nums, key=abs) # 절대값 기준으로 내림차순 정렬 descending_sorted_nums = sorted(nums, key=abs, reverse=True) print("오름차순 정렬: ", ascending_sorted_nums) print("내림차순 정렬: ", descending_sorted_nums) ``` ### 문제 2 객체정렬 - 다음과 같은 'Person' 객체 리스트를 활용하여 아래의 작업을 수행해주세요. ```py class Person: def __init__(self, name, age): self.name = name self.age = age people = [ Person('Alice', 30), Person('Bob', 35), Person('Charlie', 25), Person('Alice', 25), Person('David', 30) ] ``` #### 작업 - 이름으로 오름차순 정렬하고 결과를 출력하세요. - 나이로 오름차순 정렬하고 결과를 출력하세요. - 이름으로 오름차순 정렬 후, 같은 이름일 경우 나이가 더 많은 순으로 정렬하고 결과를 출력하세요. - 나이로 오름차순 정렬 후, 같은 나이일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. #### 정답 ```py class Person: def __init__(self, name, age): self.name = name self.age = age def __repr__(self): return f"Person(name='{self.name}', age={self.age})" people = [ Person('Alice', 30), Person('Bob', 35), Person('Charlie', 25), Person('Alice', 25), Person('David', 30) ] # 문제 : 이름으로 오름차순 정렬하고 결과를 출력하세요. people1 = sorted(people, key = lambda person: person.name) print(people1) # 문제 : 나이로 오름차순 정렬하고 결과를 출력하세요. people2 = sorted(people, key = lambda person: person.age) print(people2) # 문제 : 이름으로 오름차순 정렬 후, 같은 이름일 경우 나이가 더 많은 순으로 정렬하고 결과를 출력하세요. people3 = sorted(people, key = lambda person: (person.name, -person.age)) print(people3) # 문제 : 나이로 오름차순 정렬 후, 같은 나이일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. ## 먼저 이름을 기준으로 역순정렬을 한다. people4 = sorted(people, key = lambda person: person.name, reverse = True) ## 그 이후에 나이로 정렬하면, 나이가 같은 것들은 자연스럽게 원래의 순서(이름 역순)을 유지하게 된다. people4.sort(key = lambda person: person.age) print(people4) ``` #### 추가설명, 나이로 오름차순 정렬 후, 같은 나이일 경우 이름을 알파벳 역순으로 정렬하려면 2번 정렬 해야 함 - 2차 정렬을 할 때 나이가 같은 사람의 경우에는 순서를 바꾸지 않는다. 즉 1차의 정렬결과가 그들 사이에서 유지된다. ``` -- 원본 리스트 -- 순서 1 : [홍길동, 24살] 순서 2 : [홍길동, 25살] 순서 3 : [홍길순, 25살] -- 1차 정렬(이름 내림차순) -- 순서 1 : [홍길순, 25살] 순서 2 : [홍길동, 25살] 순서 3 : [홍길동, 24살] -- 2차 정렬(나이 오름차순) -- 순서 1 : [홍길동, 24살] 순서 2 : [홍길순, 25살] 순서 3 : [홍길동, 25살] ``` ### 문제 3 객체정렬, lt 메서드 오버라이드 - 다음과 같은 'Student' 객체 리스트를 활용하여 아래의 작업을 수행해주세요. ```py class Student: def __init__(self, name, grade, score): self.name = name self.grade = grade self.score = score students = [ Student('Alice', 3, 85), Student('Bob', 2, 90), Student('Charlie', 2, 88), Student('Alice', 1, 95), Student('Paul', 3, 78), Student('David', 3, 78) ] ``` #### 작업 - 학년(grade)으로 오름차순 정렬 후, 같은 학년일 경우 점수(score)가 높은 순으로 정렬하고 결과를 출력하세요. - 점수(score)로 내림차순 정렬 후, 같은 점수일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. 이름까지도 같은 학생이 존재한다면 학년으로 정렬해주세요. #### 정답 ```py # 학년(grade)으로 오름차순 정렬 후, 같은 학년일 경우 점수(score)가 높은 순으로 정렬하고 결과를 출력하세요. class Student: def __init__(self, name, grade, score): self.name = name self.grade = grade self.score = score def __repr__(self): return f"Student(name='{self.name}, grade='{self.grade}', score='{self.score}')" def __lt__(self, other): if self.grade != other.grade: return self.grade < other.grade else: return self.score > other.score students = [ Student('Alice', 3, 85), Student('Bob', 2, 90), Student('Charlie', 2, 88), Student('Alice', 1, 95), Student('Paul', 3, 78), Student('David', 3, 78) ] students.sort() print(students) del Student, students # 점수(score)로 내림차순 정렬 후, 같은 점수일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. # 이름까지도 같은 학생이 존재한다면 학년으로 정렬해주세요. class Student: def __init__(self, name, grade, score): self.name = name self.grade = grade self.score = score def __repr__(self): return f"Student(name='{self.name}, grade='{self.grade}', score='{self.score}')" def __lt__(self, other): if self.score != other.score: return self.score < other.score elif self.name != other.name: return self.name > other.name else: return self.grade < self.grade students = [ Student('Alice', 3, 85), Student('Bob', 2, 90), Student('Charlie', 2, 88), Student('Alice', 1, 95), Student('Paul', 3, 78), Student('David', 3, 78) ] students.sort() print(students) del Student, students ``` ## 다익스트라, 그리디(탐욕법), DP ## 힙큐 개념 ```py # Python에서 heap은 `heapq` 모듈을 통해 사용할 수 있습니다. # 힙은 우선순위 큐를 구현하는 좋은 방법입니다. # 힙은 모든 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리입니다. import heapq # 기본적인 heapq 사용 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] for num in nums: heapq.heappush(heap, num) # 힙에 원소 추가 print(heap) del nums, heap # heapq에서 가장 작은 원소 추출 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] for num in nums: heapq.heappush(heap, num) print(heapq.heappop(heap)) # 출력: 1 del nums, heap # 리스트를 힙으로 변환 nums = [3, 1, 4, 1, 5, 9, 2, 6] heapq.heapify(nums) print(nums) del nums # 힙에서 가장 큰 원소 추출 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] for num in nums: heapq.heappush(heap, -num) print(-heapq.heappop(heap)) # 출력: 9 del nums, heap # 힙을 이용한 K번째 최대 원소 찾기 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] k = 3 for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) print(heapq.heappop(heap)) # 출력: 3 (세 번째로 큰 원소) del nums, heap, k # heapq nlargest, nsmallest nums = [3, 1, 4, 1, 5, 9, 2, 6] print(heapq.nlargest(3, nums)) # 출력: [9, 6, 5] print(heapq.nsmallest(3, nums)) # 출력: [1, 1, 2] del nums # 객체를 가진 heapq class Person: def __init__(self, name, age): self.name = name self.age = age def __lt__(self, other): return self.age < other.age people = [Person('John', 20), Person('Jane', 19), Person('Adam', 21)] heap = [] for person in people: heapq.heappush(heap, person) while heap: person = heapq.heappop(heap) print(person.name, person.age) # 출력: Jane 19, John 20, Adam 21 del Person, people, heap ``` ## 실습문제 ### 문제 1 최소값, 최대값 추출 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py nums = [15, 22, 7, -8, 33, 12, 42, -3, 18, 29, -11] ``` #### 작업 - heapq 모듈을 활용하여 nums 리스트를 최소 힙으로 변환하고 결과를 출력하세요. - 최소 힙에서 가장 작은 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. - 변환한 힙에서 가장 큰 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. #### 정답 ```py import heapq ### 문제 1 # 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. nums = [15, 22, 7, -8, 33, 12, 42, -3, 18, 29, -11] #### 작업 # heapq 모듈을 활용하여 nums 리스트를 최소 힙으로 변환하고 결과를 출력하세요. heapq.heapify(nums) print(nums) # 최소 힙에서 가장 작은 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. smallest = heapq.heappop(nums) print(smallest) # 변환한 힙에서 가장 큰 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. ## 부호반전 for i in range(len(nums)): nums[i] = -nums[i] ## 다시 정렬 heapq.heapify(nums) ## 최대값 가져오기(최소값을 가져오고 부호반전) largest = -heapq.heappop(nums) print(largest) ``` ### 문제 2 최소값, 최대값 여러개 추출 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py nums = [3, 2, 5, 1, 8, 7, 4, 9, 6] ``` #### 작업 - heapq 모듈을 활용하여 nums 리스트에서 4번째로 큰 원소를 찾으세요. - heapq의 nlargest 함수와 nsmallest 함수를 활용하여 리스트에서 가장 큰 3개의 원소와 가장 작은 3개의 원소를 찾으세요. #### 정답 ```py import heapq nums = [3, 2, 5, 1, 8, 7, 4, 9, 6] k = 4 # heapq 모듈을 활용하여 nums 리스트에서 4번째로 큰 원소를 찾으세요. print(heapq.nlargest(k, nums)[-1]) # heapq의 nlargest 함수와 nsmallest 함수를 활용하여 리스트에서 가장 큰 3개의 원소와 가장 작은 3개의 원소를 찾으세요. print(heapq.nlargest(3, nums)) print(heapq.nsmallest(3, nums)) ``` ### 문제 3 객체 다루기 - 다음과 같은 'Car' 객체 리스트를 활용하여 아래의 작업을 수행해주세요. ```py class Car: def __init__(self, model, speed): self.model = model self.speed = speed def __lt__(self, other): return self.speed < other.speed cars = [Car('Sedan', 120), Car('SUV', 110), Car('Sports', 160), Car('Truck', 80), Car('Convertible', 140)] ``` #### 작업 - heapq 모듈을 활용하여 Car 객체 리스트를 속도(speed)를 기준으로 하는 최소 힙으로 변환하세요. - 생성한 힙에서 가장 빠른 차를 추출하고 그 후의 힙 상태를 출력하세요. #### 정답 ```py import heapq class Car: def __init__(self, model, speed): self.model = model self.speed = speed def __repr__(self): return f"Car(model='{self.model}', speed={self.speed})" def __lt__(self, other): # 이 부분의 괄호를 < 에서 > 로 바꿔야 합니다. return self.speed > other.speed cars = [Car('Sedan', 120), Car('SUV', 110), Car('Sports', 160), Car('Truck', 80), Car('Convertible', 140)] # heapq 모듈을 활용하여 Car 객체 리스트를 속도(speed)를 기준으로 하는 최소 힙으로 변환하세요. heapq.heapify(cars) # 생성한 힙에서 가장 빠른 차를 추출하고 그 후의 힙 상태를 출력하세요. print(heapq.heappop(cars)) ``` ## 최적경로 구하는 다익스트라 개념과 구현 ![img](https://i.imgur.com/Ywz4hwp.png) ```py import heapq def dijkstra(graph, start): # 1. 특정 지점까지의 거리를 무한대로 설정한다. distances = {node: float('inf') for node in graph} # 2. 시작점을 정한다. distances[start] = 0 # 3. 시작점을 큐에 넣는다. queue = [(distances[start], start)] while queue: # 4. 큐에서 가장 가까운 노드를 꺼낸다. current_distance, current_node = heapq.heappop(queue) # 5. 해당 노드를 방문했는지 확인한다. if current_distance > distances[current_node]: continue for nei_distance, nei_node in graph[current_node]: # 6. 현재 노드를 거쳐서 이웃 노드로 가는 거리를 계산한다. distance = current_distance + nei_distance # 7. 계산한 거리가 기존의 이웃 노드까지의 거리보다 작다면 if distance < distances[nei_node]: # 거리 값을 갱신하고 distances[nei_node] = distance # 우선순위 큐에 이웃 노드와 갱신된 거리를 넣는다. heapq.heappush(queue, (distance, nei_node)) return distances graph = { '서울': [(85, '천안'), (160, '대전'), (330, '부산')], '천안': [(85, '서울'), (70, '대전'), (305, '부산')], '대전': [(70, '천안'), (160, '서울'), (145, '대구')], '대구': [(145, '대전'), (100, '부산')], '부산': [(100, '대구'), (330, '서울'), (305, '천안')] } start_city = "서울" shortest_distances = dijkstra(graph, start_city) print("출발 도시 :", start_city) for city, distance in shortest_distances.items(): print(city + "까지 최단 거리 :", distance) ``` ### 초기 설정 - 모든 도시까지의 거리는 무한대(`inf`)로 설정됩니다. 시작 도시인 '서울'까지의 거리는 0입니다. ```python distances = {'서울': 0, '천안': inf, '대전': inf, '대구': inf, '부산': inf} queue = [(0, '서울')] ``` ### 첫 번째 업데이트 - '서울'과 직접 연결된 도시들('천안', '대전', '부산')까지의 거리가 각 도시까지의 직접 거리로 업데이트됩니다. ```python distances = {'서울': 0, '천안': 85, '대전': 160, '대구': inf, '부산': 330} queue = [(85, '천안'), (160, '대전'), (330, '부산')] ``` ### 두 번째 업데이트 - '서울'을 거쳐 '천안'으로 가는 경로를 통해 '대전'까지의 거리가 업데이트됩니다. - '서울'에서 '천안'으로 가는 거리(85)와 '천안'에서 '대전'으로 가는 거리(70)를 합하면 155이며, - 이는 이전에 계산된 '서울'에서 '대전'까지의 거리(160)보다 짧습니다. ```python distances = {'서울': 0, '천안': 85, '대전': 155, '대구': inf, '부산': 330} queue = [(155, '대전'), (160, '대전'), (330, '부산')] ``` ## 경주마 같은 탐욕법 개념 - 탐욕법 (greedy algorithm)은 최적화 문제를 해결하는 알고리즘 중 하나입니다. - 이는 매 순간 최적의 선택을 하도록 하여 전체적으로 보았을 때 최적의 결과를 도출하려는 방법입니다. - 탐욕법은 다음과 같은 특징을 가집니다: - 각 단계에서 지역적으로 최적의 선택을 합니다. - 이 선택은 그 선택이 있을 때 당장은 최선의 해결책으로 보입니다. - 이러한 선택들을 통해 최종적으로 전역적인 해결책을 찾아냅니다. - 하지만 탐욕법이 항상 최적의 해결책을 제공하는 것은 아닙니다. - 일부 문제에 대해선 탐욕적인 선택이 최적의 해결책으로 이어지지만, - 그렇지 않은 문제들도 있습니다. 이러한 경우 다른 알고리즘을 사용해야 합니다. ### 문제 1 최소한의 동전개수로 교환하는 방법 - 동전들이 있습니다. 각 동전의 금액은 각각 500원, 100원, 50원, 10원입니다. 주어진 금액을 최소한의 동전 개수로 교환하는 방법을 찾아주세요. #### 작업 - 주어진 금액을 입력 받아 최소한의 동전 개수로 교환하고 결과를 출력하세요. #### 코드 ```py def change_money(money): # TODO: 이곳에 코드를 작성하세요. pass # Test the function money = 1260 print(change_money(money)) # 예상 출력: {500: 2, 100: 2, 50: 1, 10: 1} ``` #### 정답 ```py def change_money(money): answer = {} coins = [500, 100, 50, 10] for coin in coins: count, money = divmod(money, coin) answer[coin] = count return answer # Test the function money = 1260 print(change_money(money)) # 예상 출력: {500: 2, 100: 2, 50: 1, 10: 1} ``` ### 문제 2 최대한 많은 일을 수행하는 방법 - 주어진 시간 내에 가능한 많은 일을 하려고 합니다. - 각 일에는 시작 시간과 끝나는 시간이 있습니다. - 일은 시작 시간과 끝나는 시간이 겹치지 않게 일정을 짜야 합니다. - 주어진 일들 중에서 가장 많은 일을 할 수 있는 방법을 찾아주세요. - 힌트 : 끝나는 시간을 기준으로 오름차순을 한 후 진행해주세요. #### 작업 - 주어진 일들의 시작 시간과 끝나는 시간을 입력 받아 가능한 많은 일을 할 수 있는 일정을 출력하세요. #### 코드 ```py def schedule_jobs(jobs): # TODO: 이곳에 코드를 작성하세요. pass # Test the function jobs = [(5, 7), (12, 14), (1, 4), (6, 10), (0, 6), (3, 5), (8, 12), (2, 13), (5, 9), (3, 8), (8, 11)] print(schedule_jobs(jobs)) # 예상 출력: [(1, 4), (5, 7), (8, 11), (12, 14)] ``` #### 정답 ```py def schedule_jobs(jobs): # 끝나는 시간을 기준으로 작업들을 오름차순 정렬 jobs.sort(key=lambda x: x[1]) # 선택된 작업들을 저장하는 리스트 selected_jobs = [jobs[0]] for i in range(1, len(jobs)): # 현재 작업의 시작 시간이 선택된 마지막 작업의 끝나는 시간 이후인 경우 선택 if jobs[i][0] >= selected_jobs[-1][1]: selected_jobs.append(jobs[i]) return selected_jobs # Test the function jobs = [(5, 7), (12, 14), (1, 4), (6, 10), (0, 6), (3, 5), (8, 12), (2, 13), (5, 9), (3, 8), (8, 11)] print(schedule_jobs(jobs)) # 예상 출력: [(1, 4), (5, 7), (8, 11), (12, 14)] ``` ### 문제 3 k번째로 작은 요소를 찾는 효율적인 방법 - 주어진 배열에서 k번째로 작은 요소를 찾는 문제입니다. - 이 문제는 힙 큐를 사용하여 효율적으로 해결할 수 있습니다. - 힌트 : 힙에 k개 보다 많은 요소가 추가되었다면 pop 으로 제거하여 높은 효율성 추구 #### 작업 - 주어진 배열과 k를 입력 받아 k번째로 작은 요소를 찾아 출력하세요. ```py def find_kth_largest(nums, k): # TODO: 이곳에 코드를 작성하세요. pass # Test the function nums = [3,2,1,5,6,4] k = 2 print(find_kth_largest(nums, k)) # 예상 출력: 2 ``` #### 정답 ```py import heapq def find_kth_smallest(nums, k): # 배열에서 가장 작은 k개의 요소를 반환 return heapq.nsmallest(k, nums)[-1] # 가장 작은 k개의 요소 중 마지막 요소가 k번째로 작은 요소임 # Test the function nums = [3,2,1,5,6,4] k = 2 print(find_kth_smallest(nums, k)) # 예상 출력: 2 ``` ## DP 개념, DP는 메모의 활용이다. ### 개념 - 동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 분해하고, - 이 하위 문제의 결과를 저장하여 이용함으로써 전체 문제를 효율적으로 해결하는 알고리즘 설계 방법론입니다. - DP는 크게 두 가지 개념, 즉 최적 부분 구조(Optimal Substructure)와 중복된 하위 문제(Overlapping Subproblems)를 활용합니다. - 최적 부분 구조 - 큰 문제의 최적 해결 방법이 그것을 구성하는 작은 문제들의 최적 해결 방법으로부터 도출될 수 있음을 의미합니다. - 즉, 전체 문제의 최적해가 부분 문제의 최적해를 통해 구할 수 있다는 것입니다. - 중복된 하위 문제 - 동일한 하위 문제가 반복적으로 발생함을 의미합니다. - 이러한 중복을 피하기 위해, 한 번 계산된 하위 문제의 결과를 메모이제이션(Memoization) - 등의 방법을 통해 저장해 두었다가 재활용하는 방식이 특징입니다. - 예를 들어, 피보나치 수열을 계산하는 문제를 생각해보면, - 피보나치 수열의 n 번째 값을 구하기 위해서는 n-1 번째 값과 n-2 번째 값을 알아야 합니다. - 이때, n-1 번째와 n-2 번째 값을 각각 구하는 데 있어서 중복되는 계산이 많이 발생하는데, - 이를 동적 계획법을 사용하여 한 번 계산된 값을 재사용함으로써 효율적으로 해결할 수 있습니다. ## 피보나치에 DP 적용하기 ### 문제 ```py # 메모이제이션을 활용해서 피보나치를 구현해주세요. def fibonacci(n): '''구현''' # 테스트 print(fibonacci(10)) # 55 ``` ### 정답 ```py # 메모이제이션을 위한 딕셔너리를 전역 변수로 선언합니다. # 이 딕셔너리는 계산된 피보나치 수열의 값을 저장하는데 사용됩니다. fib_cache = {0: 0, 1: 1} # 첫 번째와 두 번째 피보나치 수는 0과 1로 초기화합니다. def fibonacci(n): # fib_cache는 이 함수 바깥에서 선언된 전역 변수입니다. # 따라서 이를 함수 내에서 변경하려면 global 키워드를 사용해야 합니다. global fib_cache # n이 fib_cache의 키로 존재하면, 이미 계산된 값이므로 이를 반환합니다. if n in fib_cache: return fib_cache[n] # n이 fib_cache의 키로 존재하지 않는다면, 아직 계산되지 않은 값이므로 피보나치 수를 계산합니다. fib_cache[n] = fibonacci(n-1) + fibonacci(n-2) return fib_cache[n] # 테스트 print(fibonacci(10)) # 55 ``` ## 특정 금액을 최소한의 동전들로 구성 ### 정답 ```py def coinChange(coins, amount): '''구현''' # 테스트 coins = [1, 3, 4] # 동전의 종류 amount = 6 # 목표 금액 coinChange(coins, amount) # 결과 출력 : 2 ``` ### 정답 ```py def coinChange(coins, amount): # dp 배열 초기화 dp = [amount + 1] * (amount + 1) # 0원을 만드는데 필요한 동전 개수는 0개 dp[0] = 0 # 모든 금액에 대해 for money in range(1, amount + 1): # 각 동전에 대해 for coin in coins: # 동전의 액면가가 현재 금액보다 작거나 같으면 if coin <= money: # 현재 금액을 만드는데 필요한 최소 동전 개수를 업데이트 dp[money] = min(dp[money], dp[money - coin] + 1) # 최종 금액을 만드는데 필요한 최소 동전 개수가 '무한대'라면 -1 반환 if dp[amount] > amount: return -1 else: return dp[amount] # 테스트 coins = [1, 3, 4] # 동전의 종류 amount = 6 # 목표 금액 coinChange(coins, amount) # 결과 출력 : 2 ``` --- ## 이후 모의고사 풀이 $$hide - DFS BFS 그래프 완전 탐색 - 각

2024 디지털스마트부산아카데미 5기 PCCP 대비 교육