Angievelopment

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net ✨ 문제 풀이 문장의 앞에서 부터 문자를 짚어나가는 포인터와, 맨 뒤에서부터 문자를 짚어나가는 포인터 두 개를 이용하는 문제입니다. 앞에서부터 보는 포인터를 x, 뒤에서부터 보는 포인터를 y라고 정의합니다. 문장의 길이가 홀수일 때 가운데 문자는 무엇이든 상관없고 짝수일 때는 x=y-1일 때까지 비교하므로 x

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ✨ 문제 풀이 이분탐색은 항상 그렇듯이 무엇을 기준으로 잡고서 탐색할 것인지가 중요하다. 최소 M미터의 나무 토막을 가져갈 때 절단기 높이의 최댓값을 구해야하므로 절단기의 높이를 기준으로 잡고 탐색한다. 그렇다면 탐색할 첫 기준이 중요한데, 절단기가 모든 나무를 자르는 경우인 0을 start로, 아무것도 자르지 않는 최대 높이인 가장 큰 나무의 길이를 end..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ✨ 문제 풀이 BFS또는 DFS를 이용해서 해결할 수 있는 문제입니다. 1 6 6 3 3 5 4 1 2 4 4 7 연결된 노드의 정보가 위와 같다고 예시를 들어봅시다. 문제에 따르면 1은 무조건 루트 노드입니다. 따라서 1과 연결된 노드들은 모두 부모가 1인 노드입니다. 1과 연결된 노드는 4, 6입니다. 이 노드들에 대해서 차례대로 확인합니다. 4와 연결된 노드는 1, 2, 7 입니다. 1은 무조건 부모 노드이므로 2, 7이 자식 노드입니다. 즉 2, 7의 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ✨ 문제 풀이 간단한 BFS 해결 문제입니다. u와 v의 컴퓨터가 연결되어 있다면 u번째 배열에 v를 저장해주고, 마찬가지로 v번째 배열에 u를 저장해줍니다. 그리고 1번 컴퓨터와 연결되어 있는 모든 컴퓨터를 찾아야 하므로 BFS를 통해 연결된 컴퓨터를 하나씩 방문하면서 개수를 세어나갑니다. 이때 주의할 점은 1번에 영향을 받은 컴퓨터의 개수를 찾는 것이므로 1번 컴퓨터를 제외한 개수를 출력해야 합니다..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net ✨ 문제풀이 n*m 격자 모양 행렬을 BFS로 해결하는 문제입니다. 그러나 반복해서 전체 격자를 검색하면서 치즈가 전부 녹아서 없어질 때까지 진행해야 합니다. 이 문제의 가장 핵심은 '외부 공기'와 '내부 공기'를 구분하는 일입니다. '외부 공기'와 접촉이 없고 치즈에 둘러싸인 내부 공기에 닿은 치즈 면은 녹지 않는 면입니다. 바로 이 공기를 구분할 때 BFS를 사용합니다. '내부 공..

https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net ✨ 문제 풀이 2가 딱따구리 가족이므로 2의 (y, x)좌표가 시작점이 될 것입니다. 그리고 3, 4, 5는 딱따구리 가족이 각자 먹고 싶은 음식이고 종착점이 됩니다. 딱따구리 가족은 3, 4, 5 중 아무거나 하나만 가장 먼저 먹을 수 있는지만 구하면 됩니다. 1은 장애물이라 갈 수 없으며 0은..

n행, m열의 행렬을 받고 상하좌우 4방향으로 한 칸씩 옮기면서 해답을 찾아가는 BFS 문제를 해결하기 위한 응용 코드입니다. 문제에서 주어진 조건을 잘 읽고 아래 코드를 응용해서 풀이하면 됩니다. 🗓 코드 #include #include #include using namespace std; #define MAXINT 100 int dx[] = {0, -1, 0, 1}; int dy[] = {1, 0, -1, 0}; int n, m, start_y, start_x; int arr[MAXINT][MAXINT]; bool visited[MAXINT][MAXINT]; queue q; void bfs() { q.push({start_y, start_x}); while (!q.empty()) { int y = q..

⛳️ 그래프의 종류 Directed Graph: 방향이 있는 그래프 Cyclic Graph: 하나 이상의 cycle이 있는 경우 Acyclic Graph: cycle이 없는 경우 Undirected Graph: 방향이 없는 그래프 ⛳️ 그래프를 표현하는 방법 1. Adjacency Matrix, 행렬 (2차원배열) matrix[i][j]에 정점 i와 정점 j의 연결 상태 저장 간선이 있으면 1, 간선이 없으면 0으로 표현 (1) 방향 그래프 (2) 무방향 그래프 코드 #include using namespace std; int main(){ // n : 정점 개수, m : 간선 개수 int n,m; cin >> n >> m; int graph[n+1][n+1]; for(int i=0; i> m; vect..

https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 시간이라는 범위 내에서 점점 범위값을 줄여나가면서 최소값을 찾아나가는 문제이다. 즉, 절대 불가능한 가장 작은 시간부터 가장 최악의 시간이라는 범위 내에서 해결 가능한 시간 범위를 찾고 최소를 찾는 것이다. 문제의 입출력 예를 읽고 이게 왜 이분탐색인지 받아들이기 어려웠는데 시간의 흐름에 따라 답을 구하는 방법이 아니라 일단 모든 인..

https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net ✨ 문제 풀이 (1,1)부터 (i, j)까지의 인구수 합을 저장하는 dp 배열을 memo[i][j]라고 하자 위에 그림과 같이 빨간 네모 + 초록색 네모 - 빨간 네모와 초록색 네모가 겹치는 네모 + 그 부분의 인구수 를 계산하면 (i, j)까지의 인구수 누적합이다 이를 점화식으로 세우면 (i, j)의 인구수 + (1,1)부터 (i-1, j)까지의 인구수 합 + (1, 1)부터 (i, j-1)까지의 인..