🤔 문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요. 😉 제한사항 W, H : 1억 이하의 자연수 😧 입출력 예 W H result 8 12 80 🥳 풀이 ❤️ 생각의 흐름 어디서 본 듯 한 수학 문제… 수…

😍 출처 파이썬 알고리즘 인터뷰 😧 문제 [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순으로 방문한다. 🤔 예제 😉 풀이1) DFS로 일정 그래프 구성 💛 예시를 통한 풀이 = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]] 먼저 주어진 tickets의 요소들을 그래프 안에 넣어버리자! : 파이썬의 내장 모듈인 의 는 key 값을 넣었을 때 value 값이 존재하지 않더라도, 임의로 value 값을 넣어주는 기본값을 지정한 딕셔너리이다. 다시 코드로 돌아와서, 라는 이름으로 딕셔너리가 선언된 것을 볼 수 있다. 이 딕셔너리는 일반적인 딕셔너리가 아닌 딕셔너리이다. 지금부터 안에 를 차곡차곡 넣어 줄 것이다. 문제에서 중복된 일정인 경우 어휘 순으로 방문 한다고 조건을 달았으니, 를 sort 해주어 어휘 순…

😍 출처 파이썬 알고리즘 인터뷰 😧 문제 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다. 🤔 예제 😉 풀이) DFS로 중복 조합 그래프 탐색 각 원소는 중복 해서 사용가능하므로 주어진 원소의 중복 조합을 모두 구해주는 것이 핵심이다. 💛 예시를 통한 풀이 = [2, 3, 6, 7] = 7 = (중복조합을 구하는 리스트) = (target) - (하나의 조합 안의 원소들의 총 합) 이해를 쉽게 하기 위해 GIF를 먼저 보도록 하자! Untitled 재귀 호출을 반복하며 중복조합을 모두 구해나가는 것이 특징이다. 이때, 재귀 호출을 탈출하는 조건은 다음과 같다. csum < 0 인 경우 이는 target 값을 초과하였기 때문에 종료한다. csum = 0 인 경우 이는 target 값을 만족하였기 때문에 해당 중복조합을 에 추가한 뒤, 종료한다. 💛 전체 코드 😍 출처 😧 문제 🤔 예제 😉 풀이) DFS로 …

🤔문제 설명 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. “[닉네임]님이 들어왔습니다.” 채팅방에서 누군가 나가면 다음 메시지가 출력된다. “[닉네임]님이 나갔습니다.” 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들어, 채팅방에 “Muzi”와 “Prodo”라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다. “Muzi님이 들어왔습니다.""Prodo님이 들어왔습니다.…