백준문제풀이36 [백준][C++] 6987번: 월드컵 (263) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 보자마자 떠오른 방식은, 모든 팀은 게임을 할때마다 3가지 경우(승리, 비김, 패배)중 하나의 경우가 나온다 생각하였다. 또한 6개팀이 승부하는 경우의 수는 15가지 이다. A: {B, C, D, E, F} B.. Algorithm/백준 2023. 2. 9. [백준][C++] 2302번: 극장 좌석 <239> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 HTML 삽입 미리보기할 수 없는 소스 1) 일반석 1자리만 있는 경우 당연히 해당 1자리만 앉으면 끝이니 1가지 경우이다. DP[1] = 1 이 된다. 2) 일반석 2자리만 있는 경우 이 경우는 2가지 경우가 가능한데, 다음과 같이 가능하다. [A][B] [B][A].. Algorithm/백준 2022. 8. 16. [백준][C++] 16724번: 피리 부는 사나이 <229> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이 문제를 보고 생각한 방식은 cycle을 찾는 방식이였다. 우리 문제의 예시 를 생각해보자! 3 4 DLLL DRLU RRRU 우선 맨 왼쪽 위 부터 탐색을 시작한다고 해보자.. Algorithm/백준 2022. 6. 22. [백준][C++] 11286번: 절대값 힙 <224> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 문제 자체는 엄청 쉽다. 그냥 Queue 2개 만들어서 각각 minus, plus 용으로 사용하면 된다. 다만 주의할점이... 아무 생각없이 그냥 queue를 사용하면서 삽질하면 안된다. 우선순위큐를 사용해서 minHeap을 만들어줘야 한다. priority_qu.. Algorithm/백준 2022. 5. 30. [백준][C++] 5430번: AC <223> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 각 케이스마다 별도로 bool값을 담아두는 isReverse 와 isError 변수를 만드는 것이 핵심이다. 1) isReverse 의 사용처 이 문제를 읽자마자 든 생각은, "이걸 직접 진짜 배열을 뒤집으면 시간안에 못풀겠는데?" 였다. 당연히 직접 뒤집을 필요도 없는 문제이다. isReverse 에 true가 담겨있으면 -> 뒤집.. Algorithm/백준 2022. 5. 26. [백준][C++] 16946번: 벽 부수고 이동하기 4 <221> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제를 1이 나올때마 전체 이동 가능한 칸을 직접 확이하면 시간안에 해결할수가 없다. 총 방문 가능한 칸이 1000*1000 칸이 있는데, 각 칸마다 확인하려면 1000*1000(모든 칸)*1000*1000(이동 가능한 최대 칸) 만큼 돌아야 한다. 시간안에.. Algorithm/백준 2022. 5. 19. [백준][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++] 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++] 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++] 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. 이전 1 2 3 다음
