전체 글

[프로그래머스 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 # 하한..

[프로그래머스 Lv.2] H-Index (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이정렬한 인용 횟수의 배열과 인덱스와 전체 길이를 사용해서 문제를 해결할 수 있다.def solution(citations): citations.sort() # 배열 정렬 idx = 0 length = len(citations) if citations[idx] > length: # 인용 횟수의 최소값이 이미 전체 논문 수를 초과한다면 return ..

(Python) 백준 6588번 - 골드바흐의 추측

문제 링크: https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 문제를 해결하기 위한 기본적인 아이디어는 에라토스테네스의 체이다. 우선 가장 홀수 중 가장 작은 소수인 3부터 시작해서 소수인지 검사하고, 만약 그 수(x)가 소수라면 n-x도 소수인지 체크를 한다. 이 모든 체크가 통과되면 n = x + n-x를 출력하면 된다. import sys MAX_NUM = 1000001 # N의 최대값 arr = [True] *..

[프로그래머스 Lv.2] 의상 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 해시와 수학적인 사고가 필요한 문제이다.우선 해시를 사용해 각 옷의 종류별 개수를 파악한다. 파악한 수를 기반으로 입을 수 있는 총 조합의 개수를 계산한다. 조합의 갯수는 옷의 종류별의 수를 n이라 했을 때, n+1을 곱해주다가 최종적으로 -1을 해주면 된다. n+1을 곱해주는 이유는 n개의 옷과 입지 않을 경우의 1을 더해주는 것이고, 최종적으로 1을 빼주는 이유는 모두 다..

[프로그래머스 Lv.2] 전화번호 목록 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제의 유형은 해시로 되어있으나, 사실 해시를 사용하지 않고 정렬 후 다음 인덱스의 값이 현재 인덱스의 값으로 시작하는지 확인하는 방식으로 공간 복잡도도 낮추고, 시간 복잡도도 낮출 수 있는 방식이다.하지만 이 문제의 유형이 해시이기에 해시를 사용하여 풀이하였다.코드를 읽는 입장에서는 해시 방식이 더 간결하고 명확하게 보이는 것 같다.def solution(phone_book): ..

(JAVA) 거스름돈

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 이 문제를 딱 보았을 때는 DFS로 풀면 되지 않나라는 생각을 가지고 코드를 빠르게 작성했다. 작성 후에 테스트 케이스들도 무난하게 통과하고, 나름대로 엣지 케이스들도 추가하여 테스트를 진행했는데 모두 잘 통과해서 기분 좋게 제출을 하였지만 역시나 한번에 통과할 수 없었다. 필자가 푼 방법으로는 money 배열에 중복된 값이 들어오는 경우에는 실패하는 코드였고, 만약 올바..

트랜잭션이란?

회사에서 최근 업무를 진행하면서 트랜잭션을 사용하는 일이 매우 많다. 현재 MongoDB를 이용하여 개발하고 있는 프로젝트에서 트랜잭션을 사용하고 있는 이유는 아래와 같다. 대용량의 데이터를 벌크로 처리해야하는 경우가 많은데, 이 때 하나의 데이터라도 유효하지 않거나 실행 중 실패가 발생한다면 모든 처리 내용을 롤백 시켜야 함 여러 사람들이 하나의 데이터에 동시에 접근하여 수정을 가하는 경우가 발생할 확률이 기획 상 매우 높음 여러 컬렉션에 위치한 여러 도큐먼트에 대한 삽입이나 수정이 하나의 서비스 로직에서 수행되는 경우가 많음 위와 같은 이유들로 트랜잭션을 진행하였고, 이들은 곧 트랜잭션으로 얻을 수 있는 가장 큰 장점들이다. 이렇게 개발 과정에서 어느 경우에 트랜잭션을 사용하는지는 알고 있지만, 이에..

(JAVA) 올바른 괄호의 갯수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 난이도가 4인 문제임을 생각하면 코드가 매우 단순함을 확인할 수 있다. 코드 자체는 단순한데 문제 풀이를 위한 방법을 생각하는 것이 어려운 문제라고 생각할 수 있다. "(", 열린 괄호로 시작하여 나올 수 있는 괄호 조합들을 하나씩 탐색하는 것을 DFS 알고리즘을 사용하여 풀이하였다. 열린 괄호의 수를 open, 닫힌 괄호의 수를 close라고 하고, 아래와 같은 종료 조건들을 ..