본문 바로가기

알고리즘135

[Python] 프로그래머스 : 신고 결과 받기 https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 문제 풀이 딕셔너리 result는 키와 값을 다음과 같이 가진다. key (사용자 id) : value [[신고한 유저, ], 신고받은 횟수, 받을 메일] result를 이용해 전체적인 값을 정리했고 이후 확인하는 작업만 하면된다. set의 특징을 이용해서 중복 신고를 없애서 신고들을 걸렀다. 느낀점 코딩 테스트를 대비해서 파이썬으로 시작해보았다. 아직 .. 2022. 6. 18.
[알고리즘] 배낭 채우기 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 위의 문제는 대표적인 배낭 채우기 문제이다. 찾아보니 배낭 채우기 문제는 두 가지 유형으로 나뉜다고 한다. 물건(보석)을 자를 수 있을 때의 "Fractional Knapsack"과 자를 수 없을 때의 "0-1 Knapsack Problem"로 나뉜다고 한다. 자를 수 있는 경우는 보통 그리디 알고리즘으로 해결한다고 한다. 이 글에서 다루는, 그리고 보통 많이 다루는 배낭 채우기 알고리즘은 자를 수 없는 경우이다. 배낭 채우기 문제를 푸는 방법은 여러 가지가 있다. 모든 .. 2021. 11. 24.
[알고리즘] 가장 긴 증가하는 부분수열(LIS) ※ 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)이란? 부분 수열 중에서 각 원소가 이전 원소보다 큰 부분 수열 중에서 가장 긴 것! 예를 들어서, { 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 때, 증가하는 부분 수열은 { 2, 5 }, { 1, 4, 3} 등이 있지만 LIS는 { 2, 5, 7, 8 } 이다! 알고리즘은 시간복잡도에 따라서 2가지가 있다. ( O(N^2)과 O(N log N) ) 첫 번째 방법은 다이나믹 프로그래밍을 통한 방법이다. 시간 복잡도는 O(N^2) code#1 1 2 3 4 5 6 7 for (int i = 0; i arr[i]; } dp[0] = arr[0]; int idx = 0; for (int i = 1; i 2021. 6. 23.

티스토리툴바