Hanbit the Developer

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net > 풀이 문제에 나와있는 설명을 그대로 구현하면 된다. 단, 주의할 점이 있는데, 얼음을 1씩 줄이는 작업을 할 때, 줄이는 조건을 체크하는 로직과 얼음을 줄이는 로직이 서로 영향을 주면 안 된다. 얼음이 '동시에' 녹아야 하기 때문이다. 나는 이것을 위해 toDecrease라는 좌표를 담는 vector에 줄이게 될 좌표들을 담은 뒤에 따로 처리하였다. #include usin..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net > 풀이 큰 틀은 최대 6개까지 있는 연산을 브루트포스 돌려서 최소값을 얻어오는 식이다. 예를 들어 연산이 3개가 있다고 하면, 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1와 같은 시퀸스의 모든 집합에 대해서 연산을 수행한다. 그 다음으로는 '배열 돌리기'를 구현만 하면 된다. 단, 백트래킹을 이용하므로 반시계방향 회전도 구현해야..

https://www.acmicpc.net/problem/11046 11046번: 팰린드롬?? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net > 풀이 Manacher's algorithm의 기본 활용 문제이다. 해당 알고리즘은 A라는 array를 완성시키는 것이 목적이며, A[i]에는 i 위치에서의 팰린드롬의 길이가 들어간다. 집합 S가 있고, 그 길이가 N이라고 할 때, 0~N-1 인덱스에 대해서 반복문을 돌아주게 된다. 반복문 안에서는 다음과 같은 3개의 steps가 진행된다. 1. A[i]의 초기값을 설정해준다. 이 때 'r'이라는 값이 쓰이는데 이것은 3번째 ste..

https://www.acmicpc.net/problem/10277 10277번: JuQueen The input contains a single test case. It starts with a line containing three integers C, N, and O, where C is the number of cores (1 ≤ C ≤ 4 587 520) to manage, N is the number of frequency steps for each core (1 ≤ N ≤ 10 000) and O is the number www.acmicpc.net > 들어가기 전에 해당 글은 Lazy Propagated Segment Tree를 밑바탕으로 하여 작성하였다. https://rccode.tis..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net > 풀이 트리를 체크하는 DFS 함수(setIsTree)를 짬으로써 해결할 수 있다. 방문한 적이 있는 노드에 방문한다는 것은 트리가 아니라는 것을 말해준다. 해당 조건을 만나더라도 DFS 함수를 끝까지 진행시켜서 isVisited가 올바른 정보를 담도록 해야한다. 이를 고려하여 global variable인 isTree의 값을 정해주는 식으로 설계하였다. #include usi..

https://www.acmicpc.net/problem/1960 1960번: 행렬만들기 첫째 줄에 n(1 ≤ n ≤ 500)이 주어진다. 다음 줄에는 각 행에 있는 1의 개수가 1행부터 n행까지 차례로 주어진다. 그 다음 줄에는 각 열에 있는 1의 개수가 1열부터 n열까지 차례로 주어진다. 행 또는 www.acmicpc.net > 접근 그리디하게 풀릴 수 있을 것이라고 직감하여 고안해낸 방법은 다음과 같은 순서를 따른다. 즉, 1. row 단위로 크게 돌면서, 2. 현재 채워넣어야할 1의 개수가 가장 많은 곳을 채워넣는 것이다. > 풀이 이것을 위해 우선순위큐를 이용한다. 우선순위큐(columnInfo)에는 (채워넣어야할 1의 개수, 해당 column의 인덱스)를 넣어준다. 이후에 row 단위로 for..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 3차원 DP를 사용하여 이 문제를 해결하였다. > 발상 처음 혹은 마지막 집을 제외하면, 영향을 미치는 범위는 인접한 집뿐이라는 것을 알 수 있다. 이를 통해 O(N)의 반복과 같은 접근법을 사용할 수 있다고 판단하였다. 그리고 중요한 요소가 있는데, 바로 0, N-1번째 집이다. 만약 짜게 될 코드가 0부터 시작해서 N-1에 도달하는 식이라면, 분명히 인덱스가 0인 ..

https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net #include #include #include #pragma warning(disable:4996) #define INF 101 typedef struct Position { double x, y; } Position; typedef struct Metadata { int n; Position* obj; double** graph; } Metadata; typedef struct Pair..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net #include #include #pragma warning(disable:4996) #define INF 10000001 typedef struct Node { int val; struct Node* next; } Node; typedef struct Vertex{ Node* header; int hIndex; int dist; } Vertex; typedef struct Edge { int a, ..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct Node { int val; struct Node* next; } Node; typedef struct Vertex { Node* header; int in; } Vertex; typedef struct Edge { int a, b; } Edg..