전체 글657 [Programmers] 단속카메라 문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 그리디로 풀었다. 먼저 루트들을 시작위치를 기준으로 오름차순정렬한다. 변수를 만들어서 커버가능한 시작위치 종료위치(let, cover)를 저장한다. 루트들을 처음부터 탐색하면서 탐색 중인 루트(let, route)가 이전 가능한 카메라 위치로 커버가능한지 체크한다. 만약 route.시작위치 > cover.종료위치 이거나 route.종료위치 < cover.시작위치 라면 범위가 커버가 불가능하므로 카메라를 한 대 더 설치해야한다. 카메라 대수를 한 대 증가시키고 cover 변수를 현재 route 범위로 갱신한다. 이전 카메라로 커버가 가능하다면 현재 route 범위와 cover 범위의 교집합으로 c.. 2021. 6. 16. [Programmers] 섬 연결하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/42861 오랜만에 푸는 최소신장트리문제~ 크루스칼 알고리즘으로 풀었다. 먼저 cost 오름차순으로 costs 배열을 정렬한다. costs 배열을 탐색하면서 Union-Find로 해당 간선을 연결하면 사이클이 생기는지 확인한다. 만일 두 정점의 부모노드가 같다면 연결하면 사이클이 생기기 때문에 해당 간선을 선택하지 않는다. 두 정점의 부모노드가 다르면 해당 간선을 연결해도 사이클이 생기지 않기 때문에 해당 간선을 선택하고 해당 간선의 비용을 정답에 더해준다. 시간복잡도는 간선들을 오름차순 정렬하는데 드는 시간인 O(ElogE) 소스코드 : https://github.com/fpdjsns/Algorithm/.. 2021. 6. 14. [채팅] 0. 기획, 목표 이제 슬슬 다시 개인프로젝트를 해볼까 하다가 그나마 많이 진행한 테트리스를 켜봤다. 치명적인 버그가 있긴하지만 그럭저럭 돌아간다. 그런데 화면이 너무 텅텅 비어보인다. 버그는 버그대로 고치고 추가기획안으로 피카츄 배구처럼 2p 대전 추가. 온라인 대전 (게임서버 + aws 사용해보기). 컴퓨터 대전 ... 등등을 생각했다. 그러나 나는 웹개발자..! 게임말고 다른걸 해보고 싶어서 채팅서버를 개발해보기로 했다. 그래서 다음 개발건은 게임화면 오른쪽에 채팅화면을 추가할 예정이다. 게임엔 인성질도 빼먹을 수 없으니까 숫자키라던가 누르면 미리 지정해둔 문장을 내보낸다던가. 하는 기능도 있으면 좋을거같다. 나중에 아이템전 추가할거면 숫자키는 다른걸로 변경될거같긴한데 아이템전 추가하려면 지금 속도론 20년 걸릴듯... 2021. 6. 13. [Programmers][2020 카카오 인턴십] 보석 쇼핑 문제 : https://programmers.co.kr/learn/courses/30/lessons/67258 투포인터로 풀었다. gems를 돌면서 보석 종류 수를 구한다. 보석의 개수를 저장하는 cnts map을 하나 만든다. key = 보석이름, value = 보석 수. 그리고 탐색하면서 만난 보석들의 종류를 저장하는 set을 하나만든다. (let, exists) 투포인터의 오른쪽 인덱스(right)를 0부터 1씩 증가시키며 left 인덱스를 갱신한다. 탐색중인 보석의 수를 cnts 맵에 1더해서 갱신시킨다. exists set에 탐색한 보석을 추가한다. 정답가능한 배열의 크기를 최소화로 만들기 위해 left인덱스를 갱신한다. 만일 gems[left] 에 해당하는 보석의 개수(cnts 참고)가 1보다.. 2021. 6. 13. 플로이드 워셜 알고리즘 (Floyd warshall) 이때동안 포스팅한 최단거리 알고리즘은 벨만포드, 다익스트라 알고리즘이 있습니다. 이 두개의 알고리즘은 하나의 정점을 기준으로 다른 정점들까지의 최단거리를 구하는 알고리즘입니다. 플로이드 워셜 알고리즘은 이들과 달리 모든 정점간의 최단거리를 구하는 알고리즘입니다. 플로이드 워셜 알고리즘의 기본 원리는 i 정점에서 j 정점 간의 최단거리를 구하려고 할 때, 그 외의 노드 k를 두고 i -> k 로 이동하는 방법이 존재하고 k -> j로 이동하는 방법이 존재할 때, k를 거쳐서 가는 거리가 이때동안 구한 최단거리보다 더 짧을 때, 최단거리를 갱신하는 방법입니다. 정점들의 번호가 0~n-1, i에서 j로 가는 거리(간선)가 W(i, j)이고 최단거리를 배열 dist에 저장한다고 할 때, 플로이드 워셜 알고리즘은.. 2021. 6. 13. [Programmers] 디스크 컨트롤러 문제 : https://programmers.co.kr/learn/courses/30/lessons/42627 먼저 시작시간이 가장 빠르고, 시작시간이 같다면 소요시간이 적은 순으로 jobs를 정렬한다. 마지막 작업이 종료된 시간(let, 종료시간)을 저장하는 변수를 하나 만들고 0으로 초기화시킨다. 가장 먼저 시작되는건 jobs의 첫번째 요소일 것이다. 작업 소요시간이 적은 순으로 정렬되는 최소힙을 하나만들어서 가장 먼저 시작되는 jobs의첫번째 요소를 큐에 넣는다. 이제 최소힙 빌때까지 잡들의 최소 소요시간을 구해서 sum 변수에 더해나간다. 최소힙의 첫번째 요소를 꺼내서 job의 실제 시작시간을 구한다. 만일 이전 잡의 종료시간이 현재 job의 시작시간보다 작거나 같으면 현재 job의 시작시간이 실.. 2021. 6. 11. 이전 1 ··· 27 28 29 30 31 32 33 ··· 110 다음
