반응형

알고리즘/구름톤 챌린지 7

구름톤 챌린지 4주차 후기(2) - 18일차

교차점은 가로선과 세로선이 겹쳐서 만들어진다. 세로선, 가로선끼리는 서로 겹치지 않게 만들어지기 때문에, 세로선과 가로선이 서로 얼마나 겹치는 지에 따라 교차점의 개수가 달라진다. 예제1을 보면 아래 코드에서 주석처리된 표를 보면, 가로와 세로를 저장하는 배열을 만들어두었다가, 이 둘의 곱의 전체 합을 구하면 답이 된다. 초기 상태가 0이기 때문에, 교차하지 않는 경우엔 자동으로 0을 더하는 꼴이 되어 문제가 없다. 정답을 보자! #include using namespace std; long long garo[101][101] = {0,}; long long sero[101][101] = {0,}; long long N, M; long long ans= 0; /* 1 2 3 1 2 3 1 2 3 가로 :..

구름톤 4주차 후기 (1)

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

구름톤 후기 3주차 (2)

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

구름톤 3주차 후기 - 1

다이나믹 프로그래밍을 이용해서 구현했다. 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) 의 통증을 해결하는데 필요한 개수 + ..

구름톤 2주차 후기 - 2

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]..

구름톤 2주차 후기 -1

이번 문제는 난이도가 확 올라갔다. ㅠㅠㅠ... 중복 부분 문자열을 제거하고 사전 순으로 정렬하는 부분을 제대로 구현하지 않아 생긴 문제가 많았다. ㅠㅠ...,, 구현한 코드는 다음과 같다. 눈여겨 볼 점: 중복을 피하기 위해 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개, ... 개..

구름톤 챌린지 1주차 후기 (1)

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

728x90
728x90