mangu

2021. 11. 12. 16:39 Algorithm/BOJ

문제 링크 http://icpc.me/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 풀이 LIS(Longest Increasing Subsequence)를 이용하여 풀 수 있다. 가장 긴 증가하는 부분 집합을 구하고, 그 부분 집합에 속하지 않는 사람들만 이동하면 되기 때문에 n - LIS를 하면 된다. 코드 #include #include using namespace std; int arr[202], dp[202]; int ret = 0; int main() { ios::sync_with_stdio(0)..

백준[16946] 벽 부수고 이동하기 4

2021. 11. 12. 02:10 Algorithm/BOJ

문제 링크 http://icpc.me/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 dfs를 이용하여 풀 수 있다. 모든 1에 대해서 dfs를 돌며 인접한 0이 몇 개인지 센다면 한번 dfs를 돌 때 O(NM)이고 dfs를 NM번 돌릴 수 있기 때문에 O(N^2M^2)이 돼서 시간이 터질 것이다. 그렇기 때문에 인접한 0의 개수들을 미리 구해놓고, 1이 나올 때 상하좌우에 붙어있는 인접한 0의 개수만 세주면 된다. 상하좌우에 붙어있는 그룹이 같은 그룹인지 아닌지 체크도 ..

백준[3830] 교수님은 기다리지 않는다

2021. 11. 12. 02:05 Algorithm/BOJ

문제 링크 http://icpc.me/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 풀이 유니온 파인드를 이용하여 풀었다. 대소 관계를 이용하여 무게 차이를 구할 수 있는 것들을 같은 집합으로 묶는다. 이때, dist 배열에 두 개의 무게 차를 저장해 놓는다. dist 배열의 정의는 dist [i]는 i와 i의 부모의 거리이다. 또한 두 집합의 루트 사이의 거리를 정의해줘야 하는데, a, b를 union 할 때 a의 루트를 pa, b의 루트를 pb라고 하면, dist [..

백준[1761] 정점들의 거리

2021. 11. 8. 17:26 Algorithm/BOJ

문제 링크 http://icpc.me/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 풀이 LCA(최소 공통 조상)를 구하여 풀 수 있다. root에서 a까지의 거리를 cost[a]라고 할 때, 트리에서 정점 a, b의 거리는 cost[a] + cost[b] - 2 * cost[lca]라고 할 수 있다. 코드 #include #include #include using namespace std; const int N = 4e4 + 4; vector v[N]; int dp[22][N], cost..

백준[1043] 거짓말

2021. 11. 8. 14:30 Algorithm/BOJ

문제 링크 http://icpc.me/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 유니온 파인드를 이용해서 풀 수 있다. 진실을 아는 사람들을 같은 집합에 넣어두고, 파티 구성원들을 같은 집합에 넣을 때, 만약 이 집합에 진실을 아는 사람들이 있다면 진실을 아는 사람 그룹에 그 파티 구성원들을 모두 넣어야 한다. 그 후에 파티 구성원들 집합을 확인하며 진실을 모르는 사람들만 모여있는 집합의 개수를 세면 된다. 코드 #include #include #include using namespace std; i..

백준[6549] 히스토그램에서 가장 큰 정사각형

2021. 11. 7. 19:13 Algorithm/BOJ

문제 링크 http://icpc.me/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 스택과 분할 정복을 이용하여 풀 수 있다. 스택을 이용한 풀이는 O(N)에 풀 수 있지만 아이디어를 떠올리기 힘들고, 분할 정복은 O(NlogN)에 풀 수 있지만 세그먼트 트리를 알아야 한다. 분할 정복 구간 [l, r]에서 가장 큰 직사각형의 넓이는 (가장 작은 기둥 높이) * (r - l + 1) 그렇기 때문에 가장 작은 기둥 왼쪽, 가장 작은 기둥 ..

백준[1010] 다리 놓기

2021. 11. 7. 18:49 Algorithm/BOJ

문제 링크 http://icpc.me/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 조합을 이용하여 풀 수 있다. 고등학교 때 확통 공부를 해봤다면 아주 자주 볼 수 있는 문제다. 다리가 겹치지 않아야 하기 때문에 오른쪽의 어떤 다리에 연결할지만 정한다면, 왼쪽 다리가 어느 다리랑 연결될지는 알아서 결정이 되게 된다. 그렇기 때문에 mCn을 하면 된다. 코드 #include int dp[32][32]; int dpf(int n, int k) { int &ret = dp[n][k]; if (n ..

백준[10999] 구간 합 구하기 2

2021. 11. 5. 15:00 Algorithm/BOJ

문제 링크 http://icpc.me/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 lazy propogation 기본 문제이다. lazy propogation은 세그먼트 트리를 응용한 구간 업데이트와 구간 쿼리를 모두 O(logN)에 할 수 있는 자료구조다. 자세한 설명은 다른 더 대단한 분들이 많이 올리셨으니 생략하겠다. 내가 참고한 글은 여기에 적어놨다. 코드 #include using namespace std; using..

백준[1182] 부분수열의 합

2021. 11. 5. 14:09 Algorithm/BOJ

문제 링크 http://icpc.me/1192 1192번: 장갑 임의로 왼쪽 통에서 2개, 오른쪽 통에서 8개를 가져온다면 최소한 한 쌍의 같은색의 장갑이 나옴을 보장할 수 있다. www.acmicpc.net 풀이 백트레킹으로 조합을 만들면 된다. 만약 s가 0일때는 아무것도 뽑지 않는 경우가 생길 수 있기 때문에 정답에 -1을 해준다. 코드 #include int n, s, ret; int arr[22]; bool visited[22]; void solve(int cur, int sum) { if (sum == s) ret++; for (int i = cur; i < n; i++) { if (visited[i]) continue; visited[i] = true; solve(i, sum + arr[i]..

백준[5052] 전화번호 목록

2021. 11. 4. 10:40 Algorithm/BOJ

문제 링크 http://icpc.me/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 트라이를 이용하여 풀 수 있다. 트라이에 전화번호를 넣는 과정에서 prefix가 똑같은 문자열을 발견하면 NO를 출력하면 된다. cf) new Trie()를 하여 동적 할당을 하는 것보다 전역 변수로 Trie를 많이 만들어 할당해주는 방식이 더 빠르기 때문에 아래와 같이 구현했다. 코드 #include struct Trie; Trie* new_trie(); struct Trie { int..

백준[1913] 달팽이

2021. 11. 2. 16:50 Algorithm/BOJ

문제 링크 http://icpc.me/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 풀이 구현 문제다. 달팽이처럼 뱅글뱅글 돌면서 순회를 하는 문제다. 구현하는 방식을 알아두자. 코드 #include #include int n, k; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; bool visited[1003][1003]; int arr[1003][1003]; bool movable(int r, int c, int d) { int nr = r + dir..

다시 보려고 모은 알고리즘 개념 링크

2021. 10. 30. 12:41 Algorithm/개념

마스터 정리 https://jcdgods.tistory.com/380 [알고리즘] 시간 복잡도 계산 / 마스터 정리 시간 복잡도 계산, Master's theorem / 마스터 정리 1. 시간 복잡도 시간 복잡도란? 특정한 프로그램의 실제 동작 시간이 아닌, 입력 데이터의 크기 n에 대하여 기본적 연산의 횟수를 측정하는 것을 의 jcdgods.tistory.com 이분 탐색 https://www.acmicpc.net/blog/view/109 이분 탐색(Binary Search) 헷갈리지 않게 구현하기 개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo

백준[11003] 최솟값 찾기

2021. 10. 29. 21:22 Algorithm/BOJ

문제 링크 http://icpc.me/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 덱을 이용하여 풀 수 있다. 덱에 들어있는 값을 단조적으로 유지하면서 k번째 값이 들어올 때 그 k번째 값이 덱에서 가장 큰 값을 유지하게 덱을 관리하면 된다. 또한 덱에는 k - l - 1 이후에 들어온 값만 있어야 한다. 덱을 위와 같이 관리하면 덱의 제일 앞에 있는 값이 최솟값이 되게 된다. cf) 세그먼트 트리를 이용하면 O(nlogn)에 풀 수 있을 것 같지만 상수 때문..

백준[5430] AC

2021. 10. 29. 17:43 Algorithm/BOJ

문제 링크 http://icpc.me/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 덱을 이용하여 풀이 할 수 있다. 배열을 뒤집을 때, 진짜로 배열을 뒤집게 된다면 이때 시간복잡도가 O(n)이기 때문에 O(np)가 되어 터지게 된다. 그렇기 때문에 배열을 뒤집었는지 여부를 체크하여 수를 앞에서 버릴지 뒤에서 버릴지 정해야한다. 코드 #include #include #include using namespace std; void solve() { deque dq; string cmd; cin >> cmd; int n; cin >> n; string i..

백준[16234] 인구 이동

2021. 10. 29. 14:32 Algorithm/BOJ

문제 링크 http://icpc.me/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 dfs를 이용한 구현 문제다. bfs로 풀어도 똑같을 것 같다. 문제의 조건에 주어진대로 모든 점을 순회하면서 연합이 생기는지 확인하고 연합이 생긴다면 그 점들의 인구를 평균으로 바꿔주면 된다. dfs를 순회하면서 연합이 되는 점들을 스택에 담아 두었다가 순회가 끝나고 스택에 있는 점들을 모두 평균으로 바꿔주는 방식으로 구현했다. cf) 반복문에서 재귀를 호출할 때 retuen dfs(); 와같이..

티스토리툴바