이우의 개발일지

백준 1806번 부분합 1806번 부분합 풀이 이 문제 역시 투 포인터 알고리즘으로 풀어야 시간 초과가 뜨지 않는다.밑에 투 포인터 알고리즘과 그 문제에 대해 적어놓은 것이니 참고하길 바란다.  [백준/C++] 2559번 수열 /투 포인터 알고리즘/ two_pointer - (1)백준 2559번 수열 2559번 수열 코딩테스트 풀이이 문제는 투 포인터 알고리즘을 통해 구현할 수 있다.  투 포인터란?배열에서 이중 for문으로 O(n^2)으로 시간 복잡도를 가지는 작업을 2개 포인터everything.pipelineleewoo.com  이 문제는 S라는 부분합의 기준 값을 줌으로써 부분합이 S를 넘겨야되며, 이 중 길이가 가장 짧은 것을 출력해야한다. 부분합 투 포인터 정답 코드 int len = 1000..

백준 2559번 수열 2559번 수열 코딩테스트 풀이이 문제는 투 포인터 알고리즘을 통해 구현할 수 있다.  투 포인터란?배열에서 이중 for문으로 O(n^2)으로 시간 복잡도를 가지는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 2559번 수열 문제에서는 연속된 k개의 수열 중 가장 최댓값을 구하는 문제이기 때문에, 이중 for문으로 돌기는 하지만, 2번 째 for문은 k번만 돌면 되고 만약 k 값이 크다면 첫번째 for문은 n-k 번째까지만 돌기 때문에온전한 시간복잡도가 O(n^2)이 아니다.  for (int i = 0; i max) max = num; } 다른 부분을 볼 필요가 없고, 위 코드처럼 간단히 비교해주면 된다. 여기서 수열의 값의 범위는 -100 부터 100까지이..

SWEA 1859번 백만 장자 프로젝트 문제  SWEA 1859 백만 장자 프로젝트 입/ 출력 및 예제 풀이  백만 장자 프로젝트를 보면 결국에는 입력된 모든 수를 알고 그 수의 max 값을 안 다음에 그 max값에 그 앞의 수들을 뺀 값을 result에 더 해주면 된다. 만약 max 값이 5이고, 그 앞의 값들이 3, 4 라면result + = 5 - 3;result += 5 - 4;이런 식으로 값을 추가해줘서 총 최대 이득을 뽑으면 된다. 하지만, 1 1 4 1 3 처럼 중간에 큰 max 값이 나오고, 마지막에 3 같은 다음 max 값이 나온다면 4의 max 값 뒤로 다시 max 값을 지정해줘야 한다.  while (point max) { max = list[num][i]; max_num..