알고리즘/문제풀이

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

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

    투포인터를 이용한 부분합 문제이다. 이전에 비슷한 유형을 풀이했었는데, 시간이 지나니까 생각이 나지 않았고 그냥 흐릿하게 이건 투포인터로 푸는 것 같다 라는 느낌이 들었다.그래서 투포인터 부분합을 그대로 갔다가 사용했는데 합격이 나왔다.암튼 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는 큐에 해당 점을 넣고 인접한 모든 점을 탐색한다. 그래서 최소가 아니라고 생각이 들었다.위의 그림에서 첫 번째 예시와 두 번째 예시는 다르게 카운팅 되기때문에 ..

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

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

    스택을 활용한 문제이다. 처음에는 그냥 조합을 이용해서 풀었는데 예상했지만 역시나 시간초과가 발생했다. 저번주에 필기시험이 있어서 잠시 코테를 쉬었더니 알손실이 왔다. 그래서 바로 풀지 못했다. (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..

    [프로그래머스] 순위 검색
    알고리즘/문제풀이

    [프로그래머스] 순위 검색

    효율성 문제가 어려웠던 ... 역시 카카오 문제라고 생각했던 문제이다. 보면 단순 구현 같은데 생각보다 깊은 개념을 요구하는 문제였다. 그래서 나는 효율성 못품1 문제 설명info로 지원자의 정보가 주어지면 다음과 같이 나타낼 수 있다.이 지원자들을 query변수로 받은 조건으로 필터링 하여 확인한다.다음과 같이 진행한다.* "java and backend and junior and pizza 100" : java로 코딩테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 100점 이상 받은 지원자는 1명 입니다.* "python and frontend and senior and chicken 200" : python으로 코딩테..

    [프로그래머스] 후보키
    알고리즘/문제풀이

    [프로그래머스] 후보키

    그냥 구현이 까다로웠던 문제이다... 이렇게 더럽게 풀어도 되나 싶었는데 그냥 더럽게 푸는게 맞았던 단순히 구현력을 물어보는 문제 같았다.1. 문제 설명테이블이 다음과 같이 있을때, 각각의 row를 유일하게 식별해줄 key를 고르는 문제이다.이때 key는 2가지 조건을 만족해야 하는데 그 조건은 다음과 같다.* 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.* 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.두 가지를 쉽게 직역하면 다음과 같다.* 유일성 -> 하나의 row를 유..

티스토리툴바