개발log

완전탐색 part에서는 크게 까다로웠던 문제는 없었던 것 같다. 이번 part에서는 다른 사람의 풀이 중 인상 깊었던 풀이가 있던 문제에 대해서 리뷰 하겠다. [문제 설명] 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 먼저 이 문제가 요구하는 게 무엇이고, 어떻게 접근할 지 생각해보자. 해당 문제는 '주어진 숫자들을 조합하여 만들 수 있는 소수의 개수를 반환' 하는 것을 요구하고 있다. 그렇다면 이를 어떻게 풀어나가야할까? 해당 문제는 최적의 방법으로 소수의 개수를 구할 수 없다. 즉, 주어..

오랜만의 문제 리뷰인 것 같다. 오늘은 고득점 kit 정렬 part에서 좀 까다로웠던 문제에 대해 다뤄보겠다. [문제 설명] 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 먼저, 이 문제가 어떤 것을 요구하는지 어떤 방식으로 접근해야 되는지 살펴보자. 문제는 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하기를 요구하고 있다. 그렇다면 이를 어떻..

힙 파트를 푸는 도중 난이도가 좀 있는 문제가 있어 기록하려 한다. 내가 풀었던 방식에 대해 설명하고 내가 막히고 잘못 풀었던 부분에 대해서도 설명하겠다. [문제 설명] 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 먼저, 이 문제가 요구하는 것이 무엇이고 이를 어떻게 접근해야 되는지 파악해보자. 일단 이문제는 '작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지'를 원하고 있다. 하지만 이 요구사항만 본다고 바로 접근 방식을 파악할 수 있는 것은 아니다. ..

그다음으로 푼 문제들은 스택/큐 파트 부분이다. 이 부분에서 좀 까다로웠던 문제 하나를 소개하겠다. 내가 풀었던 방식에 대해 설명하고 다른 사람의 풀이 중 괜찮은 풀이 또한 설명하겠다. [문제 설명] 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 좀 까다로웠던 문제는 다리를 지나는 트럭이다. 일단 이 문제가 요구하는 게 무엇이고 어떻게 접근해야 되는지 알아보자. 먼저, 이문제가 요구하는 것은 무게, 다리의 길이, 다리의 최대 수용 트럭 무게가 주어진 상황에서 트럭이 순서대로 최단 ..

몇개의 기출들을 푼 뒤 이제 프로그래머스 코딩테스트 고득점 kit를 유형별로 모두 풀어보려 한다. 풀면서 괜찮은 문제나 다른 사람들의 괜찮은 풀이방식이 있다면 소개하겠다. 일단 먼저 해시(hash)파트이다. 해시 파트 같은 경우 문제들이 막 괜찮은 편은 아니라고 느껴서 (해시로 풀지않고 다른 방식으로 구현하는 것이 더 좋은 문제들도 있었음), 몇개의 문제에서의 풀이 및 새롭게 알게된 툴(?)들에 대해서 소개하고 다른 사람의 풀이 중 괜찮은 것들에 대해서만 소개하겠다. 먼저, 첫번째 문제같은 경우 해시로 풀기보다는 다른 방식으로 접근하기 보다는 sort를 이용하여 푸는 것이 직관적으로 이해가 더 쉽고 시간복잡도에 있어서도 효율적이였다. 사실 이문제에서 얻은 것은 collection 모듈이다. 다른 사람의 ..

[문제 설명 및 파악] 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 먼저 문제의 요구가 무엇인지, 이러한 요구를 만족하기 위해 어떻게 접근해야 될지 알아보자. 일단 이 문제는 여러 치킨집 중 각 가정집들과의 거리가 최소가 될 수 있게 하는 M개의 치킨집을 선택하는 것이다. 그렇다면 이를 구하기 위해서는 어떻게 접근할까? 어렵게 생각이 들 수도 있지만, 이 문제는 모든 집과 모든 치킨집들이 고정되어 있기 때문에 단순하게 생각해서 각 집들의 모든 치킨집들 사이의 거리의 최솟값을 누적해서 반..

[문제 설명 및 파악] 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 일단 이 문제의 요구사항과 힌트 및 접근 방식에 대해서 알아보자. 해당 문제는 결국 중력을 이용해서 이리 저리 굴려 파란공이 구멍에 빠지지 않도록 빨간공을 빼내는 것이다. 물론 많은 제한과 여러 조건들이 있지만, 이는 코드 설명 시 언급하겠다. 그렇다면 어떻게 접근해야 될까? 이 문제도 결국 모든 경우를 알아야 한다. 현재 위치에서 갈 수 있는 모든 방향에 대해서 고려하여 이동 후 또 다시 ..

[문제 설명 및 파악] 백준 17837번: 새로운 게임 2 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 이 문제도 어떤 것을 요구하는지, 그 요구사항을 어떻게 풀어나가야 할지 코딩을 구현하기 전에 생각해보자. 먼저 이 문제가 요구하는 것은 정해진 맵에서 말들이 위치와 방향이 주어졌을 때 해당 조건들을 만족하며 맵의 한 칸에 말이 4개 이상 있을 수 있는지 파악하는 것이다. 그렇다면 이 문제는 어떻게 접근해야 할까? 주어진 조건들을 보면 말들의 위치가 같아지면 쌓인다라는 것을 알 수 있다. 이 힌트를 통해..

문제는 총 6문제, 시간은 2시간이 주어졌다. 코딩테스트를 준비하기 시작한 이후로 처음 경험한 실제 테스트였다. 결론적으로 나는 1문제만을 맞췄다. ㅋㅋㅋ.. 2시간에 6문제라면 한문제 당 20분 안에 풀어야 한다는 것이어서, 난이도는 적당히 나올 거라고 예상했다. 물론 풀어본 문제들 중에서는 막 어려운 편에 속하는 편은 아니였다. (그래 봤자 내가 지금까지 푼 문제들은 20개도 안지만..) 물론 현재 실력이 많이 부족하고 경험도 많이 부족해서 경험하자는 의미에서 적어도 2-3문제만은 완벽히 풀자라고 다짐했지만, 결국 그냥 꽁으로 주어진 문제 하나만을 맞추었다.. 아직 실력이 정말 많이 부족한 듯 싶다. 이번 코딩테스트 문제가 공개되면 다시 풀어보며 리뷰를 하겠지만, 아직 공개가 되지 않아서 대략적인 문..

[문제 설명 및 파악] 더보기 Q. 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열..