본문 바로가기

algorithm62

[Codility] CountNonDivisible 풀이 정리 (Java) source 는 Github 에 있습니다. 문제 문제 풀이 첫번째 풀이 문제 풀이의 concept 을 array element 끼리 나눌 수 없는지 확인하도록 했습니다. int[] A = new int[] {3,1,2,3,6}; 라면 3/1, 3/2, ... 이런식으로 concept 을 잡았습니다. array element 끼리 나누면서 발생하는 중복 계산은 cache 로 저장해서 중복 계산을 피했습니다. 시간복잡도는 O(n제곱) 이였고, 실행해본 결과 정확도 100%, performance 0% 두번째 풀이 문제 풀이의 concept 은 다음과 같습니다. array 에서 발생하는 숫자 빈도수를 계산해서 메모리에 저장합니다. array 를 순회하면서 1부터 element 까지 약분하도록 했습니다. 이 때.. 2022. 6. 9.
[leetcode] Number of Islands 정리 source 는 Github 에 있습니다. 문제 (Number of Islands) 문제 풀이 연결된 섬들은 1개로 count 합니다. for 문을 2번 돌려서 순회를 하면 연결된 섬에 대해서 찾을 수 없습니다. 전체 grid 를 순회하면서 방문한 곳은 순회하지 않도록 구현해서 처리했습니다. 순회할 때, DFS 를 써서 연결된 것들을 순회하게 했습니다. 순회할 때는 상하좌우로 순회하게 했습니다. source public int numIslands(char[][] grid) { int m = grid.length; int n = grid[0].length; visited = new boolean[m][n]; int count = 0; for (int i = 0 ; i < m ; i++) { for (int.. 2022. 1. 28.
더하기, 곱하기 시간복잡도 계산 더하기, 곱하기 시간복잡도 계산 더하기 더하기 시간복잡도 O(n) 2개의 이진수를 그냥 더해주면 되기에 for 문 한 번 돌리면 됨. 곱하기 시간복잡도 O(n제곱) 2개의 수를 곱한다 가정하면, 이진수로 변환하고 일렬로 나열한 후, 밑에자리에서부터 곱하기 시작. 밑에 자리에서부터 곱하게되면 n만큼의 이진수가 최대 n-1 만큼 나오게 되며, 그렇기에 시간복잡도 O(n제곱) 물론 알고리즘 마다 시간복잡도가 다름. 자바에서 곱하기 알고리즘을 어떤걸 사용하는가? Reference https://peng-hi.tistory.com/2 https://stackoverflow.com/questions/32998207/what-is-asymptotic-complexity-of-integers-multiplication.. 2020. 12. 10.
하노이탑 문제 풀기 하노이탑 문제 풀기 import lombok.extern.slf4j.Slf4j; @Slf4j public class Hanoi { public static void main(String[] args) { int count = hanoi(3, 1, 2, 3, 0); log.info("{}", count); count = hanoi(4, 1, 2, 3, 0); log.info("{}", count); } /** * 하노이탑 원리를 이해해야 함. * 1. n-1 를 두번째 기둥으로 옮기고. * 2. 첫번째 기둥에서 마지막 원판을 세번째 기둥으로 옮긴다. * 3. 두번째 기둥에 있는 n-1 원판을 세번째 기둥으로 옮긴다. * * 위 내용을 보면 n 번쨰 기둥을 옮기는건 n-1 번째 기둥을 옮기는 것을 풀어야 풀.. 2020. 11. 5.

티스토리툴바