백준72 [백준][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. [백준][C++] 1504번: 특정한 최단 경로 <201> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 나의 생각 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 최단거리를 구하는 문제니 다익스트라 알고리즘이 떠올랐다. 문제는 특정한 지점 A, B 를 반드시 지나쳐야 한다는 점 이다! 가능한 case는 다음과 같다. 1) start -> A -> B -> end 2) start -> B -> A.. Algorithm/백준 2022. 3. 17. [백준][C++] 1043번: 거짓말 <200> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번문제는 Union Find 알고리즘을 알아야 해결하기 쉽다. 관련 내용을 정리한 글이 있으니 먼저 읽어보기를 권장한다! 그 파티에서 거짓말을 할 수 있다! 각 파티의 경우마다 오는 사람들의 번호를 vector adj 에 담아주었다. 총 2번 사용하게 되기 때문이다. 1) 처음 사람들을 union 시킬때 2) 거짓말을 할 수 있는 파티인지를 확인할 때 맨 처음 모두 자신의 부모로 자기 자신을 가리키도록 해준다. parent[1]은 1, parent[2] 는 2 ... 이런식으로 말이다! 이후 각 파티를 돌면서 Union 연.. Algorithm/백준 2022. 3. 16. [백준][C++] 12581번: 숨바꼭질 2 <199> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 생강의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 기존 숨바꼭질 문제에서는 한번 방문한 지점은 다시 큐에 넣지 않았었다. 하지만 숨바꼭질 2 문제에서는 방법의 가지수까지 고려해야하므로 Queue에서 pop할 때 해당 지점을 방문했다고 표시하는 것이 핵심이다. 예를 들어, N=1 K=4를 입력할 경.. Algorithm/백준 2022. 3. 14. 이전 1 2 3 4 5 6 다음
