< 프로그래머스 LV3 입국 심사 >
키워드 : 이분 탐색
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public long solution(int n, int[] times)
{
long left = 1; // 최소 시간
long right = (long)times.Max()*n; // 최대 시간
long answer = long.MaxValue;
while ( left <= right)
{
long mid = (left+right)/2;
long people = 0; //각 데스크별 해결한 인원 합
foreach(var value in times)
{
people += (mid / value);
if (people >= n)
break;
}
if (people >= n) // 시간이 여유롭다
{
right = mid-1;
if (mid < answer)
answer = mid;
}
else // 시간이 부족하다
left = mid+1;
}
return answer;
}
}최초에는 접근 방법에 대해서 백트래킹이나 BFS 같은 방법을 생각했었습니다.
하지만 그렇게 해서 답을 찾기에는 제한 조건이 너무나 어려워 팁을 찾아보던 와중 이분 탐색을 이용하면 빠르게 풀이 할 수 있다는 것을 알게 되었습니다.
이분 탐색 : 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘 으로 최소/최대값 찾기에서 자주 사용된다
mid값을 지정하고 찾고자 하는 값이 mid 보다 크면 오른쪽을, 작으면 왼쪽을 탐색한다.
기본적으로 이분 탐색은 원하는 값이 있고, 그 값이 어디에 해당하는지를 찾는 것이라 생각했는데, 이 문제처럼 최적해를 찾을때도 사용할 수 있었습니다. 풀이 해석은 아래와 같습니다.
- 초기화시 left는 1(최소시간) right = times 배열중 가장 큰 값에 * n명 입니다.
- while문을 돌며 이분 탐색을 시작합니다. 이때 각 시간당 해결할 수 있는 인원을 people로 저장하고 n과 people를 비교합니다
- 만약 n이 poeple보다 크다면 시간이 부족한 것이므로 left 값을 mid로 옮겨 수정합니다. 반대의 경우에는 right가 mid가 됩니다.
- 시간이 여유로운 경우 최소값 갱신을 진행합니다.
이렇게 풀이에 대한 팁을 얻고 나서는 쉽게 풀이할 수 있었으나 또 한가지의 문제가 발생했습니다.
바로 long right = (long)times.Max()*n; // 최대 시간 에서 (long) 타입 변환을 해주지 않은 것 때문이었습니다. 이에 대한 답은 아래와 같습니다
long right = (long)times.Max()*n; 에서 타입 변환을 해주지 않는다면, times의 최대범위 1,000,000,000 / 최대 시간 1,000,000,000 의 곱이 되므로 int의 범위를 초과해 오버 플로우가 발생한다.
이 오버플로우를 사전에 해결하기 위해 적어도 둘 중 하나를 형변환 하여 사전에 방지해 주어야 한다.
문제를 정확히 풀었다고 생각했는데 소수의 케이스에서 틀린경우 위와 같이 오버플로우가 발생하는 경우가 있을지도 모르는 것을 잘 체크해 주어야 합니다.
< CS 공부 >
( 언어 스팩 )
더 깊은 CS 공부를 진행하기 전에 자료를 읽을때에 필요한, 자주 사용되는 용어들에 대해서 먼저 공부하고 넘어가고자 했습니다.
[ 객체 ]
객체는 class에 따라 실체화 된것으로 메모리에 할당됩니다. 필드와 메서드로 구성되어 있는 프로그램에서 기능을 실행시키는 단위입니다.
[ 클래스 ]
객체를 만드는 설계도 입니다. 객체의 특징인 프로퍼티(속성)을 가지고 행동읠 정의한 메소드를 가지고 있습니다. 객체 지향 프로그래밍을 위한 거푸집 입니다.
[ 인스턴스 ]
클래스를 가지고 실제 객체를 생성한 결과물로 객체는 클래스의 인스턴스 라고 할 수 있습니다. 객체를 생성하는 것을 인스턴스화 한다고 말합니다.
[ 필드 ]
흔히 변수라고 말하는것이 C# 에서는 필드 입니다. 클래스 안에서 선언된 변수를 필드라고 합니다. 예를 들어 달력 클래스에는 날짜를 나타내는 필드가 존재할 수 있습니다.
[ 메서드 ]
c/c++ 에서 함수 라고 부르는것이 c#에서는 메소드 입니다. 이는 행동을 나타냅니다.
[ 추상화 ]
인간이 인지한 개념이나 사물의 속성과 기능을 컴퓨터 언어로 모델링 하는 것을 의미합니다. 또한 이런 속성과 기능의 묶음을 앞서 말했듯 클래스라고 부릅니다.
[ static 멤버 ]
static 을 붙이면 정적, 그렇지 않으면 인스턴스 멤버가 됩니다. 정적 멤버의 경우 클래스이름 -> 멤버 이름으로 // 인스턴스 멤버는 객체 이름 -> 멤버 이름으로 접근합니다.
[ 멤버 ]
필드, 상수, 속성, 메서드 이 모든 것은 멤버 입니다. 멤버는 클래스 및 구조체에 해당 데이터와 동작을 나타내는 것을 의미합니다.
[ 프로퍼티 ]
프로퍼티는 객체의 상태를 안전하게 관리하는 방법중 하나로, 일반적인 필드보다 캡슐화에 유리합니다. 이는 C#에서 get 과 set 접근자로 구성할수 있습니다.
class Player
{
private int health; // 실제 값을 저장하는 필드
public int Health
{
get { return health; } // 값을 읽을 때 실행
set { health = value; } // 값을 변경할 때 실행
}
}
아래의 경우 Health가 프로퍼티에 해당합니다.( 배열과 리스트 )
배열은 동적 할당이 불가능하고, 리스트는 가능합니다. 즉 데이터를 할당할 때 데이터의 크기가 정해져 있다면 배열을, 그렇지 않다면 리스트를 사용하는게 좋습니다.
리스트
- 메모리가 동적이며, 무작위적이고 배열보다는 더 많은 메모리를 차지합니다.
- 속도가 느린 대신 메모리 낭비는 없습니다.
- 메모리 구조가 비연속 메모리로 할당되며, 이는 프로세스를 다양한 블록으로 분리하여 메모리 공간 가용성에 따라 다른 주소공간에 배치합니다
배열
- 메모리가 정적이며 연속적이고 효율적입니다.
- 실행속도도 더 빠르지만 메모리의 낭비가 있ㅅ브니다.
- 배열에 할당된 메모리 블록은 고정크기 메모리가 할당된하, 항목이 추가 될 때 까지 사용되지 않은 상태로 유지됩니다
- 메모리 구조는 연속 메모리 할당이 수행됩니다
결론
둘 중 하나를 선택해야 한다면 이는 데이터의 크기가 변하는지가 가장 큰 핵심입니다, 변한다면 리스트를 그렇지 않다면 배열을 사용하는 것이 좋습니다.
( namespace와 partial )
[ namespace ]
프로젝트를 협업하다 보면 불가피하게 클래스 이름이 중복 되는 경우가 있습니다. 이를 방지하기 위해 namespace를 사용합니다.
특히나 클래스는 오버로드가 작동하지 않기 때문에 중복을 피하기 위해서는 namespace를 사용해 주어야 합니다.
[ namespace ]
하나의 스크립트에 하나의 클래스를 작성한다고 할지라도 그 클래스의 크기가 엄청나게 커지는 경우가 존재합니다. 이 경우 가독성이 떨어지므로 파일을 분할 해야할 필요가 있는데 이때 사용하는것이 partial 입니다.
( Override와 new )
가상 함수가 포함된 클래스를 상속 할 때, 자식 클래스에서 재정의 할때 override와 new 두가지 한정자로 정의할 수 있다. 단 추상 메서드가 포함되었다면 override만 가능하다
[ override ]
부모 클래스에서 정의된 가상, 추상 메서드를 자식 클래스에서 재정의 할 때 사용합니다.
- 부모 클래스가 virtual 혹은 abstract로 선언되어 있어야 합니다
- 부모 클래스의 메서드와 같은 이름, 매개변수를 가져야 합니다.
- override는 부모 클래스의 참조를 통해서도 호출할 수 있으며 다형성을 지원합니다
[ new 키워드 ]
부모 클래스의 메서드나 속성과 동일한 이름을 가진 새로운 메서드나 속성을 자식 클래스에서 정의할때 사용하빈다. 이때 부모 클래스의 메서드는 숨겨집니다.
- 부모 클래스의 메서드를 재정의 하는 것이 아니라 숨깁니다
- 부모 클래스의 참조를 통해 메서드를 호출하면 부모 클래스의 메서드가 호출됩니다.
- 자식 클래스에서 새로운 동작을 정의 할 수 있ㅇ으나 다형성을 지원하지는 않습니다
- override: 부모 클래스의 가상 메서드 동작을 변경하면서, 부모 클래스의 참조로도 자식 메서드를 사용할 수 있도록 다형성을 유지.
- new: 부모 클래스 메서드를 숨기고, 자식 클래스에서 새로운 동작을 정의하지만, 부모 참조로는 부모 메서드가 호출됨.
