코딩테스트 4

Longest Increasing Subsequence : 문제 번호 300 (C#)

https://leetcode.com/problems/longest-increasing-subsequence/ Given an integer array nums, return the length of the longest strictly increasing  subsequence. 배열에 존재하는 가장 긴 오름차순의 길이(문자가 연속하지 않아도 좋다)를 구하는 문제다예시로 제공한 int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 }; 에서는2, 3, 7, 101 순으로 4개가 가장 길다 이런식으로 구한다 가장 먼저 생각난 방법은맨 앞인 10에서 시작하여1바퀴 돌면서10보다 큰 것들의 개수를 세서 저장하고그 다음인 9에서 이걸 반복 이런식으로 2중 for문에서 선택정렬하듯이 풀면 ..

Flood Fill : 문제 번호 733 (C#)

https://leetcode.com/problems/flood-fill/ "Flood Fill" 문제는 주어진 2D 이미지에서 특정 위치 (sr, sc)를 시작으로 상, 하, 좌, 우로 연결된 같은 색상의 픽셀을 새로운 색상으로 바꾸는 문제입니다. 여기서 중요한 점은 변경하려는 픽셀이 원래 색상과 같아야 한다는 것입니다.  가운데 1과 수평, 수직으로 인접한 4개 중에 시작색상이 같은 것들은 가운데 숫자를 바꾼 뒤에도 색상이(숫자가) 같아야 하며, 더이상 변화가 없을때까지 반복실행한다 위의 예시로 보면, 가운데 1이니까 왼쪽 아마 2차원 배열 또는 1차원 배열로 생각해야 할 것 같은데arr[0][0] 부터 arr[2][2] 까지 있다고 하면 arr[1][1]을 최상위 부모로 한다arr[1][0]과 ar..

Day6. 배열과 컬렉션

1. 가장 큰 수찾기https://school.programmers.co.kr/learn/courses/30/lessons/120899 public int[] solution(int[] array) { int max = int.MinValue; int idx = 0; for (int i = 0; i 이걸 한줄로 푸는 풀이가 있어서 가져와봤다 int[] answer = new int[2] { array.Max(), Array.IndexOf(array, array.Max()) };Array 메서드인 Max(), IndexOf() 사용한다  2. 배열의 유사도https://school.programmers.co.kr/learn..

Largest Rectangle in Histogram : 문제 번호 84 (C#)

https://leetcode.com/problems/largest-rectangle-in-histogram/ 가장 큰 히스토그램 사각형" 문제는 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 찾는 문제입니다. 여기서 각각의 바(bar)는 연속된 바로 구성된 직사각형을 만들 수 있으며, 이 직사각형의 높이는 해당 바의 높이이고, 너비는 해당 바를 포함한 연속된 바의 수입니다.   직사각형의 넓이를 구하려면 밑변과 높이를 알아야하는데밑변 구하려면 순회하면서 해당 인덱스를 저장해야한다그런데 지역변수를 사용하려면 지역변수가 몇개 필요한지 알 수 없어서 그때마다 선언할 수도 없다만약 스택에 인덱스를 저장한다면인덱스의 차이를 이용해서 밑변을 구할 수 있고, arr[인덱스]를 이용하여 높이를 바로 가져올 ..