반응형 Python10 [Coding Test][Python][백준] 삼성 SW 코딩 테스트 기출문제 BOJ #12100 2048(Easy) 문제)2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다.이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.) 의 경우에서 위로 블록을 이동시키면 의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 의 상태가 된다.의 상태에서 블록을 오른쪽으로 이동시키면 가 되고, 여기서 다시 위로 블록을 이동시키면 이 된다. 여기서 오른쪽으로 블록을 이.. 2025. 2. 27. [Coding Test][Python][백준] BOJ #17484 진우의 달 여행 문제)우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다. 2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요.. 2025. 2. 5. [Coding Test][Python][백준] BOJ #20922 겹치는 건 싫어 문제)홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 KK개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.입력)첫째 줄에 정수 N (1≤N≤200000)과 K (1≤K≤100)가 주어진다.둘째 줄에는 a1,a2,...an이 주어진다 (1≤ai≤100000)출력)조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.. 2025. 2. 5. [Coding Test][Python][백준] BOJ #11723 집합 (input() vs sys.stdin.readline()) 문제)비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)all: S를 {1, 2, ..., 20} 으로 바꾼다.empty: S를 공집합으로 바꾼다.입력)첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에.. 2025. 2. 4. [Coding Test][Python] Exhaustive Search(완전 탐색)(Backtracking)개념 및 예제(순열, 조합, 부분집합) ※ Exhaustive Search(완전 탐색) 란?Exhaustive Search(완전 탐색)는 가능한 모든 경우의 수를 탐색하여 정답을 찾는 알고리즘 기법이다.특징완전성(Completeness) : 가능한 모든 경우를 확인하므로, 반드시 정답을 찾을 수 있다.비효율성(Inefficiency) : 최악의 경우 계산량이 급격히 증가하여 실행시간이 길어질 수 있다.단순성(Simplicity) : 구현이 쉽고 직관적이다.적용방법Iterative Approach : 단순 반복문을 통해 확인한다.Recursive Approach : Backtracking 기법과 함께 사용되어 불필요한 탐색을 줄일 수 있다.Bitmasking : 이진수 표현을 이용해 모든 경우의 수를 탐색할 수 있다.1. Backtracking.. 2025. 2. 4. [Coding Test][Python] Heap(Min Heap / Max Heap) Priority Queue 개념 및 예제(백준 2075번 N번째 큰 수) ※ Heap 이란? Complete Binary Tree(완전 이진 트리)로 구성된 특수한 자료구조이다. Heap은 Priority Queue를 구현하기 위해 사용된다.Heap 종류 Max Heap(최대 힙)부모 노드의 값이 자식 노드의 값보다 크거나 같은 TreeMin Heap(최소 힙)부모 노드의 값이 자식 노드의 값보다 작거나 같은 TreeMin - Max HeapMin Heap과 Max Heap을 동시에 만족하는 자료구조짝수 Level은 Min Heap을 따르고, 홀수 Level은 Max Heap을 따른다.Root Node는 최솟값을 제공하고, 그 자식 노드들은 최대값을 제공한다.Min Max Heap을 통해 최상위 레벨에서 최소값과 최대값을 빠르게 추출할 수 있는 장점이 있다.Sibling 간의.. 2025. 1. 30. [Coding Test][Python] Dynamic Programming(DP) 개념 및 예제 ※ Dynamic Programming(DP, 동적 프로그래밍) 란?DP는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 재사용하여 큰 문제를 해결하는 알고리즘이다. 즉, 동일한 하위 문제가 반복되는 문제에서 효율적이다. DP 주요 개념Optimal Substructure(최적 부분 구조)문제를 작은 하위 문제들로 나눌 수 있으며, 하위 문제의 최적 해를 사용하여 전체 문제의 최적 해를 구할 수 있어야한다.ex) 피보나치 수열 : F(n)=F(n−1)+F(n−2)Overlapping Subproblems(중복 부분 문제)동일한 하위 문제가 여러번 반복해서 나타나는 경우, 이를 저장해 재사용하면 계산량을 줄일 수 있다.ex) 피보나치 수열의 F(5)를 계산할 때 F(4),F(3)을.. 2025. 1. 27. [Coding Test][Python] Graph 개념 및 Graph 순회 예제 ※ Grapn 란?그래프 G(V,E)는 객체와 객체 간의 관계를 표현하기위한 자료구조이다. Graph는 객체를 표현하는 Vextex의 집합 V와 이들을 연결하는 Edge의 집합으로 구성된다. 그래프의 기본 구성요소Vertex(Node)그래프를 구성하는 기본 요소데이터의 단위를 표현한다Vertex의 집합은 일반적으로 V로 표시한다Edge두 Vertex를 연결하는 선 또는 관계를 의미한다방향성, 가중치 등에 따라 다양한 특성을 가질 수 있다Edge의 집합은 일반적으로 E로 표시한다그래프의 종류Undirected Graph(무방향 그래프)Edge에 방향이 없다. 즉, Vertex u와 v가 연결되어있다면, 서로 연결된 상태이다.Directed Graph(방향 그래프)Edge에 방향이 있다. 즉,.. 2025. 1. 27. [Coding Test][Python] Hash Table(Dictionary) 개념 및 예제 ※ Hash Table 이란?효율적인 탐색을 위한 자료구조로써 key-value 쌍의 데이터를 입력받는다. Hash Function h의 key값을 입력으로 얻은 해시값 h(k)를 위치로 지정하여 저장한다. 저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다. Direct Access AddressDirect Access Address는 특정 Key 값을 주소로 직접 사용하여 데이터를 저장하는 방식이다.위 2가지 단점이 존재하기 때문에 Key 값에 Hash Function을 적용하여 사용한다.불필요한 메모리 공간 낭비ex) Key 값이 1, 1000 => 2개의 데이터를 위해 1000개의 공간이 필요Key 값으로 문자열이 올 수 없다Collision서로 다른 Key의 Hash.. 2025. 1. 27. 이전 1 2 다음 반응형