코딩하는 해커

[Programmers] 스택/큐 - 기능 개발

본 문제를 읽어보면 우선순위에 따라서 작업의 진도가 적힌 정수 배열 progresses가 존재한다고 한다.읽자마자 이 문제는 큐 자료구조를 사용하면 편하게 구현할 수 있을 것이라고 생각이 들었다.큐 자료구조의 경우, 우선순위가 존재하는 작업이 있을 때 유용하게 활용할 수 있는데, 먼저 들어온 값이 먼저 나가는 선입선출의 개념을 포함한다. 파이썬에서 큐 자료구조를 쉽게 활용하기 위해서는 collections 라이브러리의 deque()을 사용하면 된다.문제를 조금 더 읽어보면 각 작업에 해당하는 개발 속도가 적힌 정수 배열 speeds가 주어진다고 적혀 있다.이를 참고하여 주어진 작업 진도에 대한 정수 배열 progresses와 개발 속도에 대한 정수 배열 speeds를 deque 객체로 새로 초기화하자.f..

[Programmers] BFS/DFS - 타겟 넘버

며칠 동안 하루에 평균 2문제씩 풀어 Level 1 수준의 문제는 모두 풀었다.이제 본격적으로 Level 2 수준으로 난이도를 올려볼 것인데 BFS/DFS는 코딩 테스트에서 빈번하게 나오기 때문에 반드시 마스터해야 한다. 따라서 대부분의 해당 유형의 문제는 BFS로도 DFS로도 다 풀 수 있는데, 학습을 위해서 해당 카테고리의 문제는 두 가지 방법 모두 사용해서 풀어볼 예정이다. 풀이 - BFS 버전먼저 BFS를 사용하여 풀어보자. 너비 우선 탐색이니 값이 주어지면 아래와 같이 다 탐색해 보는 것을 머릿속으로 상상할 수 있다.그리고 원래 정석적인 그래프 구조에서의 BFS라면 visited 같은 것을 남겨서 재방문하지 않도록 표시를 해줘야 하는데 단순히 1차원 형태의 배열이 주어지니 이 부분은 생략할 수 ..

[Programmers] 해시 - 전화번호 목록

본 문제를 풀 때, 해시 카테고리에 있었으므로 먼저 딕셔너리를 사용해야 한다는 것은 인지하고 시작하였다.먼저, 문제를 읽어보면 한 번호가 다른 번호의 접두어인 경우가 있다면 false를 반환하고, 아니라면 true를 반환하면 된다.조금 더 쉽게 생각하면, 문제에서 주어진 구조대 번호는 119이고 지영석의 번호는 11 9552 4421이므로 지영석의 번호는 구조대의 119와 일치한다. 따라서 false를 반환해야 하는 것이다. 먼저 전화번호부를 딕셔너리로 새로 만들어주자.딕셔너리의 경우 key값을 안다는 가정하에 자료 검색에 대한 시간 복잡도는 상수 시간 O(1)이 걸리므로 아주 빠르게 접근이 가능하다.여기서 key에 전화번호를, value는 임의의 값을 아무거나 초기화하면 된다.전화번호라서 value에 ..

[Programmers] 완전 탐색 - 모의고사

문제를 읽으면서 가장 먼저 한 것은 1, 2, 3번 수포자가 정답을 찍는 방식에 있어서 패턴을 먼저 찾으려고 하였다.먼저, 1번 수포자의 경우 1, 2, 3, 4, 5라는 패턴이 반복되고,다음으로, 2번 수포자의 경우 2, 1, 2, 3, 2, 4, 2, 5라는 패턴이 반복된다.마지막으로, 3번 수포자의 경우 3, 3, 1, 1, 2, 2, 4, 4, 5, 5라는 패턴이 반복되는 것을 확인할 수 있다. 코드를 작성하기 전에 파악한 이 패턴을 보기 쉽게 아래와 같이 정리하였고, 각각 몇 개의 수가 반복되는지 # 뒤에 적어 두었다.def solution(answers): answer = [] # 1 2 3 4 5 / 1 2 3 4 5 / ~ # 5 # 2 1 2 3 2 4 2 5 / 2 1 ..

[Programmers] 완전 탐색 - 최소 직사각형

문제를 읽어보면 명함을 넣을 지갑의 크기를 정해야 하는데, 명함의 크기가 제각각이라 모든 크기의 명함을 수납할 수 있는 것을 찾아야 한다. 주어지는 정보는 가로의 길이와 세로의 길이가 주어지기 때문에 가로 길이 중 제일 큰 값과 세로 길이 중 제일 큰 값을 선택하면 될 것 같다는 1차원적인 생각을 떠올릴 수 있었다. 그래서 제일 먼저 모든 가로의 값과 세로의 값을 리스트에 추가하고, 각각의 최댓값을 저장하였다.all_width, all_height = [], [] for i in range(len(sizes)): all_width.append(sizes[i][0]) all_height.append(sizes[i][1]) max_width, max_height = max(all..

[Programmers] 정렬 - K번째 수

K번째 수 문제는 읽자마자 파이썬의 리스트 인덱싱, 슬라이싱으로 풀면 금방 풀릴 것이라고 확신했다.먼저 commands로 받은 i번째부터 j번째까지 슬라이싱하여 새 리스트에 저장하는 방식을 택했다.commands는 2차원 리스트 형태이므로 전체 commands의 수만큼 순회하면서 0번(i에 해당)과 1번(j에 해당) 원소를 불러와 array를 슬라이싱해 주고 해당 리스트를 새로운 리스트에 추가해 준다.다음으로 나중에 몇 번째 숫자가 필요한지도 필요한데, 나중에 일일이 접근하기는 번거로우니 순서대로 find라는 새로운 리스트에 또 추가해준다.def solution(array, commands): sorted_arr = [] find = [] for i in range(len(comm..

[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)의 시간 복잡도가 필요하여 시간 초과로 실패한다. 결국 코드가 조금 길어지더라도 정석적인 ..