난쟁이 개발자

[코딩 테스트 합격자 되기 파이썬 - 4주차]시뮬레이션

개념$N \times N$ 크기의 2차원 정수 행렬을 시계 방향으로 90도 회전시키는 기능을 구현한다고 가정해 봅시다. 각 행렬의 원소가 회전 후 어떤 새로운 위치로 이동해야 할지에 대한 좌표 변환 규칙 아이디어를 시뮬레이션하여 설명해주세요. 예를 들어, 원래 행렬의 (r, c) 위치에 있던 원소는 회전 후 어떤 (r', c')위치로 이동해야 할까요? 이 규칙을 일반화하여 설명하고, 이를 구현하기 위한 주요 단계를 논리적으로 나열해주세요.더보기2차원 정수 행렬을 시계방향으로 90도 회전하는 것을 일반화하면, A`[j, (N-1)-i] = A[i, j] 를 적용하면 90도 시계방향으로 회전한 배열을 얻을 수 있다. 이를 반대로 하면 반시계방향으로 90도 회전하는 배열을 얻을 수 있다. 책 문제 62번, 배..

Kth Largest Element in an ArrayGiven an integer array nums and an integer k, return the kth largest element in the array.Note that it is the kth largest element in the sorted order, not the kth distinct element.Can you solve it without sorting? Example 1:Input: nums = [3,2,1,5,6,4], k = 2Output: 5Example 2:Input: nums = [3,2,3,1,2,4,5,5,6], k = 4Output: 4 Constraints:1 5-104 4 class Solution: ..

Edit DistanceGiven two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.You have the following three operations permitted on a word:Insert a characterDelete a characterReplace a character Example 1:Input: word1 = "horse", word2 = "ros"Output: 3Explanation: horse -> rorse (replace 'h' with 'r')rorse -> rose (remove 'r')rose -> ros (remove 'e')Exa..

Number of 1 BitsGiven a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight). Example 1:Input: n = 11Output: 3Explanation:The input binary string 1011 has a total of three set bits.Example 2:Input: n = 128Output: 1Explanation:The input binary string 10000000 has a total of one set bit.Example 3:Input: n = 2147483..

개념1. 백트래킹(Backtracking) 알고리즘의 작동 원리를 설명하고, 상태 공간 트리(State Space Tree) 개념과 연관 지어 설명해주세요. 주로 어떤 방식으로 구현되며 (예:재귀), 그 이유는 무엇인가요?더보기백트래킹 알고리즘은 어떤 가능성이 없는 곳을 알아보고 되돌아 가는 것입니다. 책을 살펴보면, 시작점(루트)은 빈 리스트로 시작을 한다. 숫자가 4개가 포함되어 있으니, level 0 -> 1로 내려가면, 빈 리스트에 하나의 숫자씩 차지하게 된다. res = [[1], [2], [3], [4]]숫자 2개의 조합을 완성해야 하므로, 이 아래로 선택한 숫자를 제외한 3개씩 노드를 가지게 되면 총 12개 조합이 완성되고, 이를 모두 통과하게 되면 O(12)이 될 것이다. ($O(N^{2}..

개념 문제BFS(너비 우선 탐색) 알고리즘의 작동 원리를 설명하고, 어떤 자료구조를 사용하는지, 그리고 그 이유는 무엇인지 설명해주세요.더보기BFS(너비 우선 탐색)는 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘입니다. 이를 위해 '큐' 자료구조를 채택하여 시작 노드를 큐에 넣은 다음, 방문 처리를 합니다. 이후,1. 큐가 비었는지 확인. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했기 때문에 탐색을 종료합니다.2. 큐에서 노드를 팝합니다.3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드는 큐에 푸시하여 방문처리이 과정을 반복하는 것이 BFS입니다.고려 사항으로는1. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 하고,2. 이미..

개념문제DFS를 구현하는 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는 것입니다. 각 구현 방식의 장단점을 비교 설명해주세요.더보기1. 재귀재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 DFS에 적용하여 구현하게 된다. 장점 : 코드의 간결함, (호출 스택이 DFS의 진행 과정을 자연스럽게 관리)단점 : 스택오버플로우 발생 가능성이 높다, (함수 호출 오버헤드로 인한 성능 저하).직접 문제를 풀면서 느꼈던 재귀 함수와 DFS의 장단점은 코드가 간결한 만큼, 스택오버플로우(시간초과, 메모리초과) 발생 확률이 타 문제들보다 많았다는 점이다. 메모리초과가 나지 않으면 시간초과로 이어지는 경우가 많았다. 괄호 내 내용은 각종 AI툴들..