Passwd

[Algorithm] 이차원 배열 나선 순회

개요최근 이차원 배열을 나선 순환하는 알고리즘 문제를 풀었다. 방법은 알았는데, 그걸 실제로 구현하는 것에서 약간 어려움이 있었어서 적절한 구현 방법을 정리해두려고 한다. 이 글에서 구현하고자 하는 것은 n 행, m 열로 이루어진 이차원 배열을 나선 순회하는 코드이다. 출발 시 이동 방향은 오른쪽이다. 방법아이디어는 다음과 같다.각 방향 별 끝 갑을 초기화한다.끝에 다다랐을 때 끝 값을 갱신한다.구현해 보자. 1. 배열 및 끝 값 초기화# n행 m열 배열 초기화spiral_list = [[0 for _ in range(m)] for _ in range(n)]# 방향 별 끝 값lp_left_side = 0lp_right_side = m - 1lp_up_side = 1 # i == 0 부터 순회 하므로..

문제문제 : https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/N개의 정수로 구성된 비어 있지 않은 배열 A가 있다. 배열 A의 연속된 요소는 도로 위의 연속된 자동차를 나타내며, 배열 A에는 0 또는 1로만 구성되어 있다. 이때, 0은 동쪽으로 이동하는 차량을 나타내고 1은 서쪽으로 이동하는 차량을 나타낸다.목표는 지나가는 차를 세는 것으로, P가 동쪽으로 이동하고 Q가 서쪽으로 이동할 때 0 ≤ P 한 쌍의 차 (P, Q)가 지나간다고 한다.예로 들어 아래와 같은 배열 A가 있다고 하자. A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1지나가는 차의 쌍은 (0, 1), (0, 3), ..

문제문제 : https://www.acmicpc.net/problem/1926어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.   풀이BFS 방식으로 풀어낼 수 있는 문제이다. 1. 입력값  초기화입력으로 받는 n과 m, 그리고 그림을 초기화한다.n, m = map(int, sys.stdin.readline().split())graph = [list(map(int, sys.stdin.readline().split())) for i in ran..

문제문제 : https://leetcode.com/problems/monthly-transactions-i/description/?envType=study-plan-v2&envId=top-sql-50+---------------+---------+| Column Name | Type |+---------------+---------+| id | int || country | varchar || state | enum || amount | int || trans_date | date |+---------------+---------+id는 테이블의 PK이고, 이 테이블은 들어오는 트랜잭션에 대한 정보를 가지고 ..

문제문제 : https://app.codility.com/programmers/lessons/1-iterations/binary_gap/양의 정수 N에서 바이너리 갭은 이진수에서 양 끝이 1로 둘러싸인 연속된 0의 최대 수이다.예로 들어, 숫자 9는 이진수로 1001이고, 길이가 2인 바이너리 갭을 가진다. 숫자 529는 이진수로 1000010001이며, 길이가 4이고 3인 두 개의 바이너리 갭을 가진다. 숫자 20인 이진수로 10100이고 길이가 1인 바이너리 갭을 가지고, 숫자 15는 이진수로 1111이고 바이너리 갭을 갖고 있지 않다. 숫자 32 또한 이진수로 100000으로 바이너리 갭을 가지고 있지 않다. 양의 정수 N이 주어지면 가장 긴 바이너리 갭의 길이를 반환하는 함수를 작성하라. N에 바..

문제문제 : https://leetcode.com/problems/primary-department-for-each-employee/?envType=study-plan-v2&envId=top-sql-50다음과 같은 스키마를 가진 테이블 Employee가 존재한다.+---------------+---------+| Column Name | Type |+---------------+---------+| employee_id | int || department_id | int || primary_flag | varchar |+---------------+---------+employee_id는 직원의 ID이고,  department_id는 직원이 속한 부서의 ID이다. employ..

문제문제 : https://leetcode.com/problems/is-subsequence/?envType=study-plan-v2&envId=leetcode-75문자열 s, t가 주어질 때 s가 T의 하위 문자열이면 True를 반환하고, 하위 문자열이 아니면 False를 반환하는 프로그램을 작성하라.여기서 하위 문자열이란, 나머지 문자의 상대적인 위치를 방해하지 않고 일부 문자열을 삭제하여 원래 문자열에서 형성되는 새로운 문자열을 말한다.  예시 )- s가 abc이고 t가 ahbgdc인 경우, t는 s의 하위 문자열이다.- s가 axc이고 t가 ahbgdc인 경우, t는 s의 하위 문자열이 아니다.   풀이정규표현식 패턴을 만들어, t가 패턴에 일치하는지 확인하는 방식으로 구현했다.예로 들어 s가 a..

문제문제 : https://leetcode.com/problems/average-selling-price/description/?envType=study-plan-v2&envId=top-sql-50 테이블 : Prices+---------------+---------+| Column Name | Type |+---------------+---------+| product_id | int || start_date | date || end_date | date || price | int |+---------------+---------+(product_id, start_date, end_date)는 테이블의 PK이다.테이블의 각 행은 sta..

문제문제 : https://leetcode.com/problems/move-zeroes/description/?envType=study-plan-v2&envId=leetcode-75정수 배열 nums가 주어지면, 0이 아닌 원소의 상대적인 순서를 유지하면서 모든 0을 끝으로 이동시키는 코드를 작성해라.단, 배열 복사 없이 원본 배열을 교체해야 한다. 예시 )# 예시 1Input: nums = [0,1,0,3,12]Output: [1,3,12,0,0]# 예시 2Input: nums = [0]Output: [0]  풀이 1배열을 전체적으로 순환하면서 0인 수를 발견하면 한 칸씩 뒤로 미루는 방법이다.class Solution: def moveZeroes(self, nums: List[int]) -> N..

문제문제 : https://www.acmicpc.net/problem/7770아즈텍 피라미드는 1 * 1 * 1 크기의 정육면체 돌 블록으로 만든다. 피라미드는 먼저 블록 하나를 놓은 뒤, 이후에 놓는 블록은 이전에 놓인 블록과 한 면 전체를 공유해야 한다.블록은 땅 바로 위에 있거나, 블록 아래에 있는 블록의 모든 면이 인접하고 있을 때 안정적이라고 하며, 모든 블록은 안정적이여야 한다.사용할 수 있는 블록의 개수가 주어졌을 때, 블록으로 만들 수 있는 안정적인 피라미드의 높이를 구하여라.   풀이계산하기 편하게 이미 쌓은 블록을 위로 올리고, 바닥에 놓아야 할 블록의 수를 생각해보자.층에 따라 바닥에 최소로 놓아야 하는 블록의 수는 다음과 같다.N층일 때 바닥에 놓아야 하는 최소 블록의 수를 구했다면..