본문 바로가기

Algorithm

 (77)
[프로그래머스] 코딩테스트 연습 - 표 편집(Python) 코딩테스트 연습 - 표 편집 [2021 카카오 채용연계형 인턴십] 풀이 참 Python이 낯설게 느껴지고 많은 걸 배울 수 있었던 문제였습니다. 그리고 3번의 풀이 끝에 간신히 해결했습니다. 사실 Python에 대한 지식이 얕아 틀린 방법이 맞는 방법이라고 생각한 게 시간을 가장 많이 잡아먹은 요인인 것 같습니다. 머리가 안 좋아 몸도 고생하고 머리도 고생한 타입...ㅎㅎ 어떠한 시도를 했는지 적어 보겠습니다. (모든 풀이 과정에서 deque을 이용한 stack을 사용했습니다!) 1. 0~n의 정수를 담은 list를 deque으로 만들어 삽입/삭제를 하는 방식으로 구현 위의 방식으로 풀이를 해보면 효율성을 하나도 통과하지 못합니다. 그 이유는 deque의 특성을 생각해보면 알 수 있습니다. deque은 ..
[프로그래머스] 코딩테스트 연습 - 거리두기 확인하기(Python) 코딩테스트 연습 - 거리두기 확인하기 [2021 카카오 채용연계형 인턴십] 풀이 풀이를 하며 반복문 중첩이 많아서 이렇게 짜도 되나 싶었지만 뭐 별수있나요.. 필요하면 써야죠ㅎㅎ 먼저 맨해튼 거리 2를 만족시키기 위해서는 [상하좌우 이동 -> 상하좌우 이동(왔던경로 포함 X)]을 하면 됩니다. 그리고 이동 중에 P를 만나면 바로 0을 반환하면 됩니다. Code def check(pl): for row in range(5): for col in range(5): if pl[row][col] != "P": continue for r, c in [(0, 1), (1, 0), (-1, 0), (0, -1)]: # [right, bottom, top, left] 순서 pl[row][col] = "X" newr, ..
[프로그래머스] 코딩테스트 연습 - 삼각 달팽이(Python) 코딩테스트 연습 - 삼각 달팽이 [월간 코드 챌린지 시즌1] 풀이 문제의 설명대로 코드를 짜면 되는 문제였던 것 같습니다. 귀여운 달팽이는 반시계 방향으로 삼각형을 그리며 안으로 돕니다. 아래의 경우를 보며 달팽이가 몇 번 어떻게 돌았는 지를 생각해보죠. 1. 왼쪽변 - [1, 2, 3, 4] 2. 밑변 - [5, 6, 7] 3. 오른쪽 변 - [8, 9] 4. 왼쪽변 - [10] 달팽이는 n개의 변을 그리고 하나의 변을 지날 때마다 그리는 숫자가 하나씩 줄어들게 됩니다. 그리고 방향은 [왼쪽-밑-오른쪽] 순서로 돌게 되니 % 3의 결과에 따라 움직임을 달리해주면 됩니다. Code def solution(n): triangle = [[0 for j in range(i,i+i)] for i in range..
[프로그래머스] 코딩테스트 연습 - [1차] 프렌즈4블록(Python) 코딩테스트 연습 - [1차] 프렌즈4블록 [2018 KAKAO BLIND RECRUITMENT] 풀이 해당문제는 특별한 알고리즘이 필요한 것이 아닌 구현 문제였던 것 같습니다. 처음 문제를 풀었던 방식은 board를 그대로 2차원배열로 만들어 사라질 2x2블록을 찾아 위에 남은 블록을 내리는 방식으로 구현하려 했습니다. 그런데 남은 블록을 내리는 기능(열 갱신)을 어떻게 구현할지 생각하다 보니 열을 갱신하는 방법보다 board를 90도 회전시켜서 행을 갱신하는 방법이 더욱 좋을 것 같다는 생각이 들었습니다. slice해서 당겨오거나 새로운 바뀌게 될 행을 새로 만들어 갈아껴주기만하면 되니까요. Code def solution(m, n, board): answer = 0 bd = list(map(list,..
[프로그래머스] 코딩테스트 연습 - 사칙연산(Python) 코딩테스트 연습 - 사칙연산 [찾아라 프로그래밍 마에스터] 풀이 저는 개인적으로 정말 어려웠던 문제였습니다. 처음 시도했던 방법은 순열이었습니다. 풀다가 생각해보니 순열로 풀려면 모든 연산자에 대해 순열이 필요하고 100개의 연산자가 있으면 반복해야 하는 횟수가 너무 많아지더라고요. 그래서 다른 방법을 생각하다가 DP로 최소, 최대값을 저장하면서 풀면 되겠다 싶었는데 코드를 짜는 것이 쉽지만은 않아서 결국 질문하기에 풀이를 공유해주신 분의 c++코드를 참고해서 풀었습니다ㅎㅎ.. 미흡하겠지만 제가 이해한 것들을 바탕으로 설명을 해보겠습니다. 먼저 풀이에 대해 간단하게 설명해보자면 풀이를 공유해주신 분의 방식과 같이 식을 뒤에서 부터 읽으며 -를 만났을 때에는 최댓값과 최솟값을 갱신하고 +를 만나면 이전 -..
[프로그래머스] 코딩테스트 연습 - 짝지어 제거하기(Python) 코딩테스트 연습 - 짝지어 제거하기 [2017 팁스타운] 풀이 - Stack 문제를 처음 풀었을 때는 제한사항을 안보고 while문에 문자열 s를 변경하며 풀다보니 효율성에서 시간초과가 나왔습니다..ㅎㅎ 아무래도 문자열 s를 한번 보더라도 문자열 s의 길이가 길어지면 중간에 추가되는 문자열 생성이나 삭제같은 방법으로 문자열 s를 갱신하는 연산도 같이 많아져 시간초과가 발생한 것 같습니다. 예를 들어 보면 문자열 s의 길이가 10,000개이고 짝이되는 알파벳이 (0, 1)와 (2, 3)에 있다고 가정해보겠습니다. 1. (0, 1)을 빼고 인덱스 2~99까지를 0~9,997로 복사 2. (0, 1)[원래 (2, 3)인덱스]을 빼고 인덱스 2~9,995까지 복사 위와 같은 연산이 계속된다면 아무리 문자열을 한..
[프로그래머스] 코딩테스트 연습 - 다단계 칫솔 판매(Python) 코딩테스트 연습 - 다단계 칫솔 판매 [2021 Dev-Matching: 웹 백엔드 개발자(상반기)] 풀이 문제 설명의 첫 이미지부터 어떻게 풀면 될지 힌트를 준 문제 같습니다. (제 풀이도 문제 설명의 순서를 그대로 코드로 적은 것뿐이거든요ㅎㅎ) 문제에 사용된 개념은 설명의 이미지처럼 Tree와 queue입니다. 직원과 추천인의 관계가 Tree의 형태라면 판매금액이 있는 노드에서 queue를 이용해서 추천인을 따라 타고 올라가며 금액만 계산하면 문제는 해결될 테니까요. deque을 사용한 이유는 pop이나 append 같은 함수를 사용할 때 일반 list을 사용하는 것보다 빨라서 사용했습니다. Code from collections import defaultdict, deque def solution(..
[프로그래머스] 코딩테스트 연습 - 자물쇠와 열쇠(Python) 코딩테스트 연습 - 자물쇠와 열쇠 [2020 KAKAO BLIND RECRUITMENT] 풀이 Python에는 행렬이나 다차원 배열을 쉽게 다루기 위한 Numpy 라이브러리가 있습니다. 저는 Numpy모듈을 lock배열의 zero-padding과 key배열의 회전을 위해 사용하였습니다. numpy가 python배열을 사용하는 것보다 행렬 or 다차원 배열에 대한 연산이 빠른 이유는 numpy는 c++로 구현되어 있어서 똑같은 방식으로 계산을 하더라도 속도의 차이가 있을 수밖에 없다고 하네요ㅎㅎ 여담이지만 문제를 읽어보니 Key를 이리저리 돌리거나 이동시켜서 lock에 맞춰보는 점이 마치 영상처리의 Image와 filter를 보는 것 같더군요ㅎㅎ Code import numpy as np def solut..

티스토리툴바