코딩하는 해커

[Programmers] 탐욕법(Greedy) - 체육복

그리디 유형은 코딩 테스트에서 가장 빈번하게 나오는 유형 중 하나이다. 그중에서 가장 쉬운 문제 중 하나인 체육복 문제를 풀어보도록 하자.문제를 읽어보면 일부 학생이 체육복을 도난당했다고 한다.학생은 총 n명이 있는데 1번 학생부터 n번 학생까지 존재한다. (이때, 학생의 수는 2 이상이다.)도난당한 학생들은 여벌의 체육복을 가져온 학생들한테 체육복을 빌릴 수가 있는데, 조건은 도난당한 바로 앞이나 뒤에 있는 학생에게만 빌릴 수 있다.예를 들어 총 7명의 학생이 있다고 가정해 보자. 이때, 3번 학생의 체육복이 도난당했다면 3번 학생은 1번 학생이나 7번 학생에게는 빌릴 수 없고 오직 2번 혹은 4번 학생에게만 옷을 빌릴 수 있다.그런데 문제 제한사항에 "여벌 체육복을 가져온 학생이 체육복을 도난당했을 ..

[Programmers] 해시 - 포켓몬

풀이문제를 읽어보면 홍 박사는 총 N마리의 포켓몬을 갖고 있고, 여기서 최대 N/2마리, 절반까지 가져가도 좋다고 하였다.즉, 최대 절반을 가져갈 수 있는 케이스가 있다는 것을 알아차릴 수 있다. 문제 설명을 보면서 문제를 조금 더 이해해 보자.예를 들어 [3, 1, 2, 3]이라는 입력이 들어온다면 총 4마리의 포켓몬이 있다는 것이다. 여기서는 최대 2마리까지 가져갈 수 있다.2마리를 어떻게 고를 수 있을까? [3,1], [3,2], [3,3], [1,2], [1,3], [2,3] 총 6가지의 조합을 만들 수 있다. 여기서 [3,3]은 동일한 종류의 포켓몬 2마리를 묶은 케이스인데, 문제에서는 최대한 다양한 종류의 포켓몬을 가지고 싶다고 하였다.그러면 [3,1]과 [1,3], [3,2]과 [2,3]은 ..

[Programmers] 스택/큐 - 같은 숫자는 싫어

이번에 풀어볼 문제는 프로그래머스의 스택/큐 부분에 있는 '같은 숫자는 싫어'이다.간단하게 설명하면 1 1 2 3 4 이런식으로 값이 존재하면 1 2 3 4처럼 연속된 숫자를 제외하고 반환하면 되는데, 가장 먼저 넣은 것이 가장 앞에 들어가서 가장 최근에 들어간게 가장 마지막에 존재하는 스택을 잘 활용하면 쉽게 풀 수 있다. 먼저 입력받은 배열을 하나씩 순회해야 한다.for i in arr: 다음으로, 가장 초기값은 중복된 값이 없을 테니 정답으로 쓸 새로운 리스트에 값이 없다는 것과 동일하다. 이 생각 그대로 코드를 짜면 다음과 같이 작성할 수 있다.answer = [] for i in arr: if not answer: answer.append(i) 이제 중복 검..

[Programmers] 해시 - 완주하지 못한 선수

오늘은 프로그래머스의 알고리즘 고득점 Kit의 가장 첫 번째 쉬운 문제인 완주하지 못한 선수 문제를 풀어보았다.파이썬으로 문제를 푼다면, 해시 카테고리의 문제들은 딕셔너리로 풀 수 있는데, 해시(hash)의 가장 큰 장점은 배열 혹은 리스트와 다르게 자료의 검색 및 접근에 있어서 시간 복잡도가 O(1)로 매우 빠르게 동작한다는 것이다. 오랜만에 코딩을 하다 보니 처음에는 사람 수를 초기화하기 위해서 첫 번째 for문 안에서 dict[i] = participant.count(i)를 사용하였는데 이 경우, 결국 초기에 participant를 순회하는 과정과 더불어 한 번 더 리스트 안에서 검색을 하기 때문에 O(N^2)의 시간 복잡도가 필요하여 시간 초과로 실패한다. 결국 코드가 조금 길어지더라도 정석적인 ..