본문 바로가기

Algorithm283

[BOJ]4485번: 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 BFS 등 다양하게 풀 수 있지만 최단 경로를 물어봤으니 다익스트라로 해결하였습니다. (y,x)좌표 하나를 노드로 보게 되면 결국 구해야 하는 건 (0,0) 노드에서 (N-1,N-1) 노드까지의 거리입니다. 이 길이를 갱신해 나가는 방법은 자신와 인접한 4방향을 살펴보며 다익스트라 원리를 적용하면 됩니다. 오른쪽, 아래쪽으로만 가라는 제한조건이 없기 때문에 4방향을 다 훑으면서 최소를 찾아야 합니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ4485.java 2020. 9. 18.
[448]Find All Numbers Disappeared in an Array leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ 다음 출처를 참고하여 해결하였습니다. ergate.tistory.com/entry/LeetCode-448-Find-All-Numbers-Disappeared-in-an-Array 중요한 성질 두 가지를 기억하면 됩니다. N: 배열의 길이 1. 배열 내의 값이 [0,N-1] 또는 [1,N] 범위 내로 주어진다면 이를 인덱스로 활용할 가능성이 높습니다. 2. 중복유무와 관계없이 한 번이라도 등장한 값과 등장하지 않은 값의 차이는 인덱스상에 표시할 수 있습니다. 위 1, 2번 성질을 활용하여 한 번이라도 등장한 숫자는 number는 arr[number-1] 숫자를 음수로 바꿔줍니다. 중복 방문하지.. 2020. 9. 18.
[169]Majority Element leetcode.com/problems/majority-element/ 숫자가 나오는 갯수를 HashMap으로 관리한 후 절반이상 등장한 숫자를 리턴해주면 됩니다. HashMap map = new HashMap(); public int majorityElement(int[] nums) { for (int i = 0; i (nu.. 2020. 9. 18.
[136]SingleNumber leetcode.com/problems/single-number/ 두 가지 이유로 XOR을 통해 해결할 수 있습니다. 1. XOR은 결합법칙과, 교환법칙이 성립합니다. 2. 자기 자신과의 XOR 결과는 0 입니다. 10^10 = 0, A^A = 0 주어진 리스트의 1개를 제외하고는 모두 2개라는 성질을 이용하면 ABCDEDCBA 위 예시 숫자를 교환법칙을 사용해서 두 쌍씩 괄호로 묶어줍니다. (AA)(BB)(CC)(DD)E 여기에 XOR을 하게 되면 결국 0 ^ E 만 남게 되어 하나짜리 E만 남는 형태입니다. public int singleNumber(int[] nums) { int xorResult = 0; for (int i = 0; i < nums.length; ++i) { xorResult = .. 2020. 9. 18.

티스토리툴바