Algorithm/백준79 [백준][C++] 17387번: 선분 교차 2 <218> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 vector의 외적에 대한 지식이 없다면 다음글을 먼저 읽어보길 권장한다. https://degurii.tistory.com/47 [알고리즘] CCW로 세 점의 방향성 판별하기 0. 들어가기 전에 첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다. 원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 .. Algorithm/백준 2022. 5. 9. [백준][C++] 10026번: 적록색약 <217> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 BFS를 2번 돌면되는 간단한 문제이다... 1) 일단 이반적인 BFS를 1번 돈다 2) R을 G로 변경한 후 (R과 G를 동일시 하기 위해) 3) 다시 BFS를 1번 돈다 (적녹생맥 전용) 나의 코드 " data-ke-type="html"> HTML 삽입 미리보기할 수 .. Algorithm/백준 2022. 5. 2. [백준][C++] 7579번: 앱 <216> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 유명한 KnapSack 문제이다. 해당 알고리즘에 대한 설명을 다음과 같이 정리해 두었다. HTML 삽입 미리보기할 수 없는 소스 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 터질 것" data-og-host="blo.. Algorithm/백준 2022. 4. 28. [백준][C++] 12100번: 2048 (Easy) <215> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 원래 맨 처음 생각한 풀이는 DFS를 진행하면서 우선 방향에 대한 중복순열을 구한 후, 구해논 중복 순열대로 돌려가면서 닶을 구하려 했다. 문제는 4방위에 맞도록 비슷한 함수를 4번이나 작성해야 한다는 점 이였다.... 이러한 문제를 해결하기 위해 2차원 .. Algorithm/백준 2022. 4. 27. [백준][C++] 1202번: 보석 도둑 <214> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 그리디(Greedy) 알고리즘에 우선순위 큐(Priority Queue) 를 사용하는 문제입니다. 1) 우선 입력으로 받은 가방의 무게와 보석의 허용 최대 무게를 기준으로 오름차순으로 정렬해줍니다. 2) 이후 가방의 수만큼.. Algorithm/백준 2022. 4. 25. [백준][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. 이전 1 2 3 4 5 6 7 다음
