알고리즘

문제12. 발전기 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 이차원 리스트의 각 칸들을 전부 돌면서, 1이라면(전력공급이 아직 안됐다면) 발전기를 설치하는 문제이다. 중요한 것은 전력이 공급된 곳의 상하좌우에 있는 집도 전력이 공급된다는 것이다. 즉, 발전기를 하나 설치할 때, 연쇄적으로 영향받는 집이 있는지를 체크해줘야한다는 것이다. 가장 먼저 생각할 수 있는 것은 재귀함수이다. 전력이 공급된 집의 상하좌우 집들에도 전력 공급이 되고, 또 전력을 공급받은 집의 상하좌우 집들에 전력이 공급된다. 이러한 구조는 재귀로 간단하게 구현할 수 있다. 아래 코드와 같이 상하좌우 집들 중에 아직 전력이 공급되지 않은 집에 한해서 ..

문제11. 통증 (2) 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 저번주 챌린지 문제였던 "문제8. 통증"에서 조건이 더 일반화된 문제이다. 예전의 문제는 회복 수치가 고정되어있었고, 서로 배수 관계였기 때문에 그리디 알고리즘을 적용할 수 있었다. 오늘 문제는 회복 수치가 고정되어있지 않고 배수 관계가 아니라는 것에 집중해야한다. 예전과 같은 유형의 문제이기 때문에, 큰 문제를 작은 문제로 쪼개어서 풀 수 있다는 최적 부분 구조를 만족한다. 다만, 탐욕적 선택 특성은 만족하지 않는다. 이럴 때 가장 먼저 떠올릴 수 있는 방법은 재귀이다. 생략이 많지만, 아래와 같은 재귀 함수를 적용하면 어렵지 않게 풀 수 있다. def..

문제10. GameJam 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제해결방법 보드게임의 규칙을 그대로 코드로 구현해야 하다보니 규칙을 정확하게 이해해야하는 것이 중요한 문제이다. 규칙이 은근 복잡해서 문제를 이해하는 데에는 시간이 조금 걸렸지만 구현 자체는 어렵지 않다. 방향과 이동할 칸 수에 대한 정보를 담고 있는 이차원 리스트와 함께, 각 플레이어들의 이동한 자취를 표시하기 위한 이차원 리스트를 같이 사용해야한다. 플레이어(또는 구름이)의 현재 위치에 따라 이동할 방향과 칸 수를 해석하고, 그만큼 이동하면서 자취를 남긴다(방문한 칸은 1로 바꿔서 표시). 계속 반복하다가 이미 방문했던 칸으로 이동하게 되었다면, 지금까지 이동한 ..

문제9. 폭탄 구현하기 (2) 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 2 차원 리스트를 두 개를 운용해야한다는 점만 고려하면, 완전탐색을 이용하여 간단하게 구현되는 문제이다. input 값으로 주어지는 k 개의 (x,y) 좌표와 그 주변 영역에 대해서 고려할 사항은 아래와 같다. (문제에서는 (y,x) 좌표라고 언급되었지만, 편의 상 (x,y)로 사용하였다.) 위, 아래, 왼쪽, 오른쪽이 N * N 영역의 밖에 위치한 경우는 무시된다. 땅 상태가 "#"이라면, 그 땅은 영향받지 않는다. 땅 상태가 "0"이라면, 폭탄 값을 1 증가시켜야 한다. 땅 상태가 "@"라면 폭탄 값을 2 증가시켜야 한다. 우선 1번 조건은 폭..

문제8. 통증 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 사용해야하는 회복 아이템의 총 개수를 최소로 하는 방법을 찾아야 한다. 각 아이템의 회복 수치를 보면 붕대(bandage)는 1, 약(medicine)은 7, 진통제(painkiller)는 14의 수치를 회복시켜 준다. 중요한 점은 서로가 서로의 배수라는 점이다. 같은 수치를 회복한다고 했을 때, 진통제를 사용하는 대신 약을 사용하면 2배 더 많은 회복 아이템을 사용해야 한다. 약을 사용하는 대신 붕대를 사용하면 7배 더 많은 회복 아이템을 사용해야한다. 심지어 진통제 대신 붕대를 사용하면 14배 더 많은 회복 아이템을 사용해야 한다. 즉, 사용해야하는 회복 아이..

문제7. 구름 찾기 깃발 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 각 깃발칸에 대해서, 그 칸에 들어갈 숫자가 k 인지를 알기 위해서는 직접 그 주변의 칸들을 탐색해보는 수밖에 없다. 모든 칸을 돌면서 그 주변 8칸에 구름이 몇 개 있는지를 확인하고, 그 결과가 k와 같은지를 확인하면 되는 간단한 문제이다. 주의할 사항들은 다음과 같다. 리스트의 숫자를 업데이트 하면 안 된다. (주변 구름이 1개여서 그 깃발칸이 1로 업데이트 되었다면, 다른 깃발칸의 입장에서, 1이 된 깃발칸을 구름으로 착각하게 된다. 만약 모든 칸의 결과를 업데이트하는 방식을 원한다면, 구름칸을 -1로 바꾸는 등의 방식이 필요하다.) 구름칸은 탐색..

문제6. 문자열 나누기 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 내가 생각해낸 방법대로라면, 다음 두 가지 단계가 필요하다. 문자열 S를 3등분했을 때 나올 수 있는 문자열의 모든 경우를 담은 리스트 P를 만든다. 리스트 P를 이용해 각각의 가능한 경우에 얻을 수 있는 점수를 계산하여, 최댓값을 얻는다. 우선 중복없는 리스트 P를 만들기 위해 집합에 가능한 모든 경우를 담아준 다음, 리스트로 변환하여 정렬해주었다. 그 다음, 이전에 구했던 것과 마찬가지로 가능한 모든 경우를 확인하면서, 리스트 P의 몇 번 인덱스에 있는지를 이용해 점수를 구했다. 위 내용을 코드로 구현하면 아래와 같다. n = int(input()) ..

문제5. 이진수 정렬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 2진수로 나타냈을 때의 1의 개수가 많은 순으로 정렬하되, 1의 개수가 같다면 10진수를 기준으로 더 큰 값이 먼저 배치될 수 있도록 하는 문제이다. 내가 생각한 방법은 총 3개의 배열(리스트)을 필요로 한다. 10진수를 담을 리스트 - 리스트1 2진수로 변환된 문자열을 담을 리스트 - 리스트2 각 2진수에 포함된 1의 개수를 담을 리스트 - 리스트3 위 3개의 리스트를 가지고 다음과 같은 순서로 문제를 해결한다. 리스트1을 내림차순 정렬한다. (나중에 1의 개수가 같을 때, 큰 것이 먼저 배치될 수 있도록 하기 위함) 리스트1의 순서와 동일한 순서로 리스..