IT
-
1 Week ] Union findIT/알고리즘 공부( Coursera ) 2021. 1. 28. 21:28
코세라 수업을 듣고 내가 정리한 내용이다. Union find 알고리즘에 대해서 공부한 내용이다. 목차는 아래와 같이 5개이다. 1. dynamic connectivity 2. quick find 3. quick union 4. improvements #5. applications # Union find 를 활용한 사례 1. dynamic connectivity 먼저 주어지는 N은 노드의 개수로 총 노드의 개수가 주어지고 이 노드들의 연결 정보가 입력값으로 주어진다. 이를 연결해주는 Union이라는 함수와 연결이 되어있는지 검사하는 find,connected 라는 함수를 만들어준다. 대략적인 클래스 모양은 아래와 같다. public class UF // Union Find UF( int n ) // n개..
-
2021-01-27] Concatenation of Consecutive Binary NumbersIT/자기계발 ( Leetcode ) 2021. 1. 27. 21:55
오늘의 문제: leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3618/ 어제는 문제가 너무 어려웠고, 시간도 부족해서.. 결국 하루를 빼먹게 되었다. 하지만, coursera에서 algorithm 수업을 들으며, 해당 내용도 블로그에 적어볼 예정이라, 위안을 삼아보며 문제를 풀어보자. 문제예시를 보며 문제를 이해해보자. 예시에서 처럼 주어지는 n에 대해서 1~n 까지 2진수로 표현하여 나열한 2진수를 10진수로 변환하는 문제이다. 예시 2번을 보면, n=3이고, 1~3까지의 숫자 1,2,3은 각각 2진수로 '1','10','11' 이며, 이를 나열한 '11011..
-
2020-01-25] Check If All 1's Are at Least Length K Places AwayIT/자기계발 ( Leetcode ) 2021. 1. 26. 00:07
오늘의 문제: leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3616/ 이번 문제는 Easy 문제이다. 문제 예시를 보며 간단히 이해해보자. 주어지는 0,1로 이뤄진 1차원 배열에서 k 값 만큼 모든 1과 1사이가 떨어져 있는지 검사하는 문제이다. 예시 1번은 k가 2이고 각 1 사이끼리의 떨어진 index 거리가 3,2 이기 때문에 True 예시 2번은 k가 2이고 각 1 사이끼리의 떨어진 index 거리가 2,1 이기 때문에 False 간단하게, 1차원 배열의 for문을 돌면서, 값이 1인 index를 저장하여, 이전 저장한 index까지의 거리와 k를 비교..
-
2021-01-24] Merge k Sorted ListsIT/자기계발 ( Leetcode ) 2021. 1. 24. 20:03
오늘의 문제: leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3615/ 주어지는 2차원 배열에 값들을 하나의 정렬된 List 값으로 전달하는 문제이다. 예시를 보면 아래와 같다. 예시 1번처럼 값이 주어졌을때, 정렬된 List로 merge하여 하나의 List로 반환해준다. 예시 2,3번은 주어지는 값이 없을때에 대한 예외처리 를 보여주는 구간이다. 문제의 답을 도출하기 위해, 모든 데이터의 값을 한 List에 받은 후, sort 함수를 써서 정렬하면 값을 도출할 수 있다. 하지만, 형식이 List가 아닌 ListNode로, 모두 생성해주며 만들어줘야한다. 문제에..
-
2021-01-23] Sort the Matrix DiagonallyIT/자기계발 ( Leetcode ) 2021. 1. 23. 21:02
오늘의 문제: leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3614/ 2차원으로 주어지는 배열에서 diagonal line을 크기 순으로 정렬한 새로운 2차원 배열을 반환하는 문제이다. 영어로 역시 보다보니 문제 이해가 어려웠지만, 예시를 보면 한결 편해진다. 입력값으로 주어지는 mat이라는 2차원 배열의 diagonal line 표현해주는 그림은 before이고, 그 diagnonal line에 대해 순서를 크기순으로 정렬하여 새로운 2차원 배열을 만들면 after가 된다. 우선 그럼 after로 만들기 위한 2차원 배열을 위한 구한다. m=len(mat) ..
-
2021-01-22] Determine if Two Strings Are CloseIT/자기계발 ( Leetcode ) 2021. 1. 22. 21:54
오늘의 문제: leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3613/ 오늘은 금요일!! 불금이지만 문제풀이로 오늘을 불태운다면 발전하는 나를 볼수있을것이다.. 이번 문제에서 주어진 Operation 2개에 대해서 이야기를 하자. 입력값으로 주어지는 2개의 문자열에서 하나의 문자열을 Operation 1,2를 사용하여 동일하게 만들 수 있으면 두 문자열은 가깝다고 생각하고 가까우면 True, 문자열이 동일해지지 않으면 False 를 반환하는 문제이다. Operation 1: 문자열에서 두 문자를 위치 변경이 가능하다. ( b -> e / e -> b ) Oper..
-
2021-01-21] Find the Most Competitive SubsequenceIT/자기계발 ( Leetcode ) 2021. 1. 22. 01:16
오늘의 문제: leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3611/ Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 문제의 난이도는 Medium인데 나에겐 왤케 어려운지.. 문제를 풀려고만 하지말고, 알고리..
-
2021-01-20] Valid ParenthesesIT/자기계발 ( Leetcode ) 2021. 1. 20. 23:27
오늘의 문제: leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3610/ 문제 예시를 보며 설명해보자. 입력값으로 주어지는 문자열은 소, 중, 대 괄호만으로로 이뤄진다. 주어진 값에 대해서 괄호가 잘 닫혔는지, 이상은 없는지 확인하는 문제이다. 각 괄호들로 알맞게 닫혀져있는지 확인하여 참 ,거짓을 판별하자. 먼저, 실패조건을 생각해본다. 1) 주어진 문자열의 길이는 무조건 짝수여야한다. ( 쌍으로 열고 닫히기 때문에 ) if len(s)%2==1: # 주어진 s의 길이가 홀수면 False return False 2) 닫히는 괄호가 먼저 나오면 무조건 실패 ( 예시..