Hanbit the Developer

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..

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net - 배경 Segment Tree의 Lazy Propagation을 안다는 전제로 글을 작성하였으니, 해당 개념에 대해서는 다음 링크를 참조하자. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net - 풀이 구현해야할 것은 크게 2가지다. 한 줄에서 가장 위에 있는 상어를 잡는 catchShark()와, 상어들을 이동시키는 moveSharks() 함수이다. 전자는 매우 간단하게 구현이 가능하다. 하지만 문제는 후자이다. moveSharks() 함수는 모든 살아있는 상어들을 반복문으로 돌면서, 각각의 위치와 속도, 그리고 방향에 따라 nextPosition을 구해준다. 다음..