[Coding test] (바킹독 실전 알고리즘) 0x03강 - 배열 (feat. Python)

INTRO

KEY POINT

배열의 성질 

 

1. O(1)에 k번째 원소를 확인/변경 가능

2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의없음

3. Cache hit rate가 높음

4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

* 임의의 위치에 있는 원소를 확인/변경 = O(1)

* 원소를 끝에 추가 = O(1)

* 마지막 원소를 제거 = O(1)

*임의의 위치에 원소를 추가/임의 위치의 원소 제거 =O(N)

 

강의에대한 내용정리는 바킹독님께서 친절하게 텍스트까지 남겨주시며 최고의 강의를 해주고 있으시니 이 블로그에서는 문제 풀이를 파이썬으로 풀어보기만 하도록 하겠습니다. 개념이나 내용이 궁금하다면 아래 링크에서 바킹독님의 강의를 듣는 것을 추천합니다.

 

3주차 배열 강의에서 진행한 실습 및 연습문제 파이썬 코드 풀이 입니다.

https://blog.encrypted.gg/927

[실전 알고리즘] 0x03강 - 배열

문제풀이

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x02.md

GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료

다음은 바킹독님이 강의를 마치고 각 강의에 맞게 올려주신 문제집입니다.

강의자인 바킹독님꼐서는 c++언어로 문제를 풀이 하셨기 때문에 저는 파이썬으로 알고리즘을 풀어보려 합니다.

 

2강 문제집은 기초문제가 많은 관계로 제가 풀면서 헷갈렸거나 배운 부분이 있던 문제만 업로드 하도록 하겠습니다.

 

직접 풀어본 파이썬 문제풀이

https://github.com/moonjoo98/Codingt_test_study

GitHub - moonjoo98/Codingt_test_study: 바킹독님이 올려주신 강의별 문제집 파이썬 풀이입니다.

위의 문제 풀이의 문제집 문제의 풀이를 C++로 하셨기 때문에 파이썬을 쓰는 저는 파이썬으로 문제를 풀어봤습니다.

 

 

문제 1. 백준 10808번

https://www.acmicpc.net/problem/10808

10808번: 알파벳 개수

Solution

우선 저는 두 가지 방법으로 문제를 풀어 봤습니다. 

 

solution 1 -> 아스키코드

ord는 문자를 숫자로 바꿔주는 함수로 ord('a')= 97이기 때문에 이를 활용하여 문제를 풀었습니다.

예를 들어, 입력 예제 baekjoon에서 첫번째 글자인 b부터 보면 ord('b')-ord('a') =1로 index[1]인 자리에 1을 더해줬습니다

이렇게 입력받은 문자 알파벳의 인덱스를 찾아 하나씩 더해주고 최종 리스트를 언패킹을 사용해 리스트를 출력

해주시면 문제를 쉽게 풀어 보실 수 있습니다.

 

solution 2 -> 아스키코드 사용 X

입력단어는 그대로 input으로 받아주고 알파벳 리스트와 알파벳 인덱스 리스트를 각각 생성해줍니다.

다음으로 이중 for문을 사용해 word의 단어와 alpha의 단어가 일치하면 인덱스 리스트인 arr에 1을 더해줍니다.

 

이 해결방법은 비효율적인걸 대충봐도 아실 수 있습니다. for문을 2번이나 쓰다니 시간복잡도..

 

 

문제 2. 백준 2577번

https://www.acmicpc.net/problem/2577

2577번: 숫자의 개수

solution

이 문제 역시 두 가지 방법으로 문제를 풀어 봤습니다. 

solution 1 

우선 num_변수에 [0,0,0,0,0,0,0,0,0,0] 0~9의 인덱스를 생성해줍니다.

그리고 sum_변수를 1로 지정해줍니다 그 이유는 0으로 설정해두면 0*n은 0이기 때문에 처음 입력받는 값이 0으로 되기 떄문에 값이 제대로 곱해지지 않기 때문입니다.

그 다음 자연수 3개를 입력 받으면 되기 때문에 for문을 통해 자연수 A,B,C를 입력하고 *= 연산자를 통해 값을 곱해줍니다.

 

A,B,C 자연수가 곱해진 결과값 sum_을 str함수를 이용하여 문자열로 반환하고 for 반복문을 통해 sum_의 첫번째 숫자의 값과 동일한 num_인덱스에 1씩 더해줍니다. 

그리고 최종적으로 출력 형태에 맞게 print() 함수에 언패킹을 적용해줍니다.

 

 

solution 2 

우선 a, b, c를 차례대로 받아줍니다.

str함수를 이용하여 문자열로 변환하고, list를 이용하여 각각의 문자를 요소로 가지는 리스트로 변환해줍니다.

그 후 count를 사용하여 그 리스트에 문자가 몇 개씩 있는지 print해줍니다.

 

문제 3. 백준 1475번

solution

solution 1

solution 2

이 문제 역시 두가지 방법으로 문제를 풀어봤습니다.

solution 1 

우선 arr변수에 [0,0,0,0,0,0,0,0,0,0] 0~9의 인덱스를 생성해줍니다.

 

그리고 입력값을 a로 받아줍니다. 입력 예제의 9999를 받았다고 가정하면 문자열 a는 9999가 됩니다.

for 반복문을 통해 a의 첫번째 숫자가 9이므로 arr리스트 9번째 인덱스에 +1을 해줍니다. 

두번째 숫자 역시 9이므로 arr리스트 9번째 인덱스에 +1을 해줍니다. 

이렇게 반복문이 종료되고 print를 하면 참 쉬울텐데 이 문제의 경우 6과 9는 뒤집어서 사용할 수 있다고 합니다.

그렇기 때문에 n은 1000000 보다 작은 숫자이므로 for문 range에 1000000을 넣어줬습니다.

그리고 조건문을 추가로 걸어서 만약에 arr의 6번째 인덱스가 9보다 작다면 둘이 같아질 때까지 9는 -1을 6은 +1을 해줍니다. 반대의 경우도 arr의 6번째 인덱스가 9보다 크다면 둘이 같아질 때까지 9는 +1을 6은 -1을 해줍니다.

그러다 arr 6번째 인덱스와 9번째 인덱스의 값이 같아지면 break를 하면 저장된 리스트 내 arr[6]과 arr[9]가 같아졌습니다.

 

그리고 마지막으로 출력값을 리스트의 값 중 최대값을 찾아주는 함수 max 함수를 사용하여 출력을 하시면 됩니다. 

 

solution 2 

다른 과정은 위와 비슷합니다. 이제 여기서 가장 중요한 것은 6,9를 동일 취급 하는 것입니다.

입력된 방번호를 하나씩 for 반복문을 통해 확인하고 6,9일 경우 동일 취급해서 하나의 변수

위의 solution에선 card_6n9의 값을 1 증가 시킵니다. 그 외의 숫자의 경우 1씩 증가 시킵니다.

입력예제로 예시를 들어보면 9997이라는 값이 input으로 들어가게 되면

card_6n9는 9가 총 3번 나왔으므로 3이 됩니다. 7도 나왔기 때문에 card[int(i)]에 7이 들어가서 card[7]도 1 증가합니다.

그러면 여기서 card = [0,0,0,0,0,0,1,0,0,0] 가 되고 card_6n9 =3 이게 되는데 이 값을 card[6]이나 card[9]에 넣어주시면 됩니다. 여기서 주의할 점은 card_6n9 값은 6과 9를 동일 취급 했기 때문에 2로 나눠줘야 합니다. 그리고 나누어 떨어지지 않는 경우엔 새로운 카드 세트가 필요하므로 나누기 2를 해준 값에 +1을 해주도록 합니다. 

 

마지막으론 solution과 동일하게 max(card)값을 뽑아 프린트해주시면 됩니다.

 

 

문제 4. 백준3273번

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

Solution

강의에서 바킹독님께서 다른 문제풀이를 하실 때 사용하신 방법으로 문제를 풀어볼라 했는데 시간초과가 나와서

투포인터 방식으로 문제를 풀었습니다. 

투포인터 방식은 좌, 우 방향의 인덱스를 이용하여 한 번의 배열 탐색으로 두 수의 합이 x가 되는 쌍을 찾을 수 있습니다.

투 포인터 탐색은 왼쪽, 오른쪽 방향의 인덱스가 서로 만날 때(교차할 때)까지 진행하면 됩니다.

 

1. 배열(arr)을 입력받고 정렬을 해주도록 합니다.

- 정렬을 하지 않으면 투 포인터를 정상적으로 사용할 수 없기 때문입니다.

 

 

2. left, right 를 이용하여 arr[left]와 arr[right]를 더해가면서 서로 교차할 때까지 진행합니다.

 

• 두 수의 합이 x인 경우 - count+1 & left+1
• 두 수의 합이 x보다 작은 경우 - 더 작은 값을 더해야하므로 right-1
• 두 수의 합이 x보다 큰 경우 - 더 큰 값을 더해야하므로 left+1

 

3. 결과(count)를 출력합니다.