알고리즘
-
📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 "크레인 인형뽑기 게임"의 로직을 구현하는 문제다. 게임은 1x1 크기의 칸으로 이루어진 NxN 크기의 정사각 격자로 이루어진 화면에서 이루어지며, 위쪽에 인형을 잡기 위한 크레인과 크레인으로 잡은 인형을 담을 별도의 바구니가 있다. 모든 인형은 1x1 크기의 격자 한 칸을 차지하며, 격자 아래 칸부터 차곡차곡 쌓여있는 모습을 띤다. 사용자는 크레인을 좌우로 움직여서 가장 위에 있는 인형을 하나 집어 올릴 수 있으며, 이 집어 올린 인형은 바구니의 가장 아래 칸부터..
[Programmers/Lv. 1] 크레인 인형뽑기 게임 (2019 KAKAO 개발자 겨울 인턴십, Python)📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 "크레인 인형뽑기 게임"의 로직을 구현하는 문제다. 게임은 1x1 크기의 칸으로 이루어진 NxN 크기의 정사각 격자로 이루어진 화면에서 이루어지며, 위쪽에 인형을 잡기 위한 크레인과 크레인으로 잡은 인형을 담을 별도의 바구니가 있다. 모든 인형은 1x1 크기의 격자 한 칸을 차지하며, 격자 아래 칸부터 차곡차곡 쌓여있는 모습을 띤다. 사용자는 크레인을 좌우로 움직여서 가장 위에 있는 인형을 하나 집어 올릴 수 있으며, 이 집어 올린 인형은 바구니의 가장 아래 칸부터..
2023.11.06 -
😳 힙(Heap) 기초 개념 간단하게 살펴보기 힙(Heap)이란? : "완전 이진트리"라는 형태적 속성과, "모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다"는 힙 속성을 모두 만족시키는 자료구조이다. (즉, 힙을 이해하기 위해서는 트리를 먼저 알아야만 한다!) 그렇다면, 트리(Tree)란? : 데이터의 상-하 관계를 계층적으로 나타내는 자료구조이다. (말 그대로, 트리 모양을 생각하면 되겠다.)-> 맨 위에 있는 노드를 Root 노드, 트리 연결의 가장 마지막 노드를 Leaf 노드라고 부른다.-> 데이터의 상-하 관계를 부모 노드-자식 노드 관계라고 부르며, 같은 깊이에 있는 노드들끼리는 형제 노드라고 부른다. 트리의 종류는 어떤 것들이 있을까? 이진트리 (Binary Tree) : 각 노드..
[Programmers, Lv.2] 코딩테스트 고득점 Kit - 힙(Heap) (1), 더 맵게 (Python)😳 힙(Heap) 기초 개념 간단하게 살펴보기 힙(Heap)이란? : "완전 이진트리"라는 형태적 속성과, "모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다"는 힙 속성을 모두 만족시키는 자료구조이다. (즉, 힙을 이해하기 위해서는 트리를 먼저 알아야만 한다!) 그렇다면, 트리(Tree)란? : 데이터의 상-하 관계를 계층적으로 나타내는 자료구조이다. (말 그대로, 트리 모양을 생각하면 되겠다.)-> 맨 위에 있는 노드를 Root 노드, 트리 연결의 가장 마지막 노드를 Leaf 노드라고 부른다.-> 데이터의 상-하 관계를 부모 노드-자식 노드 관계라고 부르며, 같은 깊이에 있는 노드들끼리는 형제 노드라고 부른다. 트리의 종류는 어떤 것들이 있을까? 이진트리 (Binary Tree) : 각 노드..
2023.09.16 -
1. 전화번호 목록 (Level 2) (문제 설명, 제한사항, 입출력 예) 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 반환하라는 문제이다. 각 전화번호의 길이는 1 이상 20 이하이며, 같은 전화번호가 중복해서 들어있지는 않다고 한다. (내가 생각한 풀이 과정) phone_book 리스트에 담겨있는 전화번호를 하나씩 반복한다. 반복되는 요소와 바로 다음 요소를 비교할 건데, 접두어를 비교해야 하므로 해당 반복 요소 인덱스 i의 길이만큼 슬라이싱 후 비교한다. 만약, 두 글자가 같다면 접두어가 같다고 판단할 수 있다. -> False 반환 반복을 끝까지 해도 조건에 걸리지 않는다면, 같은 ..
[Programmers, Lv.2] 코딩테스트 고득점 Kit - 해시 (2) (Python)1. 전화번호 목록 (Level 2) (문제 설명, 제한사항, 입출력 예) 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 반환하라는 문제이다. 각 전화번호의 길이는 1 이상 20 이하이며, 같은 전화번호가 중복해서 들어있지는 않다고 한다. (내가 생각한 풀이 과정) phone_book 리스트에 담겨있는 전화번호를 하나씩 반복한다. 반복되는 요소와 바로 다음 요소를 비교할 건데, 접두어를 비교해야 하므로 해당 반복 요소 인덱스 i의 길이만큼 슬라이싱 후 비교한다. 만약, 두 글자가 같다면 접두어가 같다고 판단할 수 있다. -> False 반환 반복을 끝까지 해도 조건에 걸리지 않는다면, 같은 ..
2023.09.12 -
📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 실패율을 구하는 코드를 완성하라는 문제이다. 실패율은 다음과 같이 정의한다. "스테이지에 도착했으나, 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수" 전체 스테이지의 개수 N과, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열이 같이 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 구하라는 문제이다. 🤔 내가 생각한 풀이 과정 (1) - 런타임 에러 코드 문제에 나와있는 예시..
[Programmers/Lv. 1] 실패율 (2019 KAKAO BLIND RECRUITMENT, Python)📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 실패율을 구하는 코드를 완성하라는 문제이다. 실패율은 다음과 같이 정의한다. "스테이지에 도착했으나, 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수" 전체 스테이지의 개수 N과, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열이 같이 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 구하라는 문제이다. 🤔 내가 생각한 풀이 과정 (1) - 런타임 에러 코드 문제에 나와있는 예시..
2023.08.24 -
📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 정수 n이 매개변수로 주어질 때, 그림과 같은 밑변의 길이와 높이가 n인 삼각형에 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한다. 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 구하라는 문제이다. 🤔 내가 생각한 풀이 과정 나는 아래와 같은 순서를 가지고 문제를 해결하려 했다. 값을 넣을 2차원 배열을 만든다. -> 배열에 들어가는 최댓값을 구한다.(n=4일 때 10, n=5일 때 15) -> 1부터 구한 최댓값까지 반복하면서 올바른 행, ..
[Programmers/Lv. 2] 삼각 달팽이 (월간 코드 챌린지 시즌1, Python)📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 정수 n이 매개변수로 주어질 때, 그림과 같은 밑변의 길이와 높이가 n인 삼각형에 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한다. 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 구하라는 문제이다. 🤔 내가 생각한 풀이 과정 나는 아래와 같은 순서를 가지고 문제를 해결하려 했다. 값을 넣을 2차원 배열을 만든다. -> 배열에 들어가는 최댓값을 구한다.(n=4일 때 10, n=5일 때 15) -> 1부터 구한 최댓값까지 반복하면서 올바른 행, ..
2023.08.15 -
📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 주어진 문자열 s를 아래 규칙에 따라서 분해하고, 분해된 문자열의 개수를 구하라는 문제이다. 문자열 s의 첫 글자를 x라고 한다. (문자열 s는 소문자로만 이루어진다.) 문자열을 읽어나가면서 x가 나온 횟수와 x가 아닌 글자가 나온 횟수를 카운트한다. 처음으로 두 횟수가 같아지는 순간 (0 제외) 이 카운트를 멈추고, 지금까지 읽은 문자열을 분리한다. 분리된 문자열을 빼고, 남은 부분에 대해서 "첫 글자를 읽고 -> 문자별 나온 횟수 카운트" 과정을 반복한다. 두 ..
[Programmers/Lv. 1] 문자열 나누기 (프로그래머스 연습문제, Python)📎 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제설명, 제한사항, 입출력 예 주어진 문자열 s를 아래 규칙에 따라서 분해하고, 분해된 문자열의 개수를 구하라는 문제이다. 문자열 s의 첫 글자를 x라고 한다. (문자열 s는 소문자로만 이루어진다.) 문자열을 읽어나가면서 x가 나온 횟수와 x가 아닌 글자가 나온 횟수를 카운트한다. 처음으로 두 횟수가 같아지는 순간 (0 제외) 이 카운트를 멈추고, 지금까지 읽은 문자열을 분리한다. 분리된 문자열을 빼고, 남은 부분에 대해서 "첫 글자를 읽고 -> 문자별 나온 횟수 카운트" 과정을 반복한다. 두 ..
2023.08.08 -
1. 문자열 밀기 (문제 설명, 제한사항, 입출력 예) 문자열 A와 B가 주어질 때, A를 밀어서 B가 될 수 있다면, 밀어야 하는 최소 횟수를 구하라는 문제이다. 만약, 밀어서 B가 될 수 없으면 -1을 반환하면 된다. (내가 생각한 풀이 과정) 차례대로 조건을 세 개로 나누어서 문제를 풀었다. 첫 번째, A와 B가 같은 경우 -> 0을 반환 두 번째, A와 B를 한 칸씩 밀면서 두 문자열을 비교 -> shift의 숫자대로 밀면서 문자열을 "A[-shift:] + A[0:-shift]" 형태로 비교 세 번째, A의 길이만큼 밀었는데도 (한바퀴 돈 경우) 같은 값이 나오지 않는 경우 -> -1 반환 (될 수 없다고 판단) (코드) 더보기 💡 내 코드 def solution(A, B): shift = 1 ..
[Programmers/Lv. 0] 코딩테스트 입문 Day 25 - 시뮬레이션, 조건문, 수학 (Python)1. 문자열 밀기 (문제 설명, 제한사항, 입출력 예) 문자열 A와 B가 주어질 때, A를 밀어서 B가 될 수 있다면, 밀어야 하는 최소 횟수를 구하라는 문제이다. 만약, 밀어서 B가 될 수 없으면 -1을 반환하면 된다. (내가 생각한 풀이 과정) 차례대로 조건을 세 개로 나누어서 문제를 풀었다. 첫 번째, A와 B가 같은 경우 -> 0을 반환 두 번째, A와 B를 한 칸씩 밀면서 두 문자열을 비교 -> shift의 숫자대로 밀면서 문자열을 "A[-shift:] + A[0:-shift]" 형태로 비교 세 번째, A의 길이만큼 밀었는데도 (한바퀴 돈 경우) 같은 값이 나오지 않는 경우 -> -1 반환 (될 수 없다고 판단) (코드) 더보기 💡 내 코드 def solution(A, B): shift = 1 ..
2023.06.07 -
1. 치킨 쿠폰 (문제 설명, 제한사항, 입출력 예) 치킨 한 마리당 쿠폰을 한 장 발급해 주는 치킨집이 있다. 쿠폰을 열장 모으면 치킨을 한 마리 서비스로 받을 수 있고, 서비스로 주는 치킨에도 쿠폰을 발급해 준다. 시켜 먹은 치킨의 수가 주어질 때, 받을 수 있는 최대 서비스 치킨의 수를 구하라는 문제이다. (내가 생각한 풀이 과정) 총 서비스를 받은 치킨의 수를 저장할 정수 변수 answer를 만들어둔다. 이제 10마리를 기준으로 입력값 chicken을 계속 반복시킬 거다. 어떻게 반복할 거냐면. 1) 입력값 chicken을 10으로 나누어서 서비스로 받은 치킨의 값을 answer에 추가한다. 2) chicken에는 10으로 나누고 남은 나머지 값과 + 서비스로 받은 치킨의 값을 저장해 둔다 (서비..
[Programmers/Lv. 0] 코딩테스트 입문 Day 24 - 수학, 시뮬레이션, 문자열, 조건문, 반복문 (Python)1. 치킨 쿠폰 (문제 설명, 제한사항, 입출력 예) 치킨 한 마리당 쿠폰을 한 장 발급해 주는 치킨집이 있다. 쿠폰을 열장 모으면 치킨을 한 마리 서비스로 받을 수 있고, 서비스로 주는 치킨에도 쿠폰을 발급해 준다. 시켜 먹은 치킨의 수가 주어질 때, 받을 수 있는 최대 서비스 치킨의 수를 구하라는 문제이다. (내가 생각한 풀이 과정) 총 서비스를 받은 치킨의 수를 저장할 정수 변수 answer를 만들어둔다. 이제 10마리를 기준으로 입력값 chicken을 계속 반복시킬 거다. 어떻게 반복할 거냐면. 1) 입력값 chicken을 10으로 나누어서 서비스로 받은 치킨의 값을 answer에 추가한다. 2) chicken에는 10으로 나누고 남은 나머지 값과 + 서비스로 받은 치킨의 값을 저장해 둔다 (서비..
2023.06.06 -
1. 특이한 정렬 (문제 설명, 제한사항, 입출력 예) 배열 numlist와 정수 n이 주어질 때, numlist의 원소를 n으로부터 가까운 순서대로 정렬한 배열을 구하라는 문제이다. 만약 n으로부터 거리가 같다면, 더 큰 수를 앞에 오도록 배치하면 된다. 단, numlist 배열은 중복된 원소를 갖지 않는다. n의 범위는 1 이상, 10,000 이하로 제한한다. (내가 생각한 풀이 과정) 이 문제는 내가 처음 생각했던 것과 다르게 몇 번의 "도약"이 필요했던 문제였다. 처음 생각한 풀이 과정과 나의 도약을 함께 따라가면서 이해해 보자. 우선, 처음 생각한 풀이 과정은 간단했다. n과 가까운 수를 구하기 위해 num에서 n을 빼 절댓값을 씌워준 후, 새로운 리스트 1에 추가하고, 값이 작은 순서대로 새로..
[Programmers/Lv. 0] 코딩테스트 입문 Day 23 - 배열, 정렬, 문자열 (Python)1. 특이한 정렬 (문제 설명, 제한사항, 입출력 예) 배열 numlist와 정수 n이 주어질 때, numlist의 원소를 n으로부터 가까운 순서대로 정렬한 배열을 구하라는 문제이다. 만약 n으로부터 거리가 같다면, 더 큰 수를 앞에 오도록 배치하면 된다. 단, numlist 배열은 중복된 원소를 갖지 않는다. n의 범위는 1 이상, 10,000 이하로 제한한다. (내가 생각한 풀이 과정) 이 문제는 내가 처음 생각했던 것과 다르게 몇 번의 "도약"이 필요했던 문제였다. 처음 생각한 풀이 과정과 나의 도약을 함께 따라가면서 이해해 보자. 우선, 처음 생각한 풀이 과정은 간단했다. n과 가까운 수를 구하기 위해 num에서 n을 빼 절댓값을 씌워준 후, 새로운 리스트 1에 추가하고, 값이 작은 순서대로 새로..
2023.06.06 -
1. 저주의 숫자 3 (문제 설명, 제한사항, 입출력 예) 3의 배수와 숫자 3을 사용하지 않는 3x 마을 사람들이 있다. 주어진 정수 n을 3x 마을에서 사용하는 숫자로 바꿔서 구하라는 문제이다. (단, 정수 n의 범위는 1 이상, 100 이하) (내가 생각한 풀이 과정) 고려해줘야 하는 조건은 두 가지이다. 3의 배수일 경우 (answer % 3 == 0)와 숫자 3이 들어가 있는 경우 (str(answer).count('3')) 3x 마을은 위 조건의 경우 해당 숫자를 건너뛰기 때문에 +1을 해주면 된다. 주어진 수 n이 0이 될 때까지 1씩 빼보면서 해당 조건을 확인하면서 얼마큼을 건너뛰어야 하는지를 파악할 수 있다. (코드) 더보기 💡 내 코드 def solution(n): answer = 0 ..
[Programmers/Lv. 0] 코딩테스트 입문 Day 22 - dp, 수학, 조건문, 배열 (Python)1. 저주의 숫자 3 (문제 설명, 제한사항, 입출력 예) 3의 배수와 숫자 3을 사용하지 않는 3x 마을 사람들이 있다. 주어진 정수 n을 3x 마을에서 사용하는 숫자로 바꿔서 구하라는 문제이다. (단, 정수 n의 범위는 1 이상, 100 이하) (내가 생각한 풀이 과정) 고려해줘야 하는 조건은 두 가지이다. 3의 배수일 경우 (answer % 3 == 0)와 숫자 3이 들어가 있는 경우 (str(answer).count('3')) 3x 마을은 위 조건의 경우 해당 숫자를 건너뛰기 때문에 +1을 해주면 된다. 주어진 수 n이 0이 될 때까지 1씩 빼보면서 해당 조건을 확인하면서 얼마큼을 건너뛰어야 하는지를 파악할 수 있다. (코드) 더보기 💡 내 코드 def solution(n): answer = 0 ..
2023.06.05 -
1. 숨어있는 숫자의 덧셈 (2) (문제 설명, 제한사항, 입출력 예) 소문자, 대문자, 자연수로만 구성되어 있는 문자열 my_string이 주어질 때, my_string 안에 있는 자연수들의 합을 구하라는 문제이다. 단, 연속된 수는 하나의 숫자로 간주한다. my_string 문자열에 자연수가 없는 경우에는 0을 반환한다. (내가 생각한 풀이 과정) 어려운 코드는 아니지만, 설명이 조금 어려워 사용한 코드도 함께 설명을 하겠다. 우선, 문자열(my_string)을 하나씩 반복하면서 요소(i)가 숫자인지 아닌지를 판별(isdigit() 함수 사용)해준다. 이때, 가장 고려해야 할 점이 "연속된 수는 하나의 숫자로 간주한다"는 점이었다. 즉, 단순히 숫자라고 더하기를 더해주면 안 되고, 이후의 수, 그 이..
[Programmers/Lv. 0] 코딩테스트 입문 Day 21 - 문자열, 사칙연산, 시뮬레이션, 2차원배열, 수학, 배열 (Python)1. 숨어있는 숫자의 덧셈 (2) (문제 설명, 제한사항, 입출력 예) 소문자, 대문자, 자연수로만 구성되어 있는 문자열 my_string이 주어질 때, my_string 안에 있는 자연수들의 합을 구하라는 문제이다. 단, 연속된 수는 하나의 숫자로 간주한다. my_string 문자열에 자연수가 없는 경우에는 0을 반환한다. (내가 생각한 풀이 과정) 어려운 코드는 아니지만, 설명이 조금 어려워 사용한 코드도 함께 설명을 하겠다. 우선, 문자열(my_string)을 하나씩 반복하면서 요소(i)가 숫자인지 아닌지를 판별(isdigit() 함수 사용)해준다. 이때, 가장 고려해야 할 점이 "연속된 수는 하나의 숫자로 간주한다"는 점이었다. 즉, 단순히 숫자라고 더하기를 더해주면 안 되고, 이후의 수, 그 이..
2023.06.04 -
1. 직사각형 넓이 구하기 (문제 설명, 제한사항, 입출력 예) 직사각형 네 꼭짓점의 좌표가 [[x1, y1], [x2, y2], [x3, y3], [x4, y4]] 형태로 담겨 있는 배열이 주어질 때, 주어진 직사각형의 넓이를 구하라는 문제이다. 주어진 직사각형은 2차원 좌표 평면에 변이 축과 평행하게 주어진다. (내가 생각한 풀이 과정) 직사각형의 넓이를 구하는 방법이 "가로 x 세로"인 것은 초등학교 때 배우니까 너무 당연한 것이고, 나는 이 가로와 세로의 길이를 x값의 최대-최소, y값의 최대-최소 식을 이용해서 구하기로 했다. (코드) 더보기 💡 내 코드 def solution(dots): return (max(dots)[0] - min(dots)[0])*(max(dots)[1] - min(do..
[Programmers/Lv. 0] 코딩테스트 입문 Day 20 - 수학, 시뮬레이션, 문자열, 사칙연산 (Python)1. 직사각형 넓이 구하기 (문제 설명, 제한사항, 입출력 예) 직사각형 네 꼭짓점의 좌표가 [[x1, y1], [x2, y2], [x3, y3], [x4, y4]] 형태로 담겨 있는 배열이 주어질 때, 주어진 직사각형의 넓이를 구하라는 문제이다. 주어진 직사각형은 2차원 좌표 평면에 변이 축과 평행하게 주어진다. (내가 생각한 풀이 과정) 직사각형의 넓이를 구하는 방법이 "가로 x 세로"인 것은 초등학교 때 배우니까 너무 당연한 것이고, 나는 이 가로와 세로의 길이를 x값의 최대-최소, y값의 최대-최소 식을 이용해서 구하기로 했다. (코드) 더보기 💡 내 코드 def solution(dots): return (max(dots)[0] - min(dots)[0])*(max(dots)[1] - min(do..
2023.06.03