[240215] 알고리즘 리부트 7일차 - 백준 10989, 3273 자바

[Part1-Chapter03-Clip04]

-백준 10989 수 정렬하기 3

 

위 문제는 시간 제한과 메모리 제한이 비교적 있는 편이라 단순히 삽입 정렬을 할 수는 없었다. 최악의 경우 모든 숫자를 배열에넣고 단순히 sort 매서드를 쓰기에는 메모리 제한에 걸리기 때문에 그렇게 풀 수 는 문제는 아니었고. 정수배열의 경우 인덱스 하나당 4바이트 인데 모든 수를 배열에 넣는다면 4천만 바이트로 메모리 제한에 걸리기 때문에 불가. 

주어지는 수의 갯수는 천개 이지만 수의 종류가 최대 10000이기 때문에 카운팅 배열을 활용하고자 했다. 입력을 받으며 해당하는 인덱스에 갯수를 늘려주고 입력되는 수의 최대값을 구해 놓으면 반복문을 돌 때 그 수를 줄일 수 있을 거라고 생각했다. 카운팅 배열에 오름차순으로 값을 넣기 때문에 순서대로 반복하며 출력하면 끝. 이때 스캐너 대신 버퍼드 리더와 버퍼드 라이터를 활용해서 시간을 줄였다. (런타임 에러는 배열 길이 +1 해놓지 않아서 발생)

 

 

참고로 Scanner와 BufferedReader 그리고 Println과 BufferedWriter는 실제로 실행 속도에 큰 차이가 있다. 백만 단위 이상의 수를 다루게 된다면 실제로 각 후자를 활용하는 것이 좋다. 아래의 링크에서 실행 시간을 확인해보자.

 

https://www.acmicpc.net/blog/view/56

입력 속도 비교

https://www.acmicpc.net/blog/view/57

출력 속도 비교

 

 

[Part--Chapter03-Clip05]

-백준 3273 두 수의 합

 

위 문제는 정렬과 투포인터를 혼합해서 풀었다. 일단 시간 제한이 1초 있기 때문에 이중 반복문을 돌지 않고 해결할 수 있으려면 투포인터를 활용해 양끝의 인덱스를 하나씩 옮겨가며 x값과 일치하는지 확인하면 된다. 2달 전에도 이 문제를 풀었는데 열어보니 완전 동일하게 풀었더라. 첫번째 풀이는 다시 열어보니 다소 로직을 헷갈려했던 것 같다. 그런데 오늘 풀 때는 명료하게 구현했으니 다행이라고 생각했다.

 

 

다음은 강사님께서 풀이한 방법이다. 카운팅 배열을 이용해서 각 수가 존재하는지 논리값을 넣어주고 1부터 x-1까지 합이 x를 만드는 값이 존재하는 경우에만 ans에 더해주는 방식인데 이 때 같은 수의 조합도 더해버리기 때문에 x-1이 아닌 (x-1)2 까지 반복문을 순회하면 중복으로 카운트 하지 않고 답을 출력할 수 있다. 이 때 각 인덱스가 배열의 범위를 벗어나지 않도록 체크해주는 것도 중요.

 

 

[Part1-Chapter04-Clip01]

 

 

완전탐색은 모든 경우의 수를 시도하는 것으로서 문제 해결의 가장 기본적인 방법이며 반드시 답을 도출해낸다. 하지만 시간이나 메모리는 고려하지 않는다는 단점이 있다. 즉, 별도의 최적화 없이 효율성을 고려하지 않는 풀이 방법이다. 

 

그만큼 문제를 정확히 이해하고 모든 경우를 검사할 수 있게 체계적으로 로직을 설계해야 하고 구현해야 한다. 문제의 크기가 작으면 부분 점수 문제라면 전체를 풀지 못해도 점수를 일부 얻을 수 있다. 이 위의 백준 3273 문제도 완전 탐색의 일종이다.

 

시뮬레이션은 문제에서 주어진 상황을 그대로 진행하며 해결해보는 기법을 말한다. 문제의 요구사항에 알맞은 코드를 모델링하고 문제의 조건을 체계적으로 수행하기 위한 구현력이 필요하다. 10158 개미 문제와 10431 줄세우는 문제가 시뮬레이션 문제의 일종이다. 하지만  이 역시 그대로 구현하면 효율성이 떨어질 수도 있다.