전체 글

[프로그래머스 Lv.2] 삼각 달팽이 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이2단계 문제이기에 코드 자체의 구현 난이도는 어렵지 않으나 풀이를 위한 아이디어를 생각하는 것이 난이도에 비해 어려웠다.아이디어는 피라미드 모형으로 되어있는 예시의 배열을 아래처럼 좌측으로 붙여 정렬을 시키는 것이었다.이렇게 좌측으로 정렬함으로써 배열을 채워나가는 로직을 생각하는 것이 훨씬 쉬워진다.배열의 절반인 삼각형을 이루는 칸을 벗어나거나, 배열에 이미 값이 채워진 경우 채워가는 ..

[프로그래머스 Lv.2] 행렬 테두리 회전하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77485?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이우선 아래와 같이 우측으로 행렬의 테두리를 회전하도록 풀이해 보았다. 하지만 아래 풀이대로 진행하면 시간 초과가 발생한다. rows와 columns가 100이고, queries도 10000 이하이므로 풀이 로직 상에서는 시간 초과가 발생하지 않을 것이라고 생각하였으나 시간 초과가 발생하여 상당히 당황스러웠었다.시간 초과 발생 코드import copydef ..

[프로그래머스 Lv.2] 교점에 별 만들기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87377 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2의 문제답게 크게 어렵지 않게 풀 수 있는 문제라고 생각한다. 아래 사진의 두 일차방정식의 교점을 구하는 공식을 알고 있기 때문에, 문제에 이를 적용함으로써 교점을 구하고 이를 사용하여 교점의 위치에 *을 출력하면 해결이 된다.def solution(line): x_min = y_min = float('inf') # 그려야할 직사각형의 시작 위치를 알기 위한 최소값 x..

[프로그래머스 Lv.3] 풍선 터트리기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이dp에서 사용하는 메모이제이션을 통해 최솟값을 저장하는 방법으로 문제를 풀이하였다. 이 문제를 풀이하긴 위해서 풍선을 마지막까지 남길 수 있는 조건이 무엇인가를 알아야 한다.문제의 조건을 간단하게 요약하면 남기려고 하는 풍선의 좌우에 위치한 남은 풍선 중 하나라도 크기만 하면 된다는 것이다.그렇기에 남기려고 하는 풍선의 좌측에 남은 풍선들의 최솟값이나 우측에 남은 풍선들의 최솟값 중 하..

[프로그래머스 Lv.3] 이중우선순위큐 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이Python의 내장 모듈인 heapq를 사용하여 문제를 풀이할 수 있다. heapq는 이진트리 기반의 최소 힙 자료구조를 제공하는 내장 모듈이다.문제 풀이에서 사용한 heapq의 메서드들을 간단히 설명한 후 코드를 통해 전체적인 풀이를 설명하겠다.heapq.heappush(list, n): 최소 힙(list)에 n을 삽입, 이진트리에 n을 삽입하는 것이므로 O(logN)의 시간 복잡도를..

[프로그래머스 Lv.3] 네트워크 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이deque를 사용한 BFS로 문제를 풀이하였다. 일반적인 BFS 문제를 풀이하는 것처럼 visited라는 배열을 통해 네트워크를 구성할 노드의 방문 여부를 확인하여 전체 노드 순회를 완료하였을 때 몇 개의 네트워크를 생성할 수 있는지 확인하면 된다. from collections import dequedef solution(n, computers): answer = 0 ..

[프로그래머스 Lv.3] 정수 삼각형 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이DP 문제이기에 문제 해결을 위한 규칙을 찾아서 점화식을 세우는 것이 가장 중요하다.삼각형의 위에서부터 아래로 내려오면서 숫자를 더하여 각 위치에 들어갈 수 있는 최댓값을 얻어내고, 이를 저장하는 방식을 반복하여 삼각형을 모두 채운다. 가장 아래층에서의 최댓값이 구하고자 하는 답이 된다.def solution(triangle): _triangle = [] # 각 위치에서의 최대값..

[프로그래머스 Lv.3] 최적의 행렬 곱셈 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12942 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이dp 문제이다. 따라서 문제 상황을 해결하기 위한 점화식을 세워야 한다.일반적인 상황을 가정하고 이 상황을 해결하는 과정을 생각해 보면서 알맞은 점화식을 유도해 보자. 4개의 행렬 M1, M2, M3, M4가 있으며,  arr라는 배열은 arr[i][j]일 때, i 행렬부터 j 행렬까지의 곱을 수행할 때의 계산 수의 최솟값이라고 가정하자. 이런 상황에서 M1, ((M2, M3), M4)..

(Python) 백준 1912번 - 연속합

문제 링크: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 Dynamic Programming 문제답게 코드 구현보다는 문제 해결을 위한 아이디어를 생각하는 것이 더 어려운 문제이다. 문제 해결을 위한 아이디어는 다음과 같다. 우선 해당 인덱스까지의 최대값을 담을 배열을 선언한다. 그 후 처음부터 순회하며 해당 인덱스까지의 최대값을 계산하고 이를 저장한다. 해당 인덱스까지의 최대값은 이전 인덱스에서의 최대값 또는 현재 인덱스의 값이 된다. 최종적으..

[프로그래머스 Lv.3] 입국심사 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이전형적인 이진탐색 문제이다. 현재 시간으로 모든 사람의 입국 심사를 진행할 수 있으면 상한선을 현재 시간으로 조절하고, 만약 현재 시간으로 모든 사람의 입국 심사를 진행할 수 없다면 하한선을 현재 시간 + 1로 조절한다. 이런 과정을 하한선이 상한선과 동일하거나 더 커진 순간까지 반복하면 이 값을 구할 수 있다. def solution(n, times): start = 1 # 하한..