Algorithm115 [백준][C++] 12015번: 가장 긴 증가하는 부분 수열 2 <213> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 기존의 LIS 를 구하는 DP 방식만으로는 시간안에 해결할수가 없었다. 나또한 처음에 어떻게 해야 시간을 줄일 수 있을지 생각하지 못해 다른 블로그의 글을 참고하였다. 기존의 LIS 풀이와 거의 유사하지만, 저장할때 방식이 조금 달라진다! vec[i]는 길이가 i인 배열에.. Algorithm/백준 2022. 4. 24. [백준][C++] 10942번: 팰린드롬? <212> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 생각보다 간단한 DP 문제이다. 1) 길이가 1인 경우 모두 팰린드롬 수가 된다. 2) 길이가 2인 경우 바로 다음 칸의 수와 비교해서 같은지 확인하면 된다. 3) 길이가 3 이상인 경우 우리의 배열 input이 다음과 같다 해보자. 1 2 1 3 1 2 1 이중 가장 중간에 있는 P : [1, 2, 1] 은 팰린드롬 수 .. Algorithm/백준 2022. 4. 7. [백준][C++] 1005번: ACM Craft <211> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 위상정렬을 이용한 문제이다. 이 문제를 풀어본 후 다음 문제도 풀어보기를 권장한다. [백준][C++] 1766번: 문제집 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,.. Algorithm/백준 2022. 4. 6. [백준][C++] 1766번: 문제집 <210> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 "일의 순서를 정해야 한다" 라는 점에서 위상정렬이 먼저 생각났다. 여기서 위상정렬의 개념을 설명하지는 않겠다. 먼저 위상정렬에 대한 글을 읽어보기를 권정한다. 입력으로 다음과 같은 input을 받는다고 해보자. 4 2 4 2 3 1 4는 2를 먼저 풀.. Algorithm/백준 2022. 4. 5. [백준][C++] 2166번: 다각형의 면적 <209> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 사실 보자마자 풀이는 떠올랐다. 그냥 점 3개씩 잡아서 외적 하면 넓이 나오는 문제이다. 우선 외적으로 면적을 구하는 공식은 다음과 같다. 3점을 기준으로 외적을 진행해 주면 삼각형의 면적이 나온다. 이를 좌표마다 진행해주면 된다. 다음 블로그의 글을 먼저 참고하길 권장한다. 다각형 도형의 면적(.. Algorithm/백준 2022. 4. 4. [백준][C++] 2473번: 세 용액 <208> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 용액 3개를 선택할 때 하나는 고정값으로 두는것이 핵심이다. 예를 들어 다음과 같은 input이 있다. 7 -2 -3 -24 -6 98 100 61 처음 용액의 목록을 input으로 받은 후, 오름차순으로 정렬하면 다음과 같아진다. -24 -6 -3 -2 61 .. Algorithm/백준 2022. 3. 31. [백준][C++] 2239번: 스도쿠 <207> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 음 왜인지는 모르겠으나... 생각보다 코드가 안짜지는 문제였다... 우선 배열의 크키가 9x9 사이즈라 백트래킹 혹은 brute force 방식으로 해결 가능할거라 생각되었다. 문제에서 input을 받을때 0인 지점들을 vector 에 담아 두었다. 따라서 vector 에 담겨.. Algorithm/백준 2022. 3. 30. [백준][C++] 2467번: 용액 <206> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 투포인트 알고리즘을 적용하면 된다. 1) left = 0, right = n-1로 시작해 두 용액의 합을 찾습니다. 2) 두 용액의 합에 대해 절댓값이 기존의 값보다 더 작다면 현재 합을 갱신해줍니다. 그리고 정답에 대한 값 또한 갱신해줍니다. 3) 현재 left과 right의.. Algorithm/백준 2022. 3. 28. [백준][C++] 16953번: A → B <205> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16953번: A → B 첫째 줄에 A, B (1 ≤ A HTML 삽입 미리보기할 수 없는 소스 이번 문제는 예전에 비슷한 문제를 푼 경험이 있어 금방 해결하였다. 역으로 해결해 나가면 된다! 예를 들어 다음과 같은 예시가 있다고 해보자 2 162 이를 역으로 162 -> 81 -> 8 -> 4 -> 2 가 될수 있다. B부터 시작하여 A를 만들어 간다고 생각하면 편하다. B에서 마지막 숫자가 1로 끝나면 => 기존 A의 수에 1추가 연산으로 B가 된것 B에서 마지막 숫자가 1이 아니고, 2로 나누어 떨.. Algorithm/백준 2022. 3. 25. [백준][C++] 11779번: 최소비용 구하기2 <204> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 간단한 다익스트라 문제이다. 다만 역으로 추적하면서 지나온 경로를 기록하는 방식을 설명해볼까 한다. 이름이 road인 1차원 배열을 하나 만들었다. road[now] = prev 의 의미는 "now번 정점에 최소 비용으로 도달하기 위해서는 prev정점으.. Algorithm/백준 2022. 3. 24. [백준][C++] 1238번: 파티 <203> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 다익스트라를 딱 2번만 적용하면 되는 문제이다!! 문제는 처음에 각 정점에서 X로 가는 비용을 구하려면, 각 정점의 수만큼 다익스트라를 진행해줘야 된다는 점 이다. 다익스트라의 시간 복잡도는 O(ElogV) 인데, 총 정점의 수만큼 돌면 =.. Algorithm/백준 2022. 3. 23. [백준][C++] 10830번: 행렬 제곱 <202> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이런 N승 문제는 기본적으로 진짜로 N승 해버리면 대부분 못푼다. 지금 까지 내가푼 대부분의 N승 문제의 결론은 O(logN) 안에 해결되도록 코드를 구서해야된다는 점 이다. 예를 들어 A의 6승을 구해야 한다면 A를 진짜 6번 곱하는 것 이 아니라, A의 3승을 2번 곱하면 된다. => (A*A*.. Algorithm/백준 2022. 3. 22. 이전 1 ··· 3 4 5 6 7 8 9 10 다음
