2020/017 [algospot][ITES] 외계 신호 분석 문제 : https://algospot.com/judge/problem/read/ITES 외부 시그널에서 신호를 새로 만들어야 한다. 생성한 시그널 = 외부시그널 % 10000 + 1 외부 시그널 = (이전 외부 시그널 * 214013 + 2531011) % 232 위 규칙으로 생성한 시그널들을 가져와서 문제를 푸는데 사용한다. 큐를 이용해서 풀 수 있다. 생성된 신호는 10000 나머지 연산 + 1이기 때문에 양수이다. 따라서 부분 수열은 항상 양수가 된다. 생성된 시그널을 큐에 넣으면서 부분 수열의 합을 구해나간다. 만약 부분 수열의 합이 K보다 작은 경우 앞으로 생성되는 시그널들을 더하면 K가 될 수 있으므로 다음 시그널을 탐색한다. 부분 수열의 합이 K와 같은 경우는 카운팅한다. N까지의 시그널들.. 2020. 1. 31. [algospot][JOSEPHUS] 조세푸스 문제 문제 : https://algospot.com/judge/problem/read/JOSEPHUS N = 6, K = 3 을 예로 들어보자. 병사 리스트 삭제되는 인덱스 (0부터 시작) 삭제되는 병사 번호 (1부터 시작) 1 2 3 4 5 6 0 1 2 3 4 5 6 2 4 2 3 5 6 0 2 3 5 6 2 6 최종 결과는 위와 같다. 리스트에 병사들 번호를 차례대로 저장한뒤 배열요소가 2개가 남을 때까지 삭제되는 인덱스를 구해서 하나씩 배열에서 삭제시킨다. 삭제 인덱스는 0부터 시작하며 다음 삭제되는 인덱스는 삭제된 인덱스 + K -1 이다. +K는 시계 방향으로 K 번째인 사람이 다음 삭제되는 인덱스이기 때문에 더해주었다. -1은 현재 리스트에서 한 병사가 삭제되었기 때문에 이(삭제된 병사 인덱스 1.. 2020. 1. 28. [leetcode][368] Largest Divisible Subset 문제 : https://leetcode.com/problems/largest-divisible-subset/ 중복되지 않는 양수 정수 배열이 주어질 때, (A, B) pair가 A%B = 0 이거나 B%A = 0 인 경우, 즉, 나누어떨어지는 수들로만 이루어진 subset들 중 가장 긴 subset을 하나 구하는 문제이다. dp로 풀었다. dp[i] = 부분문자열[i~]에서 i 번째 정수를 반드시 포함하면서 조건에 만족하는 subset들 중 최장 길이. (길이를 저장) nextInd[i] = dp[i]가 저장될 때, 2번째로 저장되는 정수의 인덱스. (1번째는 i번째 정수로 고정). 나중에 subset 문자열을 구할 때 추적용도로 사용한다. 초기값은 -1 [1,2,4,5]을 예로 들어보자. 인덱스 0,1.. 2020. 1. 26. [leetcode][1267] Count Servers that Communicate 문제 : https://leetcode.com/problems/count-servers-that-communicate/ m x n grid가 주어질 때, 1은 서버, 0은 빈 셸이라고 하자. 같은 행이나 열에 서버가 있는 경우 그 서버는 다른 서버와 통신할 수 있다고 한다. 다른 서버와 통신할 수 있는 서버의 총 개수를 구하는 문제이다. 예를 들어서 확인해보자. 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 grid가 위와같이 주워졌다고 하자. 1 1 0 0 1 1 1 0 1 1 2 0 1 1 2 1 열 subsum은 위와 같이 채워진다. 위에서 아래로 채운다고 생각하면 된다. 1 2 2 2 0 0 1 1 0 0 1 1 0 0 0 1 행 subsum은 위와 같이 채워진다. 왼쪽에서 오른쪽으로 .. 2020. 1. 26. [leetcode][1288] Remove Covered Intervals 문제 : https://leetcode.com/problems/remove-covered-intervals/ 간격배열이 주어질 때, [a,b), [c,d)가 있는 경우 c 2020. 1. 25. 2020 TODO 리스트 1월이 거의 지나가지만 이제서야 작성해보는 1월 TODO 리스트. 내 리스트는 한결같기 때문에 2년전에 작성했던 버킷리스트 포스팅을 참고했다. 마라톤 3번 참여 2018년에 마라톤을 3번 참여했었다. (5km, 7km, 10km) 마지막으로 참여했던 손기정 평화 마라톤(10월)을 끝으로 겨울에는 마라톤 대회가 많이 안열리기도 하고 춥기 때문에 쉬는 시간을 가지기로 했었다. 그리고 마라톤 톡방에 "~ 2019년 2월 까지 마라톤 쉬기" 를 등록한뒤 동면에 들어갔다. 그리고 작년 12월, 카톡방을 부활시켰다. 4달 동면 하기로 했는데 1년을 넘게 동면했다. 좀 상세 목표를 이야기하자면 18년도 나보단 빠르게 이다. 7km 마라톤을 2016, 2018년도에 한 번씩 참가했었었는데 2016년도에 워낙 천천히 달.. 2020. 1. 25. 이전 1 2 다음