전체 글

[프로그래머스 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라고 하고, 아래와 같은 종료 조건들을 ..

(JAVA) 올바른 괄호의 갯수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 난이도가 4인 문제임을 생각하면 코드가 매우 단순함을 확인할 수 있다. 코드 자체는 단순한데 문제 풀이를 위한 방법을 생각하는 것이 어려운 문제라고 생각할 수 있다. n개 이전의 괄호쌍으로 만들 수 있는 개수를 활용하는 Dynamic Programming을 사용하여 풀이하였다. 예를 들어 괄호쌍 2개와 3개를 사용해 만들 수 있는 전체 올바른 괄호쌍의 개수를 계산해 보겠다. 우선..

(JAVA) 양과 늑대

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 class Solution { int[] gInfo; // DFS에서 사용할 노드의 정보 int[][] gEdges; // DFS에서 사용할 간선의 정보 int maxValue = 0; public int solution(int[] info, int[][] edges) { gInfo = info; gEdges = edges; boolean[] isVisited = new bool..

(JAVA) 합승 택시 요금

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최소거리비용 알고리즘으로 유명한 다익스트라 알고리즘을 사용한 풀이이다. 전체적인 문제 해결 방법은 아래와 같다. mat이라는 이름의 인접 행렬을 각 지점 간의 금액을 담고 있는 fares 배열을 사용하여 생성한다. mat을 바탕으로 두 사람이 합승하여 출발 지점부터 다른 모든 정점까지 가는 최소 비용을 다익스트라 알고리즘을 사용하여 알아내고 이를 both라는 배열에 저장한다. 시..