초콜릿 파워

문제에서 요구하는 연합의 개수가 곧 우리가 평소 풀던 그래프 문제의 다리 역할을 한다. 하나만 연결되어있는 다리는 연합끼리 이어주기는 하지만 그 이상, 그이하도 아니다. 애초에 연합이어야 다른 연합이랑 이어질 수 있기 때문에, 연합인지 아닌지 판별해서 그래프 탐색을 하는게 중요하다. 따라서 처음엔 연합판별을 한 후 새로운 그래프를 만들어서 탐색하려다가, 그냥 평범한 BFS 에서 한번더 반대편 다리도 체크해서 queue에 넣는 작업 하나와, 2001 짜리 visited 배열로 섬 방문 여부를 확인할 수 있도록 했다. #include #include using namespace std; long long N,M; int graph[2001][2001] ={}; int visited[2001] = {}; /*..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이문제랑 같은 문제다. 보자마자 생각이 났지만 3주차는 DP 가 주제였기 때문에 혼란스러웠다. 대체 dp 로 어떻게 푸는 건지 너무 궁금하다. !!!! 유형이 틀린거라면 구름은 알고리즘 문제 만드는 사람 최소 10명을 뽑던지 이쪽 사업은 접는게 나을 것 같다. 너무 심각해.. 친구들이랑 같이 성취감있게 문제푸는 건 좋은데 덜 challenging 하고, 난이도가 낮은 점, 테스트케이스나 뭔가 에지케..

다이나믹 프로그래밍을 이용해서 구현했다. dp[i] = i의 통증을 0으로 만드는 데 필요한 최소 아이템의 개수 라고 정의하면, i의 통증이 생긴 경우는 i-A의 통증에 A 가 더해진 경우, i - B의 통증에 B 가 더해진 경우를 제외하고는 고칠 수가 없다. 다르게 말하면 i의 통증은 A의 아이템을 써서 i- A 의 통증으로 가라앉을 수 있고, B 아이템을 써서 i - B의 통증으로 가라앉을 수 있다.\ 그 외에 해당하는 통증은 해결 될 수 없다. 0통증을 해결하는 최소 아이템 개수 = 0이고, 이후에 [A] 통증을 해결하면 0 + 1, [B] 통증을 해결하는데 [0] + 1 개의 아이템이 필요하다. 쭉쭉쭉 가서 ... (i) 의 통증을 해결하는 개수는 (i-A) 의 통증을 해결하는데 필요한 개수 + ..

8.22 화요일 구름톤 문제! 무지 쉬운 완전탐색이었다. 근데 count 함수에서 입력이 (0,0) 일때, (-1,0) 등에 접근할 수 있는 위험이 있는데 이런 부분은 안 잡아주었다. 이렇게 풀었지만 #include using namespace std; long long N, K; int board[1001][1001]; int dist[1001][1001]; void count (int r, int c){ int dir[8][2] = {{1,0}, {-1, 0}, {0,1}, {0,-1}, {1,1}, {-1, 1}, {-1, -1}, {1, -1}}; int count = 0; for(int i = 0; i < 8; i++){ int x = r + dir[i][0]; int y = c + dir[i]..

이번 문제는 난이도가 확 올라갔다. ㅠㅠㅠ... 중복 부분 문자열을 제거하고 사전 순으로 정렬하는 부분을 제대로 구현하지 않아 생긴 문제가 많았다. ㅠㅠ...,, 구현한 코드는 다음과 같다. 눈여겨 볼 점: 중복을 피하기 위해 map 을 사용했는데 중요한 점은 map은 저장 순서가 유지되지 않고 어차피 사전순으로 정렬되면서 알아서 저장된다. 그래서 iterator를 이용해서 점수를 차례대로 넣어주면 사전순이 구현된다. #include #include #include using namespace std; int main() { int N; map m; string str; cin >> N; cin >> str; //map 에 넣고 저장. 하고 없으면 점수 제거. //str[0] -> 개수 1개, ... 개..

구름톤 챌린지라는 걸 처음 알아서 들어가봤다. 구름 이라는 곳은 아직 완전히 파악하지는 못했지만 코딩테스트를 위한 공간과 IDE 작성할 수 있는 컨테이너도 제공하는 곳이다. 구름이란? 회사 소개에 따르면, 구름은 ‘모두가 개발자가 된다’라는 비전으로 언제 어디서나 AI∙SW 개발을 배우고, 원하는 결과물을 구현할 수 있도록 ‘개발자 성장 중심’의 생태계를 만들어 나가고 있는 곳 이라고 한다. 카카오프렌즈와 함께하는 코딩운동회 콘텐츠 운영 실시간 화상 감독 서비스 ‘옵저뷰’ 출시 카카오엔터프라이즈-한국과학창의재단 업무협약 체결 SaaS 및 교육 분야 협업을 위한 카카오엔터프라이즈 업무협약 체결 등의 성과를 내고 있는 곳이다 . 구름 서비스 우리가 활용할 수 있는 전반적인 서비스는 다음과 같이 3가지 형태다..

오랜만에 돌아온 알고리즘 공부 시간! 세그먼트 트리의 필요성 A1, A2, … AN 의 수열이 있을 떄, L, R을 입력 받아서 AL 부터 AR 까지의 수열의 합을 구하라. → 이런 쿼리가 있다면, 누적합을 이용해서 sum[R] - sum[L-1]을 통해서 쉽게 구할 수 있을 것이다. → 하지만, 이렇게 누적합을 구하는 과정에서 중간에 수열의 값이 변한다면, 각각의 누적합에 대해 연산을 실시해야하므로 O(N) 의 시간복잡도가 걸린다. → 이러한 연산을 효율적으로 실행할 수 있게 해주는 기법이 세그먼트 트리 기법이다. 세그먼트 트리란 각 노드는 특정 구간을 대표한다. 노드들은 이진트리 구조를 이룬다. (부모 노드가 대표하는 구간은 자식 노드가 대표하는 구간의 합집합이다. ) 총 길이는 2^k 꼴일 때, 비..

이전 글 보러가기 : https://ebang.tistory.com/103 3. merge insert sort 그래서 결국 merge insert 는 뭔가하면, 배열을 쪼개고 다시 합병하는 과정이라는 점에서 merge sort, 원소가 들어가는 부분을 탐색하는 점에서 Insertion sort 의 포인트를 갖고 있는 알고리즘이라고 할 수 있다. 단 이전의 insertion sort 에서 설명된 것과는 다르게 삽입될 부분이 이진탐색으로 탐색된다. 이진 탐색은 이미 배열이 정렬되어있을 때, 특정 값이 들어갈 위치를 범위를 절반으로 줄여가면서 탐색하는 기법이다. (중간값보다 크면 그 이후 범위에서 다시 찾고, 중간값보다 작으면 그 이전 범위에서 다시 찾는 방식) 그리고 이게 핵심이다. binary searc..

개요 1. 소개 2. merge sort 3. insertion sort 4. binary search (이진 탐색) 4. Tim sort 1. 소개 꽤나 느린 알고리즘이고 특정 자료구조가 필요하다. (쌍으로 묶는... ) 하지만 컴퓨터 과학적인 관점에서 꽤나 흥미롭다 : 숫자 비교를 아주 최적화해서 하지는 못하지만, 비교의 횟수를 최소로 만드는 면에서는 가장 널리 알려진 알고리즘이다. The Art of Computer Programming, Volume 3 by Donald Knuth 에서 소개 되어있는 알고리즘이다. 이해하는데 이틀 ~ 삼일 정도 걸렸고 여태 알고 있던 알고리즘으로만 사고방향이 흘러서 그 틀을 깨는데 가장 시간이 오래걸렸다... 그래도 찬찬히 뜯어본만큼 기록으로 남겨두고 싶어서 글을..

13335 - 트럭 난이도: 실버1 구현방법: 시뮬레이션, 구현 문제 https://www.acmicpc.net/problem/13335 1 초 512 MB 9666 5039 4021 54.478% 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에..