JEVLOG

17143. 낚시왕 문제에서 주어진대로 진행하는 시뮬레이션 문제이다. 정렬을 편하게 하기 위해 상어 구조체를 만들고 크기순, 번호순으로 정렬하기 위한 compare함수를 선언하였다. 풀이 과정 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열에 있는 상어 중에서 가장 땅과 가까운 상어를 잡는다. 이때, 상어를 잡으면 잡힌 상어는 격자판에서 사라진다. 상어를 이동시킨다. 1~3과정을 낚시왕이 맨 끝 자리로 이동할때까지 반복한다. 소스코드 #include #include #include using namespace std; int dx[] = { 0,-1,1,0,0 }; int dy[] = { 0,0,0,1,-1 }; int ans; int map[101][101]; int curDir; int mov..

17135. 캐슬 디펜스 브루트포스 + 시뮬레이션 문제였다. 문제에 써있는 내용대로 궁수 3명의 위치를 선택 후 시뮬레이션을 진행하여 풀면 된다. 풀이 과정 궁수 3명의 위치를 선택한다. (go 함수) 적을 공격하고 적이 이동하도록 시뮬레이션해준다. (Simulate 함수) 궁수는 자신으로부터 거리가 D이하인 적 중에서 가장 가까운 적을 공격한다. 거리가 가까운 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 모든 적이 맨 아래로 이동하여 제외될때까지 반복한다. 1~3 과정을 반복한다. 소스코드 #include #include #include using namespace std; int map[16][16]; int n, m, d; int ch[3]; int ans; int endLine=-1; ..

TopologySort(위상정렬) TopologySort란? 순서가 정해져있는 작업을 수행해야 할 때 그 순서를 정하기 위해 사용하는 정렬 알고리즘이다. DAG(Directed Acyclic Graph : 사이클이 없는 방향 그래프)에만 적용이 가능하다. 정렬의 결과는 여러가지가 나올 수 있다. TopologySort의 시간 복잡도 시간 복잡도 : O(V+E) (정점의 개수 + 간선의 개수) TopologySort의 구현 진입차수가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 간선 제거 후에 진입차수(특정한 노드가 있을때 그 노드로 들어오는 다른 노드의 개수)가 0이 된 정점을 큐에 삽입한다. 큐가 빌 때까지 2~3의 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 비..

17779. 게리맨더링 2 주어진 조건대로 구현하면된다. 마름모로 선거구를 나타내는것이 다소 까다로웠던것 같다. 마름모를 나눌때 brute force 방식으로 나눠도 정답이 나왔다. 풀이 과정 마름모로 선거구를 나눈다. 마름모 끝점 4개를 저장해서 끝점을 활용하여 나머지 구역 4개도 구한다. 구역을 나눈것을 기존의 입력으로 받은 map과 매핑하여 각 선거구의 총 인원수를 구한다. 최대 최소의 차이를 구하고 그것이 최소인 경우를 저장한다. ※ 구역을 나눌때 5번 구역은 마름모를 이루는 변을 5로 저장해 두고 내부는 1로 저장해두었다. ※ 나머지 1~4번 구역을 정해주면 0으로 남은건 알아서 5번구역으로 처리해줄수 있을거라 생각하였기 때문이다. 소스코드 #include #include using namesp..

15649. N과 M (1) 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제이다. 최근에 역량 테스트에서는 거의 모든 문제에 N개중 M개를 고르는 것이 기본으로 들어가 있고 고른 것을 바탕으로 시뮬레이션을 하기 때문에 N개중 M개를 고르는 문제는 기본기로서 상당히 중요하다고 생각한다. 기본적이지만 선택하는 것이 꼬이면 끝까지 꼬일 수 있다고 생각한다.(개인적으로 경험이 있어서...) 풀이 과정 선택한것은 중복으로 선택하지 않기 위해 visit배열을 따로 만들었다. 선택하지 않았다면 선택후 visit를 true로 바꿔주고 go함수를 재귀 호출 하였다. count개만큼 선택했다면 저장한것들을 출력해주고 반환하였다. 반환하면서 visit도 false..

17471. 게리맨더링 역량테스트에 나왔던 문제라고 해서 풀어보았다. 단순 알고리즘 적용보단 알고리즘 적용한 결과를 가지고 또다시 알고리즘을 적용하거나 시뮬레이션을 돌리는 형태로 문제가 많이 나오는 것 같다. 풀이 과정 선거구를 2개로 나눈다. N개의 구역이 있다면 N/2까지 나눠봐야 한다. 즉 N=6이면 (1,5), (2,4), (3,3)으로 나누면 된다. 지역을 나누는 것은 조합 짜듯 구현하였다. (go함수) 지역을 나누고 나선 나눈걸 각각 firstRegion, secondRegion에 넣어준다. 넣어준 것을 가지고 각 선거구 안에 있는 지역의 번호를 가지고 BFS를 돌려서 모두 연결이 되어있는지 확인하였다. (isConnected함수) firstRegion, secondRegion 모두 연결이 되..