1주차 1차 1 - LeetCode-Study-Team/solutions GitHub Wiki

1 Two Sum

문제 링크

문제 요약

Array 안 숫자들 중 2개의 합이 target 숫자와 같은 위치 출력하기. (단, 같은 위치 숫자 중복 사용 불가)

인풋 데이터

public static void main(String[] args) {
    int[] nums1 = {2, 7, 11, 15};
    int target1 = 9;

    int[] nums2 = {3,2,4};
    int target2 = 6;

    int[] nums3 = {3,3};
    int target3 = 6;

    System.out.println(Arrays.toString(twoSum(nums1, target1))); // 답: [0,1]
    System.out.println(Arrays.toString(twoSum(nums2, target2))); // 답: [1,2]
    System.out.println(Arrays.toString(twoSum(nums3, target3))); // 답: [0,1]
}

풀이 1 - Brute Force

  • 제가 푼 방식이랑 동일한 방법 (초보...)
  • 간단하지만, 오래 걸림
  • 배열의 각 값을 순회하며, 그값을 target에서 빼고 나온 수가 배열에 있는지 두번째 for에서 검색하는것. (target - x = y)
    • 있을 경우, x와 y 위치값을 담은 배열 리턴
public int[] twoSum1(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    // 답 없을때, null 리턴
    return null;
}
  • 시간 복잡도: O(n^2)
    • 배열을 2번 반복해서 순회하니
  • 공간 복잡도: O(1)
    • 여기서 필요한 공간은 입력 배열의 크기에 의존하지 않으므로 일정한 공간만 사용되기에 (이해x)

풀이 2 - Two-pass Hash Table

  • 런타임 속도 올리기 위한 방법은?
  • complement가 배열에 존재하는지 더 효율적인 방법 찾기
    • Hash Table 사용하기
  • 해시테이블 특징
    • 데이터 삽입은 느려도 (해시함수 계산거치므로), 검색 속도 빠름 (링크)
    • 여기서 사용시 검색 시간 O(n) -> O(1) 됨. (최악은 O(n) 동일) (링크)
  • 순서
    • 첫째 포문, nums 배열의 값을 해시테이블 key값으로 넣는다.
    • 둘째 포문, nums 배열 안에 값을 하나씩 돌며, target에서 빼서 그 complement(보수)를 해시테이블에서 찾는다.
  • 사용된 메소드
    • map.containsKey(x) = 키 x 있나 확인
    • map.get(x) = x키의 value 가져오기.
public int[] twoSum2(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
     // 답 없을때, null 리턴
    return null;
}
  • 시간 복잡도: O(n)
    • 이유: 배열을 두번 하므로 n+n인데, n으로 하는거 같음. 위키
  • 공간 복잡도: O(n)
    • 이유: 추가 공간은 n개의 요소를 저장하는 해시 테이블에 저장된 항목 수에 따라 다르다. (이해x)
    • 공간복잡도가 늘었지만 시간복잡도 줄였으므로 괜찮다.

풀이 3 - One-pass Hash Table

  • for 문을 한번만 쓰서 시간을 줄이자.
public int[] twoSum3(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i }; // 해시테이블 값에서는 배열의 위치값이 놓여있다. 
        }
        map.put(nums[i], i);
    }
     // 답 없을때, null 리턴
    return null;
}
  • 시간 복잡도 : O(n)
    • 이유: n개의 요소를 포함하는 목록을 한 번만 탐색하기에
  • 공간 복잡도 : O(n)
    • 이유: 필요한 추가 공간은 최대 n개의 요소를 저장하는 해시 테이블에 저장된 항목 수에 따라 다르기에

시간 비교

(단위: ms)

1차 2차 3차
풀이 1 271 324 513
풀이 2 89 156 168
풀이 3 37 69 83

팁

  • 공간 복잡도 보다 시간 복잡도를 더 중요하게 생각하는 이유는?
    • 메모리는 살 수 있어도, 시간은 살수 없기에...

371. Sum of Two Integers

문제링크

문제 요약

+, - 없이 두 수를 더하고 뺄수있게 만들기

인풋데이터

내가 생각해본것

  • +,- 쓰지 말자는 조건에 비트연산을 바로 떠올리긴 했다.
  • 2진수 10 + 01 은 11 이 된다. 그럼 OR 연산 하면 더해지나? 아니네... 11+01 하면 100 이네... 패턴을 찾아야해... 비트 연산을 모르니 일단 개념부터 다잡자.

개념

  • Bitwise Operators
  • 자바 첫번째 부호는 sign 나타냄.
    • 퀴즈: 1=?, 0=?
    • 퀴즈: 0....01 은 1이다. 그럼, 1....01은 -1 일까?
  • 컴퓨터 음수 표현 방식 3가지
    • 부호와 크기 표현
    • 1의 보수
      • 퀴즈: 1011 (-4) -> 이 2진수는 1의 보수로 표현된 음수이다. 몇일까요?
    • 2의 보수
      • 퀴즈: 0101 (5)를 -5로 바꾸면?
    • 자바 2의 보수 사용
  • 비트연산자 - TCP School
int a = 10; // 1010
int b = 6; // 0110

System.out.println("(~a): " + ~a); 
System.out.println("(a | b): " + (a | b));
System.out.println("(a ^ b): " + (a ^ b));  
System.out.println("(a & b): " + (a & b));
  • Bitwise Operator와 Logical Operator 차이는?
    • binary digits에서 작동하냐 또는 boolean expressions에서 작동하냐

시프트 연산 퀴즈

  • 0000 1000 (8) << 2
  • 1111 1000 (-8) >> 2
  • 0000 1000 (8) >>> 2
  • 1111 1000 (-8) >>> 2

풀이1 - 언어 독립적

  • 덧셈
  • Bitwise 문제 팁 : 일단 XOR 하기 (XOR 문제가 많다고함)
public int getSum1(int a, int b) {
    int x = Math.abs(a), y = Math.abs(b);
		
    if (x < y) return getSum(b, a);

    // abs(a) >= abs(b) --> 
    // a determines the sign
    int sign = a > 0 ? 1 : -1;

    if (a * b >= 0) {
        // sum of two positive integers x + y
        // where x > y
        while (y != 0) {
            int answer = x ^ y; 
            int carry = (x & y) << 1; 
            x = answer;
            y = carry;    
        }    
    } else {
        // difference of two positive integers x - y
        // where x > y
        while (y != 0) {
            int answer = x ^ y;
            int borrow = ((~x) & y) << 1;
            x = answer;
            y = borrow;    
        }    
    }
    return x * sign;
}

  • 시간 복잡도: O(1)

    • 이유: Integer이 32비트 이기에

  • 공간 복잡도: O(1)

    • 이유: 추가적인 자료구조를 사용하지 않기에

  • 모든 언어에서 돌아가는 로직으로 만들어서 코드가 길다

풀이 2 - 언어 종속적

  • 언어마다 음수를 다루는 방식이 다르다. (위 3가지 음수표현 방식 참고)
  • 자바는 음수 다를때 2의 보수 사용.
    • 비트 계산 복잡도 낮추기 때문
  • 순서 (11 + 10 경우)
    • 1라운드 answer = 01 carry = 100 a = 01 b =100
    • 2라운드 answer = 101 carry = 000 a = 101 b = 000
    • 3라운드 answer = 101 carry = 000 a = 101 b = 000
  • 풀이
    • 덧셈
      • XOR 이유 = 0,0 또는 1,1의 자리는 덧셈에서 0이 나오게된다. 두개가 다를 경우에만, 즉 하나라도 1일 경우 그 자리의 값은 1로 만들어준다.
      • & 후 << 1 이유 = 받아올림을 구해야 되는데 1,1의 경우에만 받아올림으로 만들어 짐으로 &연산이 필요하고, 올림은 한칸 앞으로 가기에 시프트연산 필요
    • 뺄셈
public static int getSum2(int a, int b) {
    while (b != 0) {
        int answer = a ^ b;
        int carry = (a & b) << 1;
        a = answer;
        b = carry;
    }

    return a;
}
  • 시간 복잡도: O(1)
  • 공간 복잡도: O(1)

206. Reverse Linked List (Linked List)

문제 링크

문제 요약

연결된 노드들의 순서를 뒤집기

인풋 데이터

ListNode node5 = new ListNode(5,node4);
ListNode node4 = new ListNode(4,node3);
ListNode node3 = new ListNode(3,node2);
ListNode node2 = new ListNode(2,node1);
ListNode node1 = new ListNode(1);

개념

  • 자료구조
    • Singly Linked List
      • 노드를 탐색하는 방향이 한쪽으로만 가능
    • Doubly Linked List
      • 양쪽 가능
  • 알고리즘
    • 풀이 1: 반복문 사용
    • 풀이 2: 재귀

나의 풀이 생각

리스트에 순차적으로 스택에 담고, 마지막 담은거 부터 꺼내서 순차적으로 잊는다. (아래 수두 코드 문법 맞는지 모름)

// pseudo code 
Stack<Node> nodeStack = new Stack<>();
nodeStack.add(nodeCopy(curr)); // head 넣기
while (curr != null) {
    nodeStack.push(nodeCopy(curr));
    curr = curr.next;
}

Node newHead = null;
for(int i = nodeStack.size(); i < 0 ; i--){
    Node node = nodeList.pop();
    if (newHead!=null) {
        newHead.next = node;
        newHead = newHead.next;
    } else {
        newHead = node;
    }
}

풀이 1 - iterative solution

  • 순서
    • 1라운드 curr: 2 -> 3 -> 4 -> 5 prev: 1 -> null
    • 2라운드 curr: 3 -> 4 -> 5 prev: 1 -> 2 -> null
    • 3라운드 curr: 4 -> 5 prev: 1 -> 2 -> 3 -> null
    • ...
  • nextTemp 필요 이유: curr가 다시
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}
  • 시간 복잡도: O(n)
  • 공간 복잡도: O(1)

풀이 2 - recursive solution

  • 순서

    • 1뎁스 1 2 3 4 5

    • 2뎁스 2 3 4 5

    • 3뎁스 3 4 5

    • 4뎁스 4 5

    • 5뎁스 5

    • Back

    • 4뎁스 5->4->null

    • 3뎁스 5->4->3->null

    • 2뎁스 5->4->3->2->null

    • 1뎁스 5->4->3->2->1->null

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}
  • 시간 복잡도: O(n)
  • 공간 복잡: O(n)
  • 재귀 특징 (출처)
    • 트리에서 많이 사용
    • 재귀 알고리즘은 이해하기 쉽다는 것과 쉽게 프로그램 할 수 있다는 장점이 있는 대신 수행 시간과 기억 공간의 사용에 있어서는 비효율적인 경우가 많다.
      • 이유: 함수를 호출하면 그 함수가 끝날때 어디로 복귀해야 한다는 복귀주소를 스택에 쌓게 되는데, 재귀함수는 재귀하는 횟수가 많아 질수록 이 쌓이는 복귀주소가 기하급수적으로 늘어나게 된다.

배운것 요약

  • 비트연산이 참 많네.
  • 자료구조 (해시테이블) 를 잘써야지, 런타임이 빨라지는구나.
  • 공간 복잡도 보다 시간 복잡도가 더 중요시 되는구나.
  • 언어마다 음수 다루는 방식이 다루구나.
  • 시간 복잡도는 아직도 모르겠다.
⚠️ **GitHub.com Fallback** ⚠️