목록알고리즘/백준 (65)
개발자 김수진
[문제] www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net [풀이] N,M이 주어지고 길이가 N인 배열에서 구간합이 M인 경우의 수를 찾아서 출력하는 문제 구간합 문제길래 이중 for문을 사용해서 풀려고 했다. 하지만 시간 제한이 0.5초인데 M의 범위가 1부터 3억이라서 이중 for문을 사용하면 시간초과가 발생한다. 따라서 구간합 구하는 알고리즘인 투 포인터 알고리즘을 사용해서 풀었다. start , end 를 배열의 첫번째 ind..
[문제] www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net [풀이] 시뮬레이션 문제로 문제 조건 잘 지켜가면서 풀었다. 하나의 turn 마다 1번 말부터 순서대로 움직인다. 한 칸에 여러 말이 쌓여 있을 수 있고 이동하려는 말 위에 다른 말이 존재한다면 같이 움직인다. 한 칸에 말이 4마리 이상 쌓일 경우 게임이 종료된다. 이동하려는 칸이 흰색인 경우 이동하려는 말의 위에 있는 말부터 쌓이기 시작한다. 이동하려는 칸이 빨간색일 경우 이동하려는 말부터 쌓이..
[문제] www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net [풀이] 시뮬레이션 문제로 조건별로 함수 구현해서 풀었다. 먼저 원판의 크기와 상태가 입력으로 주어지고 x,d,k가 입력으로 주어진다. x의 배수인 원판을 d ( 0이면 시계, 1이면 반시계) 방향으로 k만큼 회전한다. 1. 회전 2. 인접하면서 같은 수 0으로 바꿔주기 3. 인접하면서 같은 수가 하나도 없다면 원판 전체 평균 구해서 평균 보다 작은 값은 +1, 큰 값은 -1 따라서 r..
[문제] 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 함수를 사용해 이미 존재하는 친구인지 아닌지를 확인한다. 존재..