알고리즘

    [프로그래머스] 숫자의 표현
    알고리즘/문제풀이

    [프로그래머스] 숫자의 표현

    투포인터를 이용한 부분합 문제이다. 이전에 비슷한 유형을 풀이했었는데, 시간이 지나니까 생각이 나지 않았고 그냥 흐릿하게 이건 투포인터로 푸는 것 같다 라는 느낌이 들었다.그래서 투포인터 부분합을 그대로 갔다가 사용했는데 합격이 나왔다.암튼 TMI였다.1. 문제 설명Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.1 + 2 + 3 + 4 + 5 = 154 + 5 + 6 = 157 + 8 = 1515 = 15자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요. 2. 어..

    [프로그래머스] 방금 그곡
    알고리즘/문제풀이

    [프로그래머스] 방금 그곡

    1. 문제 해설문제 해설은 어렵지 않았다. 하지만,, 생각보다 조건이 까다로웠고 그 조건을 매끄럽게 해결하는 것이 어려웠다. 실제로 다른 블로그의 답을 보고서도 이.. 예외케이스가 어떻게 이 2줄로 해결되지..? 라고 몇 시간이나 생각을 계속 했다.문제는 이렇다. musicinfos를 인자로 받으면 ,를 기준으로 하나씩음악 재생 시작 시간, 종료 시간, 곡명, 곡의 악보 이다.여기서 구해야 할 것은 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환하는 것이다.2. 어려웠던 점2-1. 예외사항일단 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환하는 것 자체가 예외사항이 나에게는 조금 까다로웠다.재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도..

    알고리즘/문제풀이

    [프로그래머스] 구명보트

    오늘 리뷰할 문제는 구명보트이다. 대표적인 그리디 기출문제인데, 대부분 그리디는 정렬을 먼저 하고 시작하게 된다.1. 문제 해설무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모..

    [프로그래머스] 게임 맵 최단거리
    알고리즘/문제풀이

    [프로그래머스] 게임 맵 최단거리

    이 문제는 전형적인 BFS문제이다. BFS로 푸는건 맞는데 내가 BFS를 모른다는 생각이 들었다. 왜냐면 문제에서 최소 거리를 구하라고 했는데, BFS 자체가 왔던 길을 다시 되돌아 가지 않기 때문에 최소 거리가 보장된다는 것이다.1. 문제 해설이러한 지도가 있다고 하면, 다음과 같은 경로가 있을 수 있다. 이때 하단의 경로 중에서 첫 번째 경로가 가장 최소의 경로가 된다.이때 지나가는 경로의 가중치를 모두 1이라고 한다면 최소 가중치의 합을 구하면 된다.2. 어려웠던 점1) 최소길이를 BFS로BFS는 완전탐색의 일종인데, 내가 생각했던 BFS는 큐에 해당 점을 넣고 인접한 모든 점을 탐색한다. 그래서 최소가 아니라고 생각이 들었다.위의 그림에서 첫 번째 예시와 두 번째 예시는 다르게 카운팅 되기때문에 ..

    알고리즘/개념

    [개념 정리] 파이썬 set

    파이썬에서 사용하는 자료구조 set에 대해 알아볼 것이다. 매번 set자료구조를 사용하는 일은 많은데, 효율성 있게 활용해야 하고 기억해두고 싶어서 포스팅 한다. 1. Set파이썬에서 set은 집합 자료형으로 사용된다. 주된 특징으로는 순서를 보장하지 않고, 중복된 원소를 포함하지 않는다. 특징으로 유추하면 set은 해시테이블로 구현되어 있음을 생각해볼 수 있다. 순서를 보장하지 않는다.중복된 원소를 포함하지 않는다.set() 생성자 혹은 {}를 이용해 생성한다.mutable 객체이다.2. 교집합, 합집합, 차집합1) 교집합교집합은 말 그대로 두개의 set에 중복으로 존재하는 원소를 말한다. s1 = set([1, 2, 3, 4, 5])s2 = set([4, 5, 6, 7, 8])# 교집합 메서드 int..

    [개념정리] 파이썬 다중 집합의 교집합, 합집합
    알고리즘/개념

    [개념정리] 파이썬 다중 집합의 교집합, 합집합

    코테 연습할때마다 잊을만 하면 나오는 다중집합이다. 굳이 몰라도 되지만, 모른채 쓰려면 머지소트를 구현해야 하는 굉장한 번거로움이 있기때문에 알아두는게 좋을 것 같아서 포스팅 한다.1. 다중 집합이란?기존에 파이썬에서 집합은 보통 set으로 사용한다. 그리고, set의 특징은 중복된 원소를 허용하지 않는다는 점이 있다.하지만, 중복된 원소를 포함하기 위해 사용되는 개념이 다중집합이고 개념만 다중집합이며 실제로는 리스트에 담아서 나타낸다.a = [1,2,2,3,4,5]b = [1,1,2,3,4,6]일반 집합의 합집합: [1,2,3,4,5,6]일반 집합의 교집합: [1,2,3,4]다중 집합의 합집합: [1,1,2,2,3,4,5,6] 다중 집합의 교집합: [1,2,3,4]이렇게 된다. 나는 처음에 다중 집합의..

    [프로그래머스] 큰 수 만들기
    알고리즘/문제풀이

    [프로그래머스] 큰 수 만들기

    스택을 활용한 문제이다. 처음에는 그냥 조합을 이용해서 풀었는데 예상했지만 역시나 시간초과가 발생했다. 저번주에 필기시험이 있어서 잠시 코테를 쉬었더니 알손실이 왔다. 그래서 바로 풀지 못했다. (TMI..)아무튼 내가 스택을 활용한 풀이에 약한 것 같다. 문제를 보고 스택을 활용한 풀이라는 것은 이해가 갔지만, 막상 적용이 안됐다.맨 뒤의 원소를 비교하는 것은 for루프를 돌면서 while루프를 돌리면 되는데, 왜 생각이 안났을까...? 아무튼 문제 해설을 시작한다.이 문제와 유사하게 스택을 활용하는 문제들을 뽑아놨다. 이번주 주말에 코테보기 전에 꼭 풀어봐야겠다.큰 수 만들기, 괄호변환, 같은숫자는 싫어, 나누어 떨어지는 숫자, 짝지어 제거하기, 문자열 압축1. 문제 설명number로 숫자가 문자열 ..

    알고리즘/문제풀이

    [프로그래머스] H-Index

    저번에 다리를 지나는 트럭이랑 비슷한 느낌이다. 문제 설명이 애매모호한.1. 문제 설명나는 처음에 문제를 잘못이해했다. 배열의 원소 하나하나를 정답이 되는 인용횟수중 하나라고 생각하고 풀었다.근데 그게 아니었다. 그냥 1부터 세면 된다. [3,4,9,10] 배열에서 1번 이상 인용된 논문은 4개다. 그리고 1번 이하로 인용된 논문의 개수는 4개 이하이다.1은 H-Index의 후보가 될 수 있다.이 문제에서는 최대값을 구하면 된다.2. 어려웠던 점문제 해설이 그냥 어려웠다.. 3. 풀이처음에 이렇게 풀이했다. 아마 나처럼 문제 잘못 이해한 사람들은 다 이렇게 풀었을 것 같다.def solution(citations): citations.sort() result = [] for i in ci..

티스토리툴바