5주차 과제2 - Flood Fill
출제자의 의도
배열과 시작점이 주어졌을 때, 시작점과 시작점을 중심으로 같은 값을 가진 element들을 모두 찾아서 값을 바꿔주는 알고리즘을 작성하라.
- 제한사항
가변 배열 [m][n]의 크기 제한 : 1<=m / n<=50
값 x의 크기 : 0 <= x <= 2^16
시작점 [sr][sc] : 0 <= sr < m / 0 <= sc < n
내가 생각한 풀이
- 시작 지점부터 차례대로 상하좌우 왔다갔다 하면서 같은 값인 지점을 찾는 함수를 만든다.
- 이걸로 재귀함수를 돌린다.
- 탐색이 끝나면 나올 때 그 지점의 값을 바꿔주는 작업을 한다.
완성!
큰 틀은 이건데, 문제를 잘못봐서 버전을 두개 만들어봤다. 큰 틀은 동일하니 그냥 배열의 차이점만 보면서 넘어가면 될 듯 하다.
2차원 배열
탐색 알고리즘
static int[,] Find(int[,] grid, int x, int y, bool[,] visited, int change)
{
if (y >= 1) //그냥 상하좌우 순서로 이동할 수 있는지 부터 판별
if (grid[x, y - 1] == grid[x, y]) //그 후 이동할 곳의 값이 지금 있는 곳과 같고
if (visited[x, y - 1] == false) //내가 들른 적이 없다면
{
visited[x, y - 1] = true; //들른 곳으로 체크하고
Find(grid, x, y - 1, visited, change); //거기서 더 들를 곳이 있는지 확인
}
if (y < grid.GetLength(1) - 1)
if (grid[x, y + 1] == grid[x, y])
if (visited[x, y + 1] == false)
{
visited[x, y + 1] = true;
Find(grid, x, y + 1, visited, change);
}
if (x < grid.GetLength(0) - 1)
if (grid[x + 1, y] == grid[x, y])
if (visited[x + 1, y] == false)
{
visited[x + 1, y] = true;
Find(grid, x + 1, y, visited, change);
}
if (x >= 1)
if (grid[x - 1, y] == grid[x, y])
if (visited[x - 1, y] == false)
{
visited[x - 1, y] = true;
Find(grid, x - 1, y, visited, change);
}
grid[x, y] = change; //들리는게 끝나면 맨 끝 방문한 곳부터 차례차례 숫자를 바꾸면서 나옴.
return grid; //바뀐 배열 반환
}사실 알고리즘이랄 것도 없는 게, 그냥 함수 안에서 4방향(갈 수 있는 곳만)으로 한번씩 다 찔러본다. 그러다 걸리면 거기서도 찔러본다.
이 내용과 관련해서 5주차 강의 중 그래프 알고리즘에 비슷한 게 있다. 참고하면 좋다.
Main()
static void Main(string[] args)
{
Console.WriteLine("사용하실 배열의 행 크기를 입력하세요. 50이하");
string inputx = Console.ReadLine();
int row = int.Parse(inputx);
Console.WriteLine("사용하실 배열의 열 크기를 입력하세요. 50이하");
string inputy = Console.ReadLine();
int Col = int.Parse(inputy);
int[,] grid = new int[row, Col];
bool[,] visited = new bool[row, Col];
Random rand = new Random();
for (int i = 0; i < row; i++)
{
for (int j = 0; j < Col; j++)
{
grid[i, j] = rand.Next(0, 2); //원래는 2^16까진데 눈에 확 보이게 하려고 바꿈
Console.Write($"[{grid[i, j]}]");
}
Console.WriteLine();
}
Console.WriteLine("시작 지점을 입력해주세요. 행 : 0~{0}, 열 :0~{1}사이입니다.", row, Col);
string start = Console.ReadLine();
string[] starts = start.Split(",");
int startx = int.Parse(starts[0]);
int starty = int.Parse(starts[1]);
visited[startx, starty] = true;
Console.WriteLine("무슨 숫자로 바꾸고 싶은 지 입력하세요.");
string Changeinput = Console.ReadLine();
int change = int.Parse(Changeinput);
Find(grid, startx, starty, visited, change);
for (int i = 0; i < row; i++) //완성된 배열 출력
{
for (int j = 0; j < Col; j++)
{
Console.Write($"[{grid[i, j]}]");
}
Console.WriteLine();
}
}여기서도 단순히 배열의 크기를 받아오고, 값을 랜덤으로 입력한 후
함수를 실행시키고 값을 받아 출력하는 것 밖에 없다.
반전
다 만들고 TIL 작성하려고 보니까 문제 나오는 사이트에서는 2차원 배열이 아니라
가변배열을 사용하더라.
위의 방식으로 작성하면 배열이 모양이 사각형으로만 나온다는 제약이 있다.
그래서 가변배열을 사용해 작성한 알고리즘을 풀어본다.
가변 배열
가변배열이 뭔지 모른다면 가변배열 여기를 보고 오도록 하자. 필자도 여기서 보고 작성했다.
이게 코드로 행렬 작성하다보면 이게 행 저게 열 저게 행 이게 열 이리저리 헷갈린다,
끄적이다보면 해결되긴 하는데 착착 할 수 있도록 하자.
탐색 알고리즘
static int[][] Find(int[][] arr, int Col, int Row, bool[][] visited, int change) //조건이 다채로움.
{
if (Row >= 1 && Col < arr[Row - 1].Length) //탐색 가능한 범위 지정
if (arr[Row - 1].Length >= Col) //위쪽으로 움직임
if (arr[Row - 1][Col] == arr[Row][Col]) //원래있던 위치랑 같으면?
if (visited[Row - 1][Col] == false) //방문한 적이 없으면?
{
visited[Row - 1][Col] = true; //방문했고
Find(arr, Col, Row - 1, visited, change); //거기서 또 찾아라
}
if (Row < arr.Length - 1 && Col < arr[Row + 1].Length)
if (arr[Row + 1][Col] == arr[Row][Col])
if (visited[Row + 1][Col] == false)
{
visited[Row + 1][Col] = true;
Find(arr, Col, Row + 1, visited, change);
}
if (Col < arr[Row].Length - 1)
if (arr[Row][Col + 1] == arr[Row][Col])
if (visited[Row][Col + 1] == false)
{
visited[Row][Col + 1] = true;
Find(arr, Col + 1, Row, visited, change);
}
if (Col >= 1)
if (arr[Row][Col - 1] == arr[Row][Col])
if (visited[Row][Col - 1] == false)
{
visited[Row][Col - 1] = true;
Find(arr, Col - 1, Row, visited, change);
}
arr[Row][Col] = change; //들리는게 끝나면 맨 끝 방문한 곳부터 차례차례 숫자를 바꾸면서 나옴.
return arr; //바뀐 배열 반환
}위에꺼랑 행 열 위치가 바뀐 것처럼 보이지만, 작성자의 실수다.
앞으로는 안헷갈리게 적어야 겠다.
상하 이동이 행! , 좌우가 열! 기억하자
Main()
static void Main(string[] args)
{
//Console.WriteLine("사용하실 배열의 총 크기를 입력하세요. 50이하");
//string inputx = Console.ReadLine();
//int row = int.Parse(inputx);
Random rand = new Random();
int row = rand.Next(3, 50); //임의의 열 크기 받기
int[][] arr = new int[row][];
bool[][] visited = new bool[row][];
int Col = 0;
for (int i = 0; i < row; i++) //임의의 행 크기 받아서 임의의 값 작성
{
//Console.WriteLine("사용하실 {0}번째 배열의 열 크기를 입력하세요. 50이하", i + 1);
//string inputy = Console.ReadLine();
//Col = int.Parse(inputy);
Col = rand.Next(1, 100);
int[] temparr = new int[Col];
bool[] tempbool = new bool[Col];
for (int j = 0; j < Col; j++)
{
temparr[j] = rand.Next(0, 2);
tempbool[j] = false;
Console.Write(temparr[j]);
}
Console.Write($" | {i}번째 행의 크기 : {Col} ");
Console.WriteLine();
arr[i] = temparr;//원래는 2^16까진데 눈에 확 보이게 하려고 바꿈
visited[i] = tempbool; //숫자 세팅하면서 다 false로 채워주기
}
Console.WriteLine("시작 지점을 입력해주세요. ");
string start = Console.ReadLine();
string[] starts = start.Split(",");
int startRow = int.Parse(starts[0]); ;
int startCol = int.Parse(starts[1]);
visited[startRow][startCol] = true; //시작지점만 true로
Console.WriteLine("무슨 숫자로 바꾸고 싶은 지 입력하세요.");
string Changeinput = Console.ReadLine();
int change = int.Parse(Changeinput);
Console.WriteLine();
//검수용
for (int i = 0; i < row; i++) //완성된 배열 출력
{
foreach (bool j in visited[i])
{
Console.Write($"{j} ");
}
Console.WriteLine();
}
Console.WriteLine();
for (int i = 0; i < row; i++) //완성된 배열 출력
{
foreach (int j in arr[i])
{
Console.Write($"{j} ");
}
Console.WriteLine();
}
Console.WriteLine();
Find(arr, startCol, startRow, visited, change);
//결과 출력
for (int i = 0; i < row; i++)
{
foreach (bool j in visited[i])
{
Console.Write($"{j} ");
}
Console.WriteLine();
}
Console.WriteLine();
for (int i = 0; i < row; i++)
{
foreach (int j in arr[i])
{
Console.Write($"{j} ");
}
Console.WriteLine();
}
}for문이 많아 보이는 건 콘솔에 출력하기 위한 장치로, 여기도 그냥 함수만 돌리고 출력하면된다.
정리
재귀함수를 돌리는 것으로 반복문을 안 써도 반복작업을 실행 할 수 있다.
재귀함수를 구성할 때는 조건을 촘촘히 잘 짤 것!
삐끗하면 무한의 굴레에서 빠져나올 수 없다.
5주차 과제3 - Longest_Increasing_Subsequence
출제자의 의도
int 배열이 주어졌을 때, 연속적으로 증가하는 가장 긴 수열의 크기를 구하라.
그냥 보면 무슨 말인가 싶을수도 있다. 최장 증가 부분 수열을 참고하면 좋다.
- 제한사항
배열의 길이 : 1<= nums.Length <= 2500
숫자의 크기 : -10^4 <= nums[i] <= 10^4
내가 생각한 풀이
초기버전
내가 생각한 건 for문을 두개 돌려서 임의의 수와 그 다음부터의 값들을 비교하고, 동시에 i+1의 값이 i+2의 값보다 크면 Value++ 해주고 반복이 끝날 때 Value를 최고 값으로 반환하는 방법을 생각해봤다.
근데 이 방법은 어느정도 정렬이 되어 있을 땐 문제가 없지만, 배열 중 가장 큰 숫자가 뒤에 위치해 있을 때 오류가 발생했었다.
참고버전
위의 나무위키를 참고해서 다른 버전을 제작해봤다.
이 버전은 배열의 맨 앞에 0을 붙여서 일정한 규칙을 만들어준다.
그리고 주어진 배열과 같은 크기의 0으로 채워진 배열(여기서는 Length)을 만든다.
nums[i] 라는 i번째 원소가 있으면, 0부터 그 직전까지의 수와 비교를 해서, nums[i]가
그 수들의 뒤에 붙을 수 있다면 그 수의 위치에 해당하는 length를 불러와서 +1 해서 반환한다.
+1을 하는 이유는, length가 그 수까지의 LIS이기 때문이다.
나도 뭐라 설명하는지 모르겠다.
초기버전
LIS 알고리즘
static int Findarray(int[] arr)
{
int temp = 1; //길이라서 최솟값 1
int beststreak = 0; //실제로 반환되는 최장 수열
for (int i = 0; i < arr.Length; i++)
{
for (int j = i + 1; j < arr.Length; j++) //j는 i의 다음 수부터
{
if (j == arr.Length - 1) //어레이 인덱스 오류가 나기때문에 분리해줬음.
{
if (arr[i] < arr[j])
temp++;
}
else if (j < arr.Length - 1)
if (arr[i] < arr[j] && arr[j] > arr[j + 1]) //위에 말했던 오류나는 부분
temp++;
}
if (temp > beststreak)
beststreak = temp;
temp = 1;
}
return beststreak;
}식 자체는 for문 두개돌리는 간단한 식으로 구성해봤는데, 아마 식을 바꾸면 이걸로도 가능하지 않을까
Main()
static void Main(string[] args)
{
Console.WriteLine("배열의 크기를 입력해주세요."); //배열 크기 받고
string array = Console.ReadLine();
int[] nums = new int[int.Parse(array)]; //배열 만들어준 다음
Random rand = new Random();
Console.WriteLine("입력된 숫자는 ");
for (int i = 0; i < nums.Length; i++) //랜덤으로 조건 범위 내의 숫자 생성
{
nums[i] = rand.Next(-((int)Math.Pow(10, 4)), (int)Math.Pow(10, 4));
Console.Write($"{nums[i]} ");
}
Console.WriteLine();
Console.WriteLine($"최장 증가 수열의 길이는 {Findarray(nums)}입니다.");
}이거도 배열의 크기를 맘대로 바꿔보려고 작성해놓은 Main()인데 사실 중요하진 않다.
참고버전
LIS 알고리즘
static int Findarray(int[] arr) //가장 긴 연속의 길이를 반환
{
int temp = 0; //실제 반환값
int temp2 = 0; //for문에 사용됨
int[] length = new int[arr.Length]; //새로운 배열 생성 (숫자별로 연속의 길이를 정리해놓기위해)
for (int i = 0; i < length.Length; i++) //배열들의 값은 0
{
length[i] = 0;
}
for (int i = 1; i < arr.Length; i++) //맨 앞의 0은 제외하고 하기때문에 1부터 시작
{
for (int j = 0; j < i; j++) // 여기는 맨앞의 0을 포함하고 계산해야 규칙이 생기기 때문에 0시작
{
if (arr[j] < arr[i]) //arr[i] -> 기준, arr[j]가 돌면서 조건을 만족했을 때
if (temp2 < length[j]) //현재 저장된 i번째 숫자가 뒤에 붙을 수 있는 수열의 길이 < 현재 수열의 길이
temp2 = length[j]; //수열의 길이 갱신
}
length[i] = temp2 + 1; //temp2에 한개를 더 붙이기 때문에 +1
temp2 = 0; //temp2 초기화
}
for (int i = 1; i < length.Length; i++)
{ //각 수열의 길이의 최대값을 구함
if (length[i - 1] < length[i])
temp = length[i];
}
return temp; //반환
}배열을 쓸 때는 항상 0부터 시작하는 걸 기억하자, 내가 자꾸 까먹는다.
Main()
static void Main(string[] args)
{
Console.WriteLine("배열의 크기를 입력해주세요."); //배열 크기 받고
string array = Console.ReadLine();
int[] nums = new int[int.Parse(array) + 1]; //배열 만들어준 다음
Random rand = new Random();
nums[0] = 0; //알고리즘 상 첫칸은 0
Console.WriteLine("입력된 숫자는 ");
for (int i = 1; i < nums.Length; i++) //랜덤으로 조건 범위 내의 숫자 생성
{
nums[i] = rand.Next(-((int)Math.Pow(10, 4)), (int)Math.Pow(10, 4));
Console.Write($"{nums[i]} ");
}
Console.WriteLine();
Console.WriteLine($"최장 증가 수열의 길이는 {Findarray(nums)}입니다.");
}초기 버전과 다른 점은, 새로운 규칙들을 위해 배열을 설정하는 부분이 좀 다르다.
정리(과제2도 포함)
우리가 일반적으로 숫자 셀 때 1부터 세는데, 코드 상에서는 0부터 세는 걸 항상 염두에 두고 진행하자. 이거때문에 오류가 계속 나는 부분도 있었는데, 정확하게는 내가 생각한 숫자와 실제 숫자가 1 차이가 나서 범위 설정에 오류가 나는 부분이였다.
일단은 잘 해치운 것 같고, 내일 WIL 작성하면서 한번 더 볼 예정이다.
그리고 F9로 브레이크포인트 잡아서 오류 풀어보는 게 이해가 쏙쏙되서 좋더라
오늘의 피드백
미니프로젝트 피드백 정리
피드백 항목과 나름대로의 생각을 정리해보자
함수안에 내용이 없는 Update()와 같은 함수는 지워주시는게 좋습니다.
코드의 가독성(?)을 해치기도 하고, 잘은 모르지만 일단 코드에 Update가 있으면 돌아가지 않을까? 그래서 지우라고 하시는 듯 하다.
게임 시작시 이전의 최단 시간을 표기하는 기능
- GameManager의 Update부분에 게임 시작시 이전의 최단 시간을 표기하는 기능을 switch문을 사용하셨는데 이렇게 되면 아무동작을 하지 않을 때도 계속해서 연산이 돌아가는 비효율적인 동작을 하게 됩니다.
해당 함수를 Start와 같이 게임이 시작할 때 1회성으로 호출하도록 구조를 짜는것이 바람직합니다.
내가 작성한 부분이 아니라서 정확하게는 기억이 안나지만, 아마도 Update안에서 switch문이 제약이 가벼워서 계속 돌아가고 있었나보다.
확실히 Text로 띄워주는 부분은 Start에서 한번 설정해주면 끝이라 신경써서 해야될 듯 하다.
Find() 관련
-GameObject.Find(오브젝트 이름)과 같은 코드는 성능 저하를 일으키는 함수로 다른 방법으로 구현하시는것을 권장드립니다.
이전에 작업할 때 Find 써서 찾아오는게 더 좋을 것 같아서 했었는데, 이게 하이어라키를 다 뒤지는 과정을 거치다보니 좋지 않은 듯하다. 꼭 필요한 경우가 아니라면, 다음과 같은 방법을 쓰자
1. 손으로 직접 할당하기
2. 임의로 변경해야 된다면, 그 오브젝트를 반환하고, 반환된 값을 할당해주는 방식의 스크립트로 작성하기
git 컨벤션
(출처 : 내일의 나는 오늘의 내가 만든다)
- git 컨벤션이란?
git에 커밋할 때 작성하는 내용들의 양식(?) 같은 거다. history를 볼 때 어떤 내용인지 한눈에 알기 쉽고, 어떤 목적을 위해 작성 되었는지 쉽게 알 수 있기때문에 얘기하신 듯?
나도 앞으로 올릴 때 이런 양식을 맞춰서 올리는 연습을 해야겠다.
Readme 파일
(출처 : chrome의 백엔드 연구소)
- Readme 파일?
README 파일은 주로 Github 프로필 혹은 Repository에 대한 설명을 나타내기 위해 작성한다. README는 쉽게 말하면 가이드라인, 안내문 정도로 생각할 수 있다. 그 이유는 README 파일에는 일반적으로 프로젝트에 대한 정보가 담겨 있어, 소프트웨어 배포시에 함께 포함되는데, 이러한 점이 마치 새 제품을 샀을 때 읽어보는 사용 설명서와 비슷하기 때문이다.
- README 파일의 필요성
① For Myself
자신이 코딩한 프로그램이라고 해서 언제까지나 코드의 모든 내용을 이해하고 있을 수는 없다.
시간이 흘러 자신의 프로그램을 다시 읽어보고 해석해야 할 일이 생길 경우, README 파일이 필요한 수고를 덜어줄 수 있다.
② For My Co-workers
함께 협업하는 동료들에게 지침서 역할로 유용하게 쓰일 수 있다.
③ For Users
서비스를 구현하여 오픈소스로 배포하는 경우, 자신의 프로그램을 이용하는 사람들이 쉽게 프로그램을 이해할 수 있게 된다.
- README 파일의 구성
README 파일을 작성하는 방법에 있어 정해진 양식은 하나도 없다. 어떤 구성요소를 포함할지 모르겠다면 아래의 내용을 고려해볼 수 있다.
프로젝트 구성
프로젝트 프로그램 설치방법
프로젝트 프로그램 사용법
저작권 및 사용권 정보
프로그래머 정보
버그 및 디버그
참고 및 출처
버전 및 업데이트 정보
FAQ
작성 방법에 관해서는 출처에 있으니 주차별 작성한 프로젝트에 Readme를 작성해보자!
깃에 프로젝트 올릴 시 주의사항
깃에 프로젝트를 올리실 땐 [Assets].[Packages],[ProjectSettings] 3개의 폴더를 올려주세요.
잡다한 거 많이 올리면 복잡하니까 그러지 말라는 뜻
앞으로 할거
- 개인 과제 해설 영상 보고 리팩토링
- WIL 작성 (1~5주차까지 과제 해설 보면서 내꺼랑 비교분석 리팩토링)
- Git에 올려놓은 것들 readme 작성해보기 (컨벤션은 앞으로 잘하기)
- 동기화 / 비동기화 공부하기
- Json 공부하기 (parse)
