https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; for (int t = 0; t > func; i..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #pragma warning(disable:4996) #include using namespace std; int map[51][51]; int T; int M, N, K; //가로 세로 (1~50), 배추개수 // 아, 왼, 위, 오 int dm[4] = { 0,-1,0,1 }; //가로 int dn[4] = { 1,0,-1,0 }; //세로 void dfs(int n, int m) { //map이 1이면 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net #pragma warning(disable:4996) #include #include using namespace std; vector graph[101]; //인접 리스트 int visit[101]; void dfs(int node) { visit[node] = 1; for (int i = 0; i < graph[node].size(); i++) { int next = graph[node][i]; i..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net #pragma warning(disable:4996) #include #include #include using namespace std; int tomato[101][101][101]; int M, N, H; queue q; int day = 0; //위층, 아래층, 상,하,좌,우 int dn[6] = { 0,0,-1,1,0,0 }; int dm[6] = { 0,0,0,0..

https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 알고리즘 분류 풀이 방법 구분 백준 문제 티어 블로그 기록 완전 탐색 (Brute-force) for문으로 전부 확인 18111번: 마인크래프트 2 DFS + backtracking 1062번: 가르침 4 자료구조 트리 2042번: 구간 합 구하기 1 https://recordgarden.tistory.com/5 맵(map) 4358번: 생태학 2 https://recordgarden.tistory.com/6 덱(deque) 5430번: AC 5 https://recordgarden.tisto..

안쓰니까 맨날 까먹어서 기록해두는 C++ 입출력 기능 (새로운 기능 생각날 때마다 추가) 1. printf 정수 format지정 출력 #pragma warning(disable:4996) //scanf등 오류 지우기 #include //printf, scanf #include //cin, cout using namespace std; //std::cin, std::cout int main(){ printf("%d-%02d-%02d", 2023,5,24) //%02d = 정수 2글자 format으로 출력, 공백엔 0삽입 return 0; } 2. 문자열 printf, scanf 사용해서 출력 (왠만하면 string + cin, cout으로 하는게 편할듯) https://www.acmicpc.net/prob..

위상 정렬 그래프의 방향대로 정점들을 나열하는 알고리즘이다. 선후관계가 존재하는 것들을 순서대로 나열할 때 사용된다. 인접리스트와 큐로 구현한다. 1. indegree (진입차수) 배열을 만든다. (다른 정점에서 들어오는 개수) 2. 진입차수가 0인 정점에서 시작한다. 3. 시작 정점에서 방문할 수 있는 정점들의 진입차수를 -1해서 갱신한다. 4. 갱신한 진입차수가 0이 된 정점들을 queue에 집어 넣는다. 5. 2~4의 과정을 반복한다. 문제 및 코드 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 ..

다익스트라(Dijkstra) 모든 간선이 음수가 아닌 그래프에서만 사용 가능하다. 하나의 정점에서 출발하여 다른 정점들까지의 최단거리를 구한다. 방문하지 않은 정점들 중에서 출발점으로부터의 거리가 제일 짧은 정점을 확정해나가는 과정을 반복한다. 우선순위 큐를 사용하여 구현한다. 문제 및 코드 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net #pragma warning (disable:4996) #includ..

https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net map의 주요 특징 1. key-value로 이루어져있다. 각각 first, second으로 접근 가능하다. 2. 중복을 허용하지 않는다. 3. 내부에서 자동으로 key값 기준 오름차순 정렬을 해준다. 코드 #include #include #include using namespace std; map tree; //string=key, int=value int main() { ios::s..

이진 트리를 응용한 구조인 인덱스 트리에 대해 알아보자. 인덱스트리는 배열에서 구간합, 최대, 최솟값 구하기에서 시간복잡도를 줄여야 할 때 사용된다. 보통 인덱스 트리와 유사한 자료구조로 세그먼트 트리 (segment tree)가 있는데, 둘의 차이는 다음과 같다. 인덱스 트리 (Indexed Tree) bottom-up 방식, while문으로 구현 가능 세그먼트 트리 (Segment Tree) top-down 방식, 재귀로 구현 세그먼트 트리로 구현 가능한 문제는 모두 인덱스 트리로도 구현이 가능하기 때문에 먼저 인덱스 트리를 공부했다. 인덱스 트리 인덱스 트리는 완전 이진트리로 모든 리프노드가 존재하는 구조를 가진다. 따라서 N개의 수를 인덱스트리로 표현하기 위해서는 2*N보다 최초로 크거나 같은 2..