분류 전체보기

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 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 배열에 중복된 값이 들어오는 경우에는 실패하는 코드였고, 만약 올바..

    개발/CS

    트랜잭션이란?

    회사에서 최근 업무를 진행하면서 트랜잭션을 사용하는 일이 매우 많다. 현재 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라는 배열에 저장한다. 시..

티스토리툴바