본문 바로가기

Algorithm9

[구름톤 챌린지] 4주차 학습 일기 #2 (20일차) & 후기 문제 링크 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 문제 설명 입력 출력 문제 이해이전에 풀었던 발전기랑 풀이 방식이 굉장히 유사하다.1. 상하좌우로 같은 알파벳이 있으면 이동하여 다시 상하좌우를 비교한다.2. 1을 더 이상 상하좌우에 같은 알파벳이 안 나올 때까지 반복한다.(DFS를 사용)3. 총 반복 횟수 + 1(처음 자리)가 연결 요소의 개수이다.4. 연결 요소를 저장한 vector의 size를 확인하여 k개 이상이면 해당하는 칸에 알파벳을 점으로 변경해 준다.5. 1~4까지의 행위가 문제 설명에 있는 작업이며 이를 q번 반복하면 끝난다. 문제 해결 1. DFS함수와 연결 요소를 저장할 vector인 save를 만들.. 2023. 9. 9.

[구름톤 챌린지] 4주차 학습 일기 #1 (16일차) 문제 링크 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io문제 설명 입력 출력N개의 섬 사이에 존재하는 연합의 수를 출력한다. 문제 이해양방향을 확인하는 것까지는 쉽게 구현을 했고 이후 BFS를 이용하여 문제를 해결한 뒤 인터넷의 다른 사람들의 해결 코드를 살펴보다가 Union - Set 알고리즘을 이용한 코드가 흥미로워 코드를 변경하였다.1. 초기 입력은 단방향이다.2. 양방향인지 검사해준 후 (3) BFS를 사용하거나, (4) parent 배열(연합 정보)을 만들어 연합의 root를 저장한다.3.BFS3-1. 양방향인걸 이미 검증했으니, 그래프 간 연결을 확인해보면 된다.3-2. 그래프의 연결 확인이 모두 끝나면 방문했던 섬들을 다 방문했.. 2023. 9. 5.

[구름톤 챌린지] 3주차 학습 일기 #2 (14일차) 문제 링크 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io문제 설명 입력 출력마지막으로 방문한 노드의 번호와 방문한 노드의 수를 출력한다. 문제 이해결론부터 말하자면 dfs를 이용하여 문제를 해결했는데, 유추 과정은 이러했다.1. 그래프가 모든 노드를 들리는지는 미지수이다.2. 한번 방문한 건 다시 가지 못한다.3. 그래프에 연결된 간선의 개수가 많다면 제일 작은 노드와 연결되어 있는 간선을 선택한다.4. 위의 3가지 상황을 종합했을 때, 어떻게 연결되어 있는지 잘 모르는 그래프를 시작점만 주고 탐색하여 끝이 어딘지를 찾는 것이다.5. 따라서 현재의 노드부터 이어 나가면서, 노드의 끝까지 탐색해 보는 깊이 우선 방식이 적합하다고 생각했.. 2023. 9. 1.

[구름톤 챌린지] 3주차 학습 일기 #1 (11일차) 문제 링크 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 문제 설명8일 차의 문제와 유사하지만, 이번엔 아이템의 감소 수치가 정해져 있지 않다. 입력 N의 범위는 2부터 10의 6 제곱까지이다.아이템 A, B의 범위는 2 출력통증을 0으로 만들어주는 아이템의 최소 개수를 출력한다. 문제 이해처음엔 이전 통증 문제과 같이 단순 빼기 연산을 이용해서 문제를 풀었었다. 그런데 빼기 연산만을 사용할 경우에는 문제에 있는 예제 중 10000, 4, 13과 같이 0이 나올 수 있는 결과가 있음에도 불구하고 단순 계산으로 0이 나오지 않는 결과가 나오는 것을 확인하였다. 따라서 문제의 풀이 방식을 바꿔야 할 필요가 있다. 1. 처음에 주어지는 숫자를.. 2023. 8. 28.

[구름톤 챌린지] 2주차 학습 일기 #2 (8일차) 문제 링크 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 문제 설명구름-그라운드 게임에는 통증이라는 시스템이 있다. 해당 통증은 아이템을 이용하여 치료가 가능하다.bandage: 통증을 1 줄여준다.medicine: 통증을 7 줄여준다.painkiller: 통증을 14 줄여준다.아이템을 썼을 때, 통증이 0 밑으로 내려가면 안 되고, 최소의 아이템만 써서 통증을 0으로 만들어 보자. 입력통증 N은 1부터 10의 9 제곱까지 입력 가능하다. 출력통증을 0으로 만들어주는 아이템의 최소 개수를 출력 문제 이해1. 아이템의 최소 개수니까, 통증을 크게 줄여주는 painkiller부터 해서 쭉쭉 써나가면 된다. 문제 해결#1. 입력된 N.. 2023. 8. 24.

[구름톤 챌린지] 2주차 학습 일기 #1 (6일차) 문제 링크 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 문제 설명길이가 N인 문자열 S가 주어진다. 플레이어는 문자열 S를 서로 겹치지 않는 3개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가 1 이상이어야 하며, 원래 문자열에서 연속해야 한다.문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다.문자열 S를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 P라고 한다.나누어진 3개의 문자열이 각각 P에서 i,j,k번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 i+j+k이다. 입력첫째 줄에 문자열의 길이 정수 N이 주어진다.둘째 줄에.. 2023. 8. 22.

이전 1 2 다음

티스토리툴바