프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해결하는데 좀 오래 걸렸다.처음에는 구현, 그리디 방식으로 해결이 가능할 것 같다고 생각했지만 실패했다.1. 원형으로 이루어진 외벽을 일직선으로 편 후, 길이를 2배 늘린다.2. 점검할 수 있는 거리를 내림차순으로 정렬.3. 각 친구가 점검할 수 있는 만큼 최대한의 취약 지점을 찾아 처리.이런 방식으로 가능할 것이라 생각했지만,'점검 거리 내에 포함되는 취약 지점의 수가 같은 경우가 2개 이상 생기면 어떤 구간을 선택해야 하는가'를해결할 수 없어서 다른 방법을 고민했다. 결론적으로 백트래킹을 써서 해결. 1. 취..
PS/Programmers
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 머리 아파서 좀 대충 풀었다 왜인지는 모르겠지만 게리맨더링이 생각나는 문제였다. 전선 개수가 최대 99개여서 하나하나 다 끊어보는 방법이 가장 먼저 떠올랐다. 1. 부모 배열과 부모를 찾는 함수 작성(분리집합) 2. 매 케이스마다 두 집합의 크기를 구해 차가 답보다 작은지 확인하자. 3. 전선 배열을 돌면서, 해당 전선을 제외하고 모든 전선을 확인해 집합을 둘로 나눈다. 4. 부모 배열을 초기화한다. 이렇게 작성했는데, 통과하고 다른 사람 풀이를 보니 dfs 한 번만으로 해결했더라... 전선을 모두 확인해 트..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1시간 고민하고도 모르겠어서 질문 게시판에 있는 힌트를 봤지만, 문제를 애초에 잘못이해해서 힌트도 이해를 못 한 거였다;; 이 지문을 잘못이해해서, 내 양쪽 집이 둘 다 털리면 경보가 울리는 것으로 생각했었다. 그래서 첫 번째 집과 마지막 집에 포커스를 둘게 아니라, 첫 번째 집을 터느냐 마느냐만 생각하면 된다는 힌트도 이해를 못 했었다. 지문을 제대로 풀어보면 그냥 연속으로 집을 털지 말란 거다. (이 쉬운걸 왜 못 알아먹었을까) 2차원 배열로 DP 배열을 만들었고, DP[i][0]은 0번째 집을 털지 않았..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백준에서 정렬, 스위핑 태그가 붙어있는 문제들의 풀이 유형이 떠올라 바로 적용했다. 우선 나가는 지점 오름차순으로 정렬한다. (나가는 지점이 같다면, 들어오는 지점이 작은 것이 앞으로 오도록 한다.) 최대한 많은 차량의 경로가 겹쳐야 단속카메라를 적게 달 수 있다. 나가는 지점을 기준으로 정렬했으니, 앞 차량의 나가는 지점(기준)이 뒷 차량의 들어가는 지점보다 크거나 같은 경우 차량들의 경로가 겹치므로 언제까지 겹치는지 확인하고 겹치지 않는 순간 단속카메라를 설치하고 기준을 바꿔준다. 첫 차량(i = 0)의 ..
