개발자 김수진

[문제] 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..

[개념] 이진 탐색은 데이터가 정렬되어 있는 상태에서 특정 데이터를 찾는다. 배열의 시작, 중간, 끝 index를 조절해가며 탐색을 한다. 찾고자 하는 값인 x가 배열의 중간 값보다 작으면 중간을 기준으로 왼쪽에 있는 데이터 중에서만 찾고 x가 배열의 중간 값보다 클 경우 중간을 기준으로 오른쪽에 있는 데이터 중에서만 찾는다. 이와 같이 탐색 범위를 좁혀가면서 찾고자하는 값을 찾아낸다. 위의 그림은 이진 탐색의 예시로 정렬된 배열을 가지고 시작한다. 찾고자 하는 값인 13은 처음 mid인 7보다 크므로 low = mid +1이 되고 , mid = (low+high)/2 = 3 이 된다. arr[3]이 13이므로 true를 반환하면서 탐색을 종료한다. [코드] 아래 코드와 같이 low는 배열의 시작, hi..

- 선택 정렬 ( Selection Sort) [ 개념 ] 선택 정렬은 현재 자신의 index보다 뒤에 있는 index들 중에서 배열의 원소 값이 가장 작은 원소랑 자리를 서로 바꿔줍니다. 이러한 방식으로 배열의 처음부터 끝까지 진행하여 정렬을 할 수 있습니다. 아래 그림은 선택 정렬의 예시로 다시 한번 설명해드리겠습니다. 먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다. 첫번째 index부터 시작하여 자신의 값보다 작은 값들 중에서 가장 작은 값을 찾습니다. 해당 배열에서는 '13'보다 작은 값 중에서 제일 작은 '2'를 택하게 됩니다. 제일 작은 값을 찾은 뒤 서로 자리를 swap합니다. 다음 index로 넘어가 두번째 index를 기준으로 뒤에 있는 값들 중에서 가장 작은 값을 찾습니다. ..

[문제] 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를 구현하여 풀었다. 물고기들의 정보를 구조체에 저장..