목록알고리즘 (89)
개발자 김수진
[문제] https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net [풀이] 배열이 주어지고 해당 배열에 찾고자 하는 숫자가 있으면 1을 출력하고 없으면 0을 출력하는 문제이다. 따라서 이진 탐색으로 풀어야겠다고 생각했다. 먼저 입력 받은 배열을 오름차순으로 정렬시킨다. BinarySearch 함수에서 이진 탐색으로 해당 값을 찾으면 true를 반환하고 존재하지 않는다면 false를 반환 [코드] 시간 : 72..
[문제] www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [풀이] 도시간의 연결 정보가 주어지고, 여행 경로가 주어진다. 도시가 연결되어 있으면 이동할 수 있고 연결되어 있지 않다면 이동할 수 없다. 여행경로를 통해 여행을 할 수 있는지 구하는 문제이다. 이 문제는 유니온 파인드(Union-Find)를 통해 풀었다. 먼저 parent 배열을 자기 자신으로 초기화 해준다. 연결정보를 입력으로 받으면 두 개의 node에 대해 parent를 같게 해주어 하나의 집..
[문제] www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] 처음에 파이프는 가로 방향을 (1,1)과 (1,2)에 위치한다. 파이프는 회전을 할 수 있으며 파이프가 이동하여 (N,N)에 도달할 수 있는 방법의 수를 출력하면 된다. BFS 방법으로 풀어보고 DFS 방법으로도 풀어봤다. - BFS visited 배열을 사용해 좌표와 현재 방향과 앞으로 나아갈 방향을 가지고 방문한 곳은 1로 update 해주었다. 이미 확인한 곳은 ..
[문제] www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net [풀이] 1. 낚시왕 이동 낚시왕은 열을 기준으로 한칸씩 움직인다. 2. 낚시왕 낚시 낚시왕은 자신이 존재하는 열에서 가장 가까운 물고기를 잡는다. 3. 물고기 이동 물고기는 1초에 속력만큼 이동한다. 이 때 범위를 벗어나면 방향을 바꿔서 움직인다. 시뮬레이션 문제로 낚시하는 함수인 fishing과 물고기가 이동하는 함수인 move를 구현하여 풀었다. 물고기들의 정보를 구조체에 저장..
[문제] https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net [풀이] Union-Find (혹은 Disjoint-Set)을 사용해서 풀었다. 입력 값이 문자로 주어지기 때문에 map을 사용했다. parent 배열에는 해당 index의 부모 노드 index를 저장했고 number 배열에는 부모 index를 기준으로 해당 set에 속한 노드의 개수를 저장했다. map의 count 함수를 사용해 이미 존재하는 친구인지 아닌지를 확인한다. 존재..
[문제] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net [풀이] 아기 상어와 물고기가 존재. 아기 상어는 자신보다 작은 물고기들을 잡아먹을 수 있다. 아기 상어는 자신보다 큰 물고기가 존재하는 칸은 지나가지 못한다. 아기 상어는 1칸 움직이는데 1초 걸린다. 아기 상어가 자신의 크기만큼 물고기를 먹는다면 크기가 1 증가한다. ( 크기가 3인 상어가 물고기 3마리를 먹으면 크기가 4가 된다.) 입력으로는 공간의 크기와 상태가 주어진다..
[문제] https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [풀이] N,M,K가 주어지고 K년 후에 남아있는 나무의 수를 출력하면 된다. 따라서 for 문을 K년 동안 돌리고 for문에서 봄, 여름, 가을, 겨울에 대한 함수를 호출했다. 봄 - 에는 나무가 영양분을 먹는다. 단, 한 좌표에 나무가 2개 이상이면 나이가 어린 순서부터 영양분을 먹는다. 영양분이 부족하다면 먹지 못하고 나무는 죽는다. 여름 - 봄에 죽은 나무가 양분으..
[문제] https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net [풀이] 인구 차가 L 이상, R 이하라면 queue와 vector에 넣어서 인구 이동 할 수 있는 좌표 모두 구하고 마지막에 인구 평균 구하고 map을 평균 값으로 update 해준다. queue는 BFS로 풀기 위해서 사용 vector는 나중에 인구 이동 하고 인구 수 update 하기 위한 좌표들 저장 solve 함수에서 평균 인구 수 구하고 vector에 저장된 ..