티스토리

코딩합시다
검색하기

블로그 홈

코딩합시다

copain.tistory.com/m

백준 일지

구독자
0
방명록 방문하기

주요 글 목록

  • (C++) 백준 1644 : 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이 문제는 연속된 부분합을 구하는 문제와 거의 유사한 문제입니다. 다른점은 어떠한 리스트가 주어지고 그 리스트에서의 부분합을 구하는게 아니라는 점입니다. 이 문제에서는 소수를 직접 구하고, 구한 소수를 이용해야합니다. 따라서 이 문제는 소수를 구하기, 연속된 부분합이 N이 되는 경우의수 구하기로 나눌 수 있습니다. 문제 풀이 먼저 필요한 소수를 구해야 하는데 어디까지 구해야 하는지 생각해 보아야 합니다. 연속된 소수의 부분합이 N이 되는 경우의 수를 구해야 하는데 이 말인 즉슨 N까지의 소수를 모두 구해야 한다는 말.. 공감수 0 댓글수 0 2021. 12. 20.
  • (C++) 백준 3273 : 두 수의 합 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 두 수의 합이 x가 되는 모든 순서쌍 조합을 찾는 문제입니다. 단순히 모든 두 순서쌍을 비교하려면 경우의 수가 n(n-1)/2 이므로 시간복잡도가 O(n^2)이 됩니다. 이 문제에서는 n이 최대 10^5 이므로 시간 초과가 되게 됩니다. 따라서 다른 방법을 사용해야 하는데 그 방법이 바로 투포인터 알고리즘 입니다. 투포인터 알고리즘은 리스트에.. 공감수 0 댓글수 0 2021. 12. 18.
  • (C++) 백준 1956 : 운동 그래프에서 탐색 알고리즘을 이용하여 사이클을 찾는 문제입니다. 처음 이 문제를 봤을 때는 다익스트라로 풀 생각을 하다가 바로 플로이드 워셜-알고리즘(Floyd-Warshall Algorithm)이 생각났습니다. 그리고 조금 생각해 봤더니 워셜 알고리즘을 사용하면 바로 풀리겠다는 확신이 생겼습니다. 사이클은 모든 노드가 시작점이 될 수 있기 때문에 모든 노드에 대해 탐색을 진행해야 합니다. 이러한 점에서 모든 노드에 대해 탐색을 진행하는 워셜 알고리즘을 쓰면 매우 간단히 구할 수 있겠다고 생각했습니다. 문제풀이 이 문제는 정말 플로이드 워셜-알고리즘을 한번만 사용하면 풀리는 문제입니다. 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘입니다. 모든 노드에 대해 각각 n번째 노드.. 공감수 0 댓글수 0 2021. 12. 17.
  • (C++) 백준 10217 : KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 이 문제를 처음봤을 때 바로 배낭문제가 생각 났습니다. 배낭문제는 N개의 물건의 가치와 무게가 주어졌을 때 최대 무게 K를 넘지 않는 선에서 물건 가치 합의 최댓값을 구하는 문제입니다. 배낭문제는 가치와 무게 두가지 요소를 가지고 있으므로 2차원배열을 사용하여 총 무게의 합을 열의 인덱스에, 가치의 합을 각 배열의 값에 대응시켜 물건의 갯수를 하나씩 늘려가며 .. 공감수 0 댓글수 0 2021. 12. 14.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.