Algorithm/백준79 [백준][C++] 6593번: 상범 빌딩 <242> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 너무나 단순한 BFS 탐색 문제이다. 우선 우리는 좌표와 몇분이 걸리는지를 저장하기 위해 Position이라는 Class를 다음과 같이 정의하자. class Position { public: int x, y, z; i.. Algorithm/백준 2022. 9. 5. [백준][C++] 7569번: 토마토 <241> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번문제는 Queue를 얼마나 잘 활용하는지가 핵심이다. 보통 BFS문제는 (!Q.size)동안 반복문을 돌게 된다. 문제는 이렇게 한번에 다 BFS탐색을 돌면, 하루안에 모든 과일이 익은것 처럼 코드가 작동한다. 우리는 하루마다 이미 익어있는 토마토에 인접한 토마토만 익도록 만들어야 한다. 따라서 BFS도 하루 단위로 동작해야 한다. 그래야 총 몇일이 소모됬는지 확인할 수 있다. 이를 위해서는 Queue의 사이즈를 이용해야 한다. 문제의 input을 보자. 5 3 1 0 -1 0 0 0 -1 -1 0 1 1 0 0 0.. Algorithm/백준 2022. 9. 1. [백준][C++] 2410번: 2의 멱수의 합 <240> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 동전1 문제와 매우 유사한 문제입니다. 우선 DP[i] : i를 2의 멱수로 표편하는 방식의 수 라고 정의합시다. DP[i]를 구하는 방법은 DP[i-1] + DP[i-2] + DP[i-4] + DP[i-8] + ... + DP[0] 로 구할수 있습니다. 예를 들어 문제의 예시인 7을 구한다 생각해봅시다. 2^0(1) 일때의 모든 DP 배열을 채우면 다음과 같다 1로만 각 수를 만들수 있는 경우는 전부 1가지 이다. i = 1 2 3 4 5 6 7 DP[i] 1 1 1 1 1 1 1 2^1(2) 일때의 모든.. Algorithm/백준 2022. 8. 18. [백준][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++] 15486번: 퇴사 2 <238> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 N의 범위가 150만 이라서 완전탐색 이런 방식으로는 절대 해결할수 없다 생각하였다. 그리고 문제 자체에서 DP smell이 엄청나게 느껴졌다. 바로 동적계획법을 적용시켜보려 노력하였다... Algorithm/백준 2022. 8. 9. [백준][C++] 17143번: 낚시왕 <237> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 아... 캐어렵다... 구현할 부분이 생각보다 많고, 생각해야 될점도 많다... 먼저 문제의 진행방식을 크게 3단계로 나눌 수 있다. 1. 배열 초기화 하기 2. 사람이 상어 낚시하기 3. 모든 상어 움직이고, 잡아먹기 ▶ 배열 초기화 하기 이때 맨 처음 초기화 가.. Algorithm/백준 2022. 7. 28. [백준][C++] 10775번: 공항 <236> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 원래 나의 첫 풀이는 Greedy 방식으로 매우 직관적인 코드를 작성했었다. 그냥 맨 뒤부터 확인하면 되겠다 생각 하였다. 따라서 맨 처음 나의 코드는 다음과 같았다. (73%에서 시간 초과 나는 코드) #include #include using namespace std; #define MAX 100001 int G, P; int cnt; vector air; bool gate[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> G >> P; for (in.. Algorithm/백준 2022. 7. 26. [백준][C++] 1541번: 잃어버린 괄호 <235> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 생각보다 잘 안풀렸던 문제... 문자열 파싱이야 쉬운데... 최소의 값을 어떤 방식으로 만들것인가? 이걸 생각 못해서... 다른 블로그의 글을 참고하였다. 생각보다 간단하다, - (음수) 부호 뒤의 모든 수.. Algorithm/백준 2022. 7. 18. [백준][C++] 1074번: Z <234> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 재귀문제인건 당연하게 느껴진다. 재귀 문제는 항상 "나 안에 나 찾기" 를 한다는 생각으로 접근하다보면 실마리가 보인다. 재귀 함수에 들어왔을때, 우리가 원하는 칸에 도착했다면 출력하고 바로 종료시킨다... Algorithm/백준 2022. 7. 11. [백준][C++] 4386번: 별자리 만들기 <233> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최소 신장 트리(MST)가 가장 먼저 떠오르는 문제이다. 다만 다른 MST 문제와 다른 점은 간선(edge) 정보가 주어지지 않는다는 점 이다. 따라서 사용자가 직접 모든 간선을 만들어 주어야 한다. 따라서나는 2중 f.. Algorithm/백준 2022. 7. 10. [백준][C++] 12893번: 적의 적 <232> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 적의 적을 구한다는 점 에서, 분리집합 즉, Union Find가 가장 먼저 떠올랐다. (ps 다른 방식으로는 1, -1, 1, -1 이런식으로 표식을 남기는 방법을 떠.. Algorithm/백준 2022. 7. 7. [백준][C++] 11085번: 군사 이동 <231> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 C++에서의 Class를 간만에 작성해서.... 오래걸린 문제.... 맨 처음에 문제를 읽고 든 생각은, 꼭 최단경로는 아니여도 된다는 점 이다. 그냥 지나간 길의 모든 너비중에서 가장 좁은 길의 너비를 최대화하는 경로를 선택하는 것.. Algorithm/백준 2022. 7. 1. 이전 1 2 3 4 5 ··· 7 다음
