(2차) 2022.04.12 스터디

오늘은 총 2 문제를 풀어오고 각자 코드에 대해 토론하였다.

1. 시저암호 

2. 소수찾기

해당 문제가 이번 스터디 과제였다.

---

시저암호

isalpha() 함수는 그저 알파벳인지만 확인하는 함수인지 알았는데 대소문자 구분도 가능한 함수였다.

이를 몰랐기에 대소문자를 구분하였는데 이 함수를 더 잘 활용할 수 있을 것 같다.

다른 친구는 해당 알파벳이 몇번째 자리의 알파벳인지를 구해서 'a' || 'A'에 index를 더하는 코드를 사용하였다.

나는 대소문자 구분과 n을 더했을 때 char의 범위를 벗어나는 것에 어려움을 겪었는데 각자 다른 방식으로 이를 해결하는 것이 신기했다.

---

소수찾기

아마 지금까지 해온 과제 중에 가장 어려운 과제가 아닌가 싶다.

나도 문제를 푸는데 하루 넘게 소요되었고 다른 친구들도 어려움을 토로하였다.

나는 3번의 시행착오 끝에 문제를 풀어냈다.

첫번째는 1~n까지 그 아래숫자를 나눠 떨어지면 소수가 아닌것으로 하여 코드를 풀었는데 이는 O(n^3)으로 시간초과를 받았다.

 

두번째는 에라토스테네스의 체라는 이론을 활용하여 문제를 풀었는데
이도 첫번째보다는 빠르나 O(n^2logn)정도의 시간복잡도를 가져 시간초과를 받았다. 

세번째는 밀러-라빈 이론을 활용하였는데 이또한 대략 O(n^2logn)의 시간복잡도를 가져 시간초과를 받았다.

프로그래머스의 질의응답 게시판에서 힌트를 얻어 문제를 풀 수 있었다.

소수를 구하는데에는 3가지 이론을 활용할 수 있는데

1.  모든 자연수는 소수의 곱으로 이루어져있다.
2.  자연수 n이 소수인지 알기 위해서는 1~루트 n까지의 수만 확인하면 된다.
3.  2가 아닌 짝수는 모두 소수가 아니다.

사실 이 이론들은 내가 시행착오를 하면서 겪어왔던 이론들이었다.

1번 이론은 밀러-라빈 이론을 활용하면서 사용했었다.

 

2번 이론은 에라토스테네스의 체를 활용하며 사용었다.

나는 해당 이론들을 활용하여 시간복잡도를 O(nlogn) 정도까지 낮출 수 있었다.

다른 친구들의 풀이도 형태는 달랐지만 해당 이론들을 활용한 것이여서 공통점과 차이점을 찾는 것이 즐거웠다.

 

풀이들은 아래 링크에서 확인할 수 있다.

시저암호

2022.04.12(화) 스터디 문제 1 : 시저 암호 · Issue #2 · MinaleeTeam/CodingTest_Study

소수찾기

2022.04.12(화) 스터디 문제 2 : 소수 찾기 · Issue #3 · MinaleeTeam/CodingTest_Study