본문 바로가기

알고리즘/백준

[2468]안전 영역(C++) 1. 문제 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 2. 접근 방법 1) 물에 잠기는 기준 값을 standard라고 하면, standard는 1~101까지 존재한다. 2) 각 standard기준보다 높이가 높아서 물에 안잠겼으면서 방문했던 적이 없었던 지역을 기준으로 dfs를 수행하여 방문처리를 한다. 3) standard별 그룹 수가 나오는데, 가장 큰 수를 출력한다. 3. 실수했던 부분 & 처음 알았던 부분 1) 나는 처음에 물에 잠기는 범위를 지역 .. 더보기
[1261] 알고스팟(C++) 1. 문제 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 접근 방법 1) (1,1) -> (N,M)으로 가는 모든 경우를 탐색해야 하므로 BFS / DFS로 구현 2) 문제에서 "부숴야 하는 벽의 최소 개수"를 구해야 하므로 단순 BFS / DFS에서 지금까지 깬 벽의 개수를 고려해야 함 3) 두 가지 경우의 수 - DFS 형식으로 푸는 경우 : 재귀 + 배열을 사용하여 배열 map[N][M]에는 (1,1) -> (i,j)까지 도.. 더보기
[2606] 바이러스 1. 문제 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 2. 접근 방법 1) PC 간의 연결 정보를 나타내기 위해 2차원 벡터를 선언한다(v). 2) dfs의 방문 정보를 나타내기 위해 bool 타입의 벡터를 선언한다(visited). 3) PC간 연결 정보는 양방향이므로 v에 값을 넣을 때 이 점을 유의하여 a-b의 연결 정보를 v[a]와 v[b]에 각각 저장한다. 4) 재귀 함수인 dfs를 선언하여 감염된 PC개수인 cnt를 반환한다. 3. 실수했던 부.. 더보기
[11000]강의실 배정 3. 유의 할 것 - 입력값이 20만개 이므로 logN형 자료구조를 사용해야 한다. - 나는 시간을 줄이기 위해서 주로 map,set을 사용했는데 set의 경우 균형 이진 트리이므로 검색은 빠르지만 삽입 & 삭제가 느리다. (삽입,삭제는 log(N)) - 우선순위 큐는 Heap을 사용하므로 set보다 더 빠르다. 삽입 삭제도 logN 이므로 따라서 우선순위 큐를 자주 쓰도록 하자. 4. 코드 더보기 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N,s,e; vector v; cin >> N; for(int i=0;i> s >> e; .. 더보기
[16235]나무 재테크(C++/구현) 1. 문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 2. 접근 방법 1. 특별한 알고리즘을 써야 한다기 보단 구현 문제이다. 구현일 수록 사용할 자료구조 선택, index 의미에 유의하자! 2. 문제의 조건 & 제약 사항을 파악하자 (다음은 문제를 읽으면서 생각한 흐름) 1) 한 칸에 "여러 개"의 나무가 있을 수 있다. => "container형 이차원 배열 사용해야 겠다." 2) 양분을 먹을 때, 나이가 어린 나무부터.. 더보기
[백준] DP > 1. DP의 정의 & 속성 동적 계획법: 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 두 가지 속성을 만족해야 DP로 풀 수 있다 -optimal substructure: 문제의 정답을 다른 문제의 정답에서 구할 수 있음 ex) 피보나치 -overlapping subproblem: 겹치는 부분 문제 ( 작은 문제로 N-1과 N-2번째 수를 구하는 것) ex)서울->부산 가는 가장 빠른 길: 서울->대전-> 대구->부산 이면, 대전->부산을 가는 가장 빠른 길은 대전->대구->부산이다. 2. 문제 스킬 1) 각 문제는 한 번만 풀어야 한다. 2) 같은 문제는 구할 때마다 정답이 같다. 정답을 어딘가에 메모해두자(memorization) 3) 문제에서 구하려고 하는 답을 문장으로 나타낸다. 4) 문장에 .. 더보기
[9251] LCS(C++) 1. 문제 2. 접근 방법 - 못풀어서 해답을 찾아보았다. http://melonicedlatte.com/algorithm/2018/03/15/181550.html [백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect 출처 : https://www.acmicpc.net/problem/9251 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB76453240240041.746% 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, � melonicedlatte.com - dp[i][j] : s1.substr(0,i) , s2.substr(0,j)의 LCS 길이 (i번째, j 번째 문자열을 선택했을 때가 아님) .. 더보기
[백준]수학1 1. 나머지 연산 답을 M으로 나눈 나머지를 출력하라는 문제 시 유의 할 것 분배법칙 성립 1. (A + B) mod M = ( (A mod M) + (B mod M) mod M) 2. (A * B) mod M = ( A mod M) * (B mod M) mod M) 3. (A - B) mod M = (( A mod M) - (B mod M) + M) mod M) //뺄셈의 경우 주의 4. 나눗셈은 성립 X 2. 최대 공약수 최대공약수는 GCD라고 함 가장 쉬운 방법: 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법 for(int i=2; i (3/3 = 1 ...0) => (1/3 = 0 ...1) 따라서 답은 102 5. 소수 약수가 1과 자신 밖에 없는 수 2, 3, 5, 7, 11, 13.. 더보기

티스토리툴바