본문 바로가기
반응형

알고리즘13

[프로그래머스] 스택/큐 - 기능 개발(파이썬 문제풀이) 문제 링크 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr deque 함수를 통해 큐 자료구조로 문제를 풀이했습니다. 다른 분들이 풀이하신 것은 대부분 각 기능의 개발 시간을 배포 날짜마다 구하는 코드가 많았는데, 저는 큐에 먼저 모든 기능을 개발하는데 걸리는 시간을 입력해두었습니다. 큐에 자료가 없을 때까지 반복문을 이어가며 큐의 제일 첫 번째 항목이 현재 기능의 개발 시간보다 적게 걸리면, 함께 배포할 수 있는 것으로 판단했습니다. 문제 풀이(파이썬) from collections import de.. 2022. 3. 12.
[프로그래머스] 완전탐색 - 모의고사(파이썬 문제풀이) 문제 링크 단순하게 문제 조건대로 구현해서 풀었습니다. repeat 이라는 2차원 배열에 문제에서 제시된 1번, 2번, 3번 학생의 반복 규칙을 넣어두고 chk 라는 함수를 만들어 각 학생별 점수를 확인하도록 했습니다. 학생별 점수를 res 배열에 넣어두고 가장 큰 점수를 구해 res에서 가장 큰 점수의 학생 번호를 answer 리스트에 추가한 뒤 리턴하도록 코드를 작성했습니다. 저는 chk 함수에서 idx == len(tmp) 라는 조건으로 학생의 반복 규칙을 회전하도록 구성했는데, 이 부분을 나머지 연산으로 대체한다면 각 학생별로 chk 함수를 돌릴 필요없이 for 문 한번으로 해결할 수 있겠습니다. 문제 풀이(파이썬) def chk(idx, tmp, answers): score = 0 for i i.. 2021. 4. 2.
[프로그래머스] 해시 - 베스트앨범(파이썬 문제풀이) 문제 링크 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 딕셔너리 두 개를 사용해 문제를 풀어봤습니다. genre_score : 각 장르별 속한 노래의 총 점수를 저장하는 딕셔너리 chk : 노래의 고유번호를 key 값으로 사용하고, value로 [해당 노래가 속한 장르의 점수, 해당 노래의 개별 점수]를 저장 이제 문제에 제시된 노래 수록 기준에 맞추어 정렬을 하고 추출을 하면 되겠습니다. for문으로 두 딕셔너리의 값을 설정한 뒤 sorted를 이용해 딕셔너리를 정렬했습니다. 먼저 수록 기준 1번을 맞.. 2021. 4. 2.
[프로그래머스] 해시 - 위장(파이썬 문제풀이) 문제 링크 코딩테스트 연습 - 위장 programmers.co.kr 간단한 수학 공식을 이용해 문제를 풀이했습니다. 각 옷의 종류마다 몇 개의 옷을 가지고 있는지 구하고 그 수를 모두 곱하면 그 수들을 조합한 경우의 수가 나오게 됩니다. 하지만 이렇게 계산하면 해당 옷의 종류가 포함되지 않았을 때의 경우의 수가 빠지게 되므로 (해당 옷의 종류 + 1)을 해준 값을 곱해야 원하는 결과가 나옵니다. 또 문제에서 반드시 한 개의 의상을 착용해야한다고 했으므로 모두 안입었을 경우의 수 하나를 최종 값에서 빼주어야 합니다. 다른 분들 코드를 보니 딕셔너리를 사용할 때 분기문으로 해당 키값이 현재 딕셔너리에 포함되어있나 확인하는 코드를 넣었는데, 저는 딕셔너리의 내장 함수 get을 이용하여 따로 분기 처리를 하지 .. 2021. 4. 1.
[프로그래머스] 해시 - 완주하지 못한 선수(파이썬 문제풀이) 문제 링크 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 간단하게 딕셔너리를 이용해 풀이를 해보았습니다. 파이썬에서는 딕셔너리로 해시 자료구조(키와 값을 쌍으로 갖는 자료구조)를 사용할 수 있습니다. 먼저 딕셔너리 변수를 하나 만들고, 참여자들의 수 만큼 +1 해주었습니다. 동명이인이 있을 수 있으므로 단순히 참여자가 있으면 1, 없으면 0으로 풀면 테스트 케이스 3번을 통과하지 못합니다. 마찬가지로 완주자를 for문으로 탐색하며 딕셔너리에서 -1을 해주면, 완주를 한 경우 딕셔너리에서 .. 2021. 3. 31.
[프로그래머스] DFS/BFS - 네트워크(파이썬 문제 풀이) 문제 링크 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 무방향 그래프가 computers로 주어집니다. 처음에는 그래프에서 1로 상하좌우가 묶여있는 덩어리들의 수를 세면 될 것이라고 생각했습니다. 그 결과.. 15점이 나왔습니다. def DFS(x, y, n, computers): computers[x][y] = 0 for k in range(4): xx = x + dx[k] yy = y + dy[k] if 0 2021. 3. 18.
[프로그래머스] DFS/BFS - 타겟 넘버(파이썬 문제 풀이) 문제 링크 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 단순하게 DFS를 이용해 문제를 풀이했습니다. 상태 트리 각 노드의 레벨이 numbers의 요소를 하나씩 탐색하는 인덱스가 되고 해당 인덱스를 더할 때, 뺄 때 두가지의 경우로 가지를 내려나갑니다. 레벨이 numbers의 길이만큼 도달하면 탐색을 종료하고 지금까지 연산한 값이 target 값이라면 카운팅을 추가합니다! 문제 풀이(파이썬) def DFS(L, sum, numbers, target): .. 2021. 3. 18.
[프로그래머스] 정렬 - H-Index(파이썬 문제 풀이) 문제 링크 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 프로그래머스 고득점 Kit 정렬의 마지막 문제 H-Index 입니다. 문제에 주어진 조건대로 우선 구현을 하고 효율성을 높여보려고 했는데, 구현하고 제출하니 통과가 되어버렸네요..! 저는 아래와 같은 방법으로 구현했습니다. 1. 인용된 논문 수의 최대값 만큼 리스트를 하나 만든다. 2. 1부터 인용된 논문 수의 최대값까지 반복문을 돌며 1이상 논문은 몇개, 2이상 논문은 몇개, 3이상 ... 을 반복한다. 3. 각 인덱.. 2021. 3. 18.
[프로그래머스] 정렬 - 가장 큰 수(파이썬 문제 풀이) 문제 링크 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 주어진 정수를 이어 붙여 가장 큰 수를 만들어내는 문제입니다. Level2 치고는 체감 난이도가 꽤 높았던 문제인 것 같습니다! 우선 입력 데이터인 numbers의 최대 길이가 100,000인 것으로 보아 상태 트리를 이용한 모든 경우의 수를 조합하는 방법은 아니라고 생각했습니다. 1. 파이썬에서 문자형으로 된 숫자를 비교할 때 자릿수에 상관없이 앞자리가 큰 수가 큰 것이다는 점을 활용해.. 2021. 3. 18.
반응형