20220811 TIL

Algorithm

8월 말부터 진행하는 학교 알고리즘 특강 전에 사전 지식도 쌓고 미리 머리도 풀어볼 겸 선배님께서 추천해주신 사이트에서 문제를 몇 개 풀어보았다.

영어사이트라 문제 해석에도 생각보다 오래 걸렸다.
나름 영어를 좀 하는 편이라 생각했는데 실전에서는 진짜 1도 도움이 안 되는걸 보고는 영어공부도 다시 좀 해야겠다는 생각이 들었다.

어쨌든 오늘 푼 6문제이다.

Merge Sorted Array

사실 이 문제의 알고리즘 자체는 그냥 말그대로 뺄거 빼고 정렬만하면 되었던지라 어려웠던건 아니지만 처음풀어보는 문제라 제출방식에서 조금 애먹었다. 특히 이 문제에서 다시 영어공부를 시작해야겠다는 생각이 들었다.

백준같이 IO 비교형식도 아니고 프로그래머스처럼 결과값 return 형식도 아니어서 선배님께 여쭤보니 함수의 인자로 주는 인자 중 하나인 변수의 inplace 방식이라고 해주셨다. 결국 해당함수가 끝나고 watch point?로 설정한 인자의 상태로 정답을 판별한다고 해주셨다. 그래서 처음에 내 코드는

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1 = nums1[m:]
        nums1 += nums2[0:n]
        nums1.sort()

이런 식이었는데 내가 nums1의 슬라이싱 배열을 nums1이라는 '새로운' 배열에 주는 순간 매개인자의 nums1과 내가 좌항에 선언한 nums1의 객체 id가 달라져 실제 매개인자의 nums1은 바뀌지 않았던 것이다.

즉, 첫 줄에서 새로운 nums1을 만들지않고 슬라이싱 혹은 삭제를 하고 진행을 해야해서

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        del nums1[m:]
        nums1 += nums2[0:n]
        nums1.sort()

그냥 del을 썼다.

Missing Number

요건 그냥 말 그대로 0부터 n까지 중에 중간에 없는 숫자를 찾는 것이다.

어차피 등비수열도 아니고 등차가 1이 아닌 등차수열도 아닌 말그대로 1씩 더해지는거라 이걸 sort를 하면 밑에 있는 그림처럼 없는 숫자말고는 그 인덱스값과 같아질거라 생각했다.

여기에선 2가 빠졌는데 그래서 인덱스가 2인 곳에 숫자 2가 아니라 3이 들어와있어서 그냥 정렬하고 인덱스랑 그 숫자가 다르면 그 숫자를 바로 리턴해버렸다.

근데 정렬된 배열의 끝까지 돌았는데 안 나온거면 제일 큰 값이 없다는 걸 의미하기 때문에 배열을 순회하는 for문 바깥에 그냥 배열의 길이(나올 수 있는 최댓값)를 리턴했다.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        for idx in range(len(nums)):
            if idx == nums[idx]:
                continue
            else:
                return idx
        
        return len(nums)

Valid Anagram

요건 bear과 bare처럼 같은 문자가 같은 횟수만큼있는지 판별을 하라는 문제 같았다.

랩실에 계시는 형께서는 알고리즘을 푸실 때 딕셔너리를 자주 쓰시고 은근 꿀이라 하셔서 이참에 써볼까했는데, 이건 금요일께 딕셔너리가 과연 좋은 방법일지 여쭤보고 연습할거라 일단은 꼼수를 찾아버렸다.

정말 쉬운데 리스트에서 정렬메소드인 sort가 있듯이 문자열에서 사전식으로 정렬해주는 sorted함수가 있었다.

그래서 같은 문자가 같은 횟수만큼 쓰인 두개의 문자열이라도 사전식으로 정렬을하면 같아질 수 밖에 없기때문에 사전식으로 정렬해서 비교를 해서 그 결과를 리턴했다.

문제풀때마다 너무 꼼수같아서 죄책감이 든다..

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if sorted(t) == sorted(s):
            return True
        else:
            return False

Contains Duplicate

이건 중복이 있는지만 리턴하라는 문제이다.
(즉 중복이 있어도 뭐가 몇 번 중복되는지 같은 것은 알 필요가 없는 것이다.)

이번엔 set를 이용해보았다.
set는 중복이 인자로 오는 리스트를 중복이 없는 set객체로 만들어주는 것이다.

예를들어 [1,2,3,4,4,5]를 set로 바꾸면 [1,2,3,4,5]가 된다.

여기서 꼼수가 발생한다.

중복이 있다면 없어진다는 것이고 이 말은 해당 객체가 가지고 있는 요소의 수가 줄어든다(달라진다)는 것이다.

그래서 원본 리스트와 원본 리스트를 세트로 만들었다가 다시 리스트로 만들어서 그 두개의 길이가 같다면 중복이 없었다는 것이고, 다르면 중복이 있었다는 말이 된다.

그래서 아래와 같이 코드를 작성했다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        compare_set = list(set(nums))
        if(len(compare_set) == len(nums)):
            return False
        else:
            return True

Majority Element

요건 배열의 크기의 반 이상을 차지하는 원소를 구하라는 것이다.
(문제는 이러한 원소가 무조건 있다고 가정하는 것 같다. 즉, [2,2,2,3,3,3,4,4,4] 같은 입력값은 없을 것이라는거다.)

example의 input을 보면 해당 배열이 정렬이 되어있지 않다.

그래서 또 꼼수를 찾았다. 일단 오름차순으로 배열을 해버린다.

그렇게 되면 같은 원소끼리 붙어있게 되는데, 밑에 있는 그림처럼 같은 원소끼리 선을 죽 그어서 하나의 막대라고 생각해보자.

근데 이렇게 만들어진 막대 중 전체 길이의 반보다 더 긴 길이를 가진 초록색막대(6)는 내가 어디에 끼워넣든 중간은 무조건 포함될 수 밖에 없는 구조이다.

즉, 가정처럼 배열의 반보다 더 많은 개수를 가진 요소가 있다면 이를 정렬해서 붙어보면 중간에 있는 값은 무조건 과반수를 차지하는 숫자가 될 수 밖에 없다는 것이다.

그래서 그냥 쉽게 말해서 정렬해서 중간 숫자를 뽑았다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[int(len(nums)/2)]

Intersection of Two Arrays II

이 문제를 이해하는데 생각보다 너무 많은 시간이 걸렸다.

처음에 예시만 보고서는 길이가 더 짧은 배열에서 나올 수 있는 문자열들의 집합이 더 긴 배열에서 찾는 것일줄 알았다.
ex) example2에서 [4,9,5]가 있는데 그래서 나는 긴 배열에서
[4,9],[9,4],[9,5],[5,9],[4,9,5],[4,5,9],[5,4,9],[5,9,4],[9,4,5],[9,5,4]가 있는지, 있으면 거기에서 가장 긴 배열을 찾는 것일줄 알고 머리를 싸매고 있었다.
(단순히 교집합이라고 하기에는 input에 같은 숫자를 두 개를 줄 이유도 없었고, example1의 expected가 [2]가 아니라 [2,2]라서 위에 있는 것처럼 순서까지 생각하는 줄 알았다.)

근데 이건 도저히 아닌 것 같아서 랩실 선배께 여쭤보니 교집합이긴 한데, 하나의 집합에 같은 원소가 존재할 수 없는 수학적 의미의 집합이 아니라 중복을 허용하는 집합에서의 교집합을 찾는 것이라고 설명을 해주셨다.(== 순서를 생각할 필요가 없었다.)

그래서 아무 배열의 원소를 for문으로 돌려서 그 원소가 다른 배열에 있는지 확인해보고 있으면 추가를 하는 코드를 짜보았다.

result=[]
for num in nums1:
            if num in nums2:
                result.append(num)
        return list(result)

근데 이런식으로 짜면 반례를 들면 이렇게 된다.
nums1=[1,2,2,1], nums2=[2] 라고 하면 expected는 [2]인데,
for문은 nums1을 돌고있고, 1번 2번 인덱스를 돌 때 어쨌든 '2'가 nums2에 있는건 사실이기 때문에
[2,2]라고 출력을 하게된다.
expected : [2]
output : [2,2]

그래서 이번엔 무조건 짧거나 같은 리스트를 찾아서 그 리스트로 for문을 돌리기로 해보았다.

result_list=[]
        if(len(nums1)>len(nums2)):
            longer_list=nums1
            shorter_list=nums2
        else:
            longer_list=nums2
            shorter_list=nums1
        
        for num in shorter_list:
            if num in longer_list:
                result_list.append(num)
        return list(result_list)

또 문제가 생겼다.
nums1=[1,1] nums2=[1,2]이다. expected : [1]
길이가 같을 때라 else문이 실행되어 nums1로 for문을 돌리는데 위에처럼 어쨌든 nums2에도 1이 있는건 사실이기 때문에 1이 두번 들어간다.

expected : [1]
output : [1,1]

근데 길이가 같을 때라는 처리를 하기엔 코드가 너무 더러워질 것 같아서 새로운 접근 방법을 찾아야했다.

그게 바로 위에서 나중에 시도해보려했던 딕셔너리다.

임의의 딕셔너리에 나온 숫자를 key값으로, 그 숫자가 나온 횟수를 value 값으로 둔다.
그리고 남은 리스트(nums2)를 for문으로 돌리다가 nums1의 key값에 있는 숫자가 나오면 결과에 추가하고 그 횟수를 하나깐다. 이렇게하면 일대일교환이 되기때문에 위에처럼 남은 값에 의해 또 결과가 추가되는 것을 막을 수가 있다.

	result = []
       
    count = { i : nums1.count(i) for i in nums1}

    for n in nums2:
        if n in count and count[n] != 0:
            result.append(n)        
            count[n] -= 1
        
    return result

이렇게 알고리즘 6문제를 풀어보았다.

오랜만에 푸는거라 잘 생각도 되지않았고 그마저 영어여서 이해하느라 조금은 힘들었지만 그래도 진짜 재미는 있었다.

Web Hacking

사실 이건 아직 성공한 게 없어서 태그로 넣어도 될 정도일지는 모르겠다.. 그러나 나름의 익스플로잇 가능성이기에 적어는 보았다.

저번에 클론코딩으로 정말 간단한 게시판 구현을 해보았고 해당 게시물들을 MongoDB에 넣어보았는데 <>같은 것은 HTML인코딩이 되어 들어가는 것을 확인해보았었다.

여기서 과연 HTML인코딩이 일어나는 것이 어딘지가 궁금해졌다.

서버에서 DB로 넘길 때 인코딩이 일어났다면 솔직히 이건 우회할 방법이 없다. 하지만 클라이언트에서 백엔드에 넘어오기전에 HTML인코딩이 된다면(클라이언트단에서 한다면) 시도해볼 수 있는 방법이 하나가 생각이 났다.

웹 취약점 분석툴 중에 BurpSuite라고 하는 툴이 있는데 이 툴은 어떠한 특정 포트에 프록시를 걸어놓고 여기에 통신이 올때마다 패킷을 중간에서 일시정지시켜 이를 보여주는 툴이다.

그래서 위에서 말했던 것처럼 클라이언트단에서 HTML 인코딩이 되었다면 패킷에 잡힐 때 이미 인코딩이 된 상태로 잡힐 것이다.

여기서 이 툴을 사용하는 이유가 나오는데 해당 요청에 있는 값들을 툴 사용자가 바꿀 수 있다는 것이다. 그래서 lt,gt,quot 등으로 인코딩로 된 상태로오면 이걸 내가 <>'같은 실제 문자로 바꾸어서 보낼 수 있다는 것이다. 이렇게 되면 DB에도 실제로 <>'가 저장될 것이고 이렇게 되면 피해자가 게시물을 클릭하면 그대로 뱉으면 XSS를 실행시킬 수도 있을 것 같다는 느낌이다.

하지만 아직 네트워크 지식이 없어서 프록시에 대한 정확한 개념도 없어서 어느 포트에 프록시를 걸고 Burpsuite에서 어느 포트를 관찰할지 모르겠다. 그래서 월화수동안은 Burpsuite사용법같은 것을 찾아봤는데 도저히 이해할 수가 없다. 그래서 내일은 그냥 네트워크에 대한 지식을 조금 찾아볼 것이다.

(사실 내가 만든 사이트인 로컬호스트가 아니라 아무 사이트잡고 하면 되긴한데 이는 범범행위라 안하고있다.)