백준 문제를 푸는데, 분명 로직이 맞는 것 같은데 안되는 경우가 있다.
1
2
3
4
5
6
7
int ma=-1;
for(int i=1;i<=n;i++){
if(ma < graph[i].size()){
ma = graph[i].size();
save = i;
}
}
이런 코드였는데 틀릴 만한 부분이 없는 아주 간단한 일만 한다.
그런데 실행하면 ma의 값이 -1에서 바뀌지 않았고, 그 이유를 못 찾아 1시간 동안 삽질을 했다..
도대체 문제가 뭘까 하고 코드를 다시 짜면서 ma를 0으로 고쳐봤는데 바로 맞았습니다!!라고 한다.
1
2
3
4
5
6
7
int ma=0;
for(int i=1;i<=n;i++){
if(ma < graph[i].size()){
ma = graph[i].size();
save = i;
}
}
ma가 -1이든 0이든 상관 없이 size()는 무조건 0이상이니까 당연히 둘 다 되어야 하는게 아닌가?
보통 최댓값 구할 때 ma에는 음수를 넣어주니까 아무 생각 없이 했는데 이것이 문제였다.
size()라는 함수는 c++ STL에서
1
inline std::size_t std::vector<int>::size()
라고 정의가 되어 있다. 즉 size_t 자료형을 반환하는 함수이다.
그런데 size_t를 또 열어보면
1
typedef unsigned int size_t
unsigned int를 다른 이름으로 size_t로 사용하고 있음을 알 수 있다.
int와 unsigned int의 차이점은 부호가 없다는 것이고 그것은 최상위 비트의 사용에 차이가 있다.
int에서는 최상위비트를 1로 함으로써 음수라는 것을 표현하고, 2의 보수법을 통해 저장한다.
그런데 unsigned int에서는 최상위비트도 숫자의 일부로 보기 때문에 엄청 큰 수로 이해하는 것이다.
1
2
3
4
5
6
7
int ma=-1;
for(int i=1;i<=n;i++){
if(ma < graph[i].size()){
ma = graph[i].size();
save = i;
}
}
이 코드에서 ma에 -1을 넣었지만 ma에 저장된 값을 unsigned int로 이해하면 ma는 엄청 큰 수가 된다.
그렇기 때문에 ma의 값이 조건문을 통해 바뀔리가 없고 잘못된 값을 출력하게 된다.
1시간 동안 맞는 코드를 들여다보고 있던게 억울하지만 지식이 또 늘었다..