Algorithm
-
c++ 자료형 범위 체크하기Algorithm 2020. 11. 11. 13:43
int와 long long의 선택 조건 백준 문제 해결 시 overflow로 '틀렸습니다'를 만나는 경우가 종종 있다. 그래서 미리 범위의 경계를 기억하기 위해 기록한다! int 정수 자료형 Int는 32 / 64 비트에 상관 없이, 4바이트의 정보를 기록할 수 있다. signed int(부호 있는 정수)를 기준으로, 기록할 수 있는 범위는 0 ~ 2,147,483,647이다. (21억) 단, 계산 시 int의 범위를 넘어가면 overflow가 발생할 때가 존재한다. (파도반 수열과 같은 문제) 이럴 때에 long long을 사용해주자. long long 8바이트의 공간을 가지는 자료형이다. signed long long을 기준으로 하면, 최대 계산 가능한 양의 정수 범위는 0 ~ 9,22..
-
[BOJ] #17472 다리 만들기 2Algorithm 2020. 11. 11. 13:41
[BOJ] #17472 다리 만들기 2 삼성 역량테스트 문제였다 MST와 BFS 구현 위주의 문제라 그냥 끝까지 풀어보았다. 그리고 엣지케이스가 생각보다 많아서 꽤 오랜 시간이 걸렸다(..) FLOW 각 섬을 Numbering해야한다. BFS로 진행하였다. 섬과 섬 사이의 거리를 구한다. 이 때, 꼭 일직선으로만 진행해야한다.(진행 후 벡터에 저장하여 edge값으로 사용했다.) 각 섬간의 관계를 가중치 그래프로 나타낸 뒤, Kruskal Algorithm을 적용한다. 가중치의 합을 구하다 보면 result가 0일 때에만 cout= n) { continue; } if (vis[nextX][nextY]) continue; if (map[nextX][nextY] == 1) { map[nextX][nextY] ..
-
[BOJ] #11967 불 켜기Algorithm 2020. 11. 11. 13:36
[BOJ] #11967 불 켜기 문제 농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 베시가 불을 켤 수 있는 방의 최대 개수를 구하시오. 입력 첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다. ..