본문 바로가기

Problem Solving

 (152)
[프로그래머스/파이썬] 2018 KAKAO BLIND RECRUITMENT[1차] 비밀지도 문제 해석 문제 설명 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 ..
[프로그래머스/파이썬] 성격 유형 검사하기 문제 해석 문제 풀이 결국 각 문항마다 점수를 부여하는데 (매우 비동의 3점) ~ (모르겠음 0점) ~ (매우 동의 3점) 이라고 생각하면 각 문항에 대해 한 가지 성격 유형을 음수 다른 나머지를 양수로 지정하고 계산하면 되는 것이다. 조금 복잡하지만 최대한 간단한 방법은 map을 이용하는 방법이라고 생각했다. 요즘 특히 프로그래머스 lv.1에 map을 이용한 풀이 문제가 참 많아서 바로 map을 떠올리기도 했다. (이렇게 유형타면 실제 코테에서 말아먹을텐데... 자꾸 게으르게 편한 방법을 생각한다.) 우선 나는 한가지 성격 유형을 map으로 지정해주고 그 유형이 앞글자라면 동의를+3점으로 그 유형이 뒷글자라면 비동의를 +3점으로 처리하였다. 이후 각 점수에 대한 결과로 양수면 지정된 성격 유형을 반대라..
[프로그래머스/C++] 달리기 경주 풀이 문제 해석 문제 풀이 처음에 이름을 부른 이후 추월을 어떻게 계산해주어야 할까 고민하다가 단순 구현인가 하고 callings의 길이를 보았더니 100만이라 각 플레이어가 불릴 때마다 배열을 swap해주는 형태는 시간 초과가 날 것 같았다. 그럼 배열을 O(1)이나 O(nlogn)만에 찾아줄 수 있는 방법이 필요했다. map 사용을 생각하였으나 하나로 풀 방법을 몰라 2개로 구현했었다. 하나에는 선수의 이름을 넣으면 등수를 알려주고, 다른 것에는 등수를 넣으면 이름을 알려주도록 짰는데 다른 정답 코드들을 보니 map하나로도 충분하다. 코 드 #include #include #include using namespace std; vector solution(vector players, vector callin..
[프로그래머스/C++] 디스크 컨트롤러 풀이 문제 해석 문제 풀이 운영체제 시간에 배운 CPU Job scheduling 문제 같았다. 처음에 activity selection problem으로 생각해서 헤맸는데 우선순위 큐 문제이다. job을 시작 시간 기준으로 오름차순 정렬한다. 현재 시간보다 작거나 같은 job을 모두 우선순위 큐에 넣는다. 우선순위 큐는 빨리 끝나는 job을 top으로 올리도록 설정한다. job을 실행한 후 큐에서 pop한다. 2~4번을 큐가 빌 때까지 반복한다 코 드 #include using namespace std; struct compare { bool operator()(vector lhs, vector rhs) { return lhs[1] > rhs[1] ; } }; int solution(vector jobs) ..
[백준/C++] 2252번 줄 세우기 (Topology sort) 문제 해석 문제 풀이 코딩테스트 준비하면서 위상 정렬은 알고 있어야지~ 싶어서 한 문제 풀려고 찾아본 문제이다. 위상 정렬이 기억나지 않아 푸는데 좀 헤맸다. 문제 풀이에 들어간 내 의식의 흐름은 아래와 같다. 우선 배열(인접행렬)로 생성하면 3만 x 3만으로 128MB는 훌쩍 넘어 터질 것 같아 인접리스트(adjacency list) 형태로 구현하였다. 만약 한 번도 누군가의 뒤에 선다는 정보가 없었던 사람이 있다면 모두 큐에 넣어주고 순서대로 출력하면 되겠다 싶었으나 (반례: 4,4 1->2 2->3 4->3 4->1 형태로 준다면 단순 bfs로는 해결할 수 없고 응용해야한다는 것을 알게 되었다. bfs에서 생기는 반례는 결국 내 이전 작업이 끝나지 않았는데 내가 먼저 queue에 들어가서 생기는 문..
[백준/C++] 1525번 퍼즐 풀이 문제 해석 문제 풀이 종이에 끄적여보니 0을 바꾸는 순서와 숫자의 위치에 관계를 찾기에는 어려움이 있었고 BFS로 브루트포스처럼 모든 나갈 수 있는 경우의 수를 보기에는 체크해야하는 배열이 99개라서 10억에 가까운 배열을 생성하기엔 어려움이 있어 보였다. 그렇다면 map에 필요한만큼 넣고 순서를 잘 백트래킹형식으로 작성해주면 되겠다고 생각했는데 그냥 int를 넣기에는 어려움이 있어서 1차원으로 flatten한 이후 string으로 변환시켜주었다. 그리고 문제에는 함정이 존재하는데 flatten해서 1차원 배열로 계산하는 경우 4번째칸에서 3번째칸으로 7번째칸에서 6번째칸으로 이동이 불가능하다 코 드 #include using namespace std ; const string want = "123456..
[프로그래머스/C++] 2023 KAKAO BLIND RECRUITMENT 택배 배달과 수거하기 문제 해석 문제 풀이 결국 어느지점까지 찍고 돌아와야 하니 가장 먼곳을 가장 적게 다녀오는 것이 핵심이겠다고 생각했다. 택배를 배송하고 나면 수거할 공간이 생기니 자명하게 최대 갯수만큼 배송하고 최대갯수만큼 수거하는 것이 좋을 것이다. 가장 먼곳에서 최대한 많은 갯수를 동시에 배송하고 수거하는 것이 핵심이라 보고 greedy하게 뒷배열부터 처리해주는 결정을 했다. 또한 횟수가 남는다면 그 다음번에 그 횟수만큼 차감한 후 계산하면 되겠다고 생각하였다. 처음 짠 코드는 배송과 수거를 분리하여 고려하고 둘 중에 횟수가 많은 쪽을 정답으로 처리해주었는데 4, 4, [25, 24, 51, 0], [51, 0, 0, 49] 에서 반례가 생겼다. 다시 생각해보니 매 순간마다 더 많이 다녀와야하는 곳이 어디인지 고려하..
[백준/C++/USACO] 23879번 Air Cownditioning 풀이 문제 이해 문제 풀이 이 문제에서 주어지는 배열 2개의 차이를 가지고 이리저리 그리디하게 생각해보았지만 도저히 패턴을 찾을 수 없었고 조금 신박한 방법으로 풀어야하는 문제였다. 문제에서 주어준 배열의 차이는 아래와 같은데 이 이후로가 생각하지 못했던 신박한 부분이었다. 여기에 앞뒤로 0을 붙여주고 인접한 두 수 사이의 차를 구하면 이렇게 되는데 [증명] basis: 어떤 값이 0에서 시작해서 0이 되려면 더하고 뺀 값이 같아야하는 것은 자명하다. 우리가 원하는 것은 결국 희망 온도의 차이가 0이 되는 것이고 희망 온도의 차이가 0이 되면 인접한 차이 값 역시 0이 되어야 한다. 특정 구간의 배열에 1도를 높이거나 1도를 낮추면 위 그림처럼 선택한 배열 앞 뒤로 +1과 -1 혹은 -1 +1 되는 것을 확인..

티스토리툴바