알고리즘41 3차원 배열, 1차원 배열 같은 데이터라면 속도차이 이번에는 별도 알고리즘을 작성하는 것보다 개인 작업 중 잼있었던 부분을 공유해보고자 한다. 3차원 배열과 1차원 배열의 속도. 당연히 이 골자만 본다면 누가봐도 1차원 배열이 더 빠른걸 알 것이다. 실제 코딩을 하다보면 단순 1차적인 데이터 순회로 그치는 경우는 많지않음을 알 것이다. 그리고 이 3차원 배열이 비정형이고 양이 많을 경고 정확한 곳에 정확한 순서로 사용해야한다면 그렇게 3차원 배열과 1차원 배열의 총 양이 동일하다면 결과는 어떨까? 사실 지금의 조건으로도 1차원 배열이 더 빠르다 여기서 차이가 생기는건 { name : a age : 10 location : frorest child : { name : b age : 2 location : ocean element : fire child : .. 2023. 11. 6. 퀵정렬 설명과 함께 작성한 코드 수업 중 설명드렸던 퀵정렬 코드와 함께 설명을 추가한 버전 둘 중 편한 버전으로 보셔요 같은 내용입니다. package test; public class Loop { public static void main(String[] args) { int[] list = new int[10];// for(int i = 0 ; i < 10 ; i++ ) { list[i] = (int) (Math.random()*100)+1;//임의의수 10개를 고름 System.out.print(list[i]+" "); } sort(null, 0, list.length-1); System.out.println("\n==========================="); for(int i = 0 ; i < 10 ; i++ ) { S.. 2023. 6. 6. 페이징에 대한 이해 게시판 페이징에 관련해 수업을 한 적이 있다. 그때도 로직만 보고 시작했어서 설명하면서 정리한 자료가 내게는 없다. 기억을 더듬어 조금 더 생각을 정리하며 적어보고자 한다. 사실 텍스트만으로는 조금 전달이 복잡할 수 있을것 같지만 노력해보겠다. 처음 페이징로직을 접하면 아마 많이들 뭐지? 하는 생각을 하지 않을까 한다. 적어도 나는 그랬다. 페이징은 구조를 이해하고나면 간단함을 알 수 있다. 아주 동일하게 주기적으로 반복되는 로직이기 때문이다. ( 전체 규칙을 파악하고자 하는 것이 목표이므로, 글번호는 1번부터 시작하고, 중간에 삭제되거나 번호가 점프된 글은 없다고 가정한다. 이거야 어차피 정렬하면 되니까 굳이 지금 상황에 예외를 확인할 필요는 없다. ) 각 페이지의 마지막 게시글의 번호를 구하는 법을 .. 2023. 4. 24. 분수의 덧셈 ( 프로그래머스 문제, 코드 없음 ) 분수의 덧셈 프로그래머스에서 분수의 덧셈 문제를 풀었다. 다른 기본적인 구현은 하실 줄 아는 상황에서 두 분이 이 문제를 가져오셨다. 이 문제에서 요구되는 바는 다음과 같다. 1. 분수의 더하기, 빼기 등의 연산 2. 기약분수의 이해 얼추 예시들을 보고 유추할 수 있겠지만 해결하는 방법에 있어서는 분수에대한 정보는 필요했다. 우선, 분수는 전체의 일부, 동일한 부분의 수 로 정의된다. ( 무언가를 할때 정의는 굉장히 중요하다. 이는 내가 무엇을 해야할지 정확히 알 수 있기 때문이다. ) 분수는 또한 비율로 표시된다. 예를들면, 1/2 는 전체를 2등분 한 것중 1개만큼의 크기라는 뜻이된다. 그리고 2/4를 보면 전체를 4등분 한 것중 2개만큼의 크기로 실질적으로 1/2와 같은 크기가 된다. 이는 비율의 .. 2023. 4. 24. BOJ3052 - 서로 다른 나머지의 개수 간단한 문제이나, 은근 자주 쓰이는 생각의 방법을 담고 있는 문제라 기록할 가치가 있어 적는다. 단순하게 생각하면 나머지들을 구하고, 서로 다른 값이 있는 것을 비교하는 알고리즘을 짤 수 있다. 이 경우 이중 for문이 사용되고, 하나의 값마다 전체 리스트에 중복값이 있는지 비교하게 되므로 시간복잡도는 O(n^2) 이 된다. 여기서 이런 식으로 값을 받아올때 42로 나눈 나머지를 저장하고, 나머지의 종류를 세어주는 것으로 시간복잡도를 낮출 수 있다. 이러한 방법처럼 내가 원하는 데이터로 변환해서 다루는 것이 유용한 경우들이 있다. 2022. 1. 13. StringBuilder, StringBuffer 이는 String의 특성을 먼저 보는 것이 좋다. 다들 알다시피 String str1 = "가나다"; String str2 = "라마바"; str1 += str2; System.out.println(str1); 를 한다면, 출력되는 문자열은 가나다라마바 일 것이다. 이때 String타입은 불변성을 갖기 때문에, 원래 str1이 갖고있던 "가나다"에 문자열이 추가되는 것이 아니라, "가다나"는 GC ( garbage collector )의 처리대상이 되고, "가나다라마바"가 str1이 갖게되는 값이 된다. 즉 사용되는 메모리가 많아지는 것이다. 이로인해 StringBuilder와 StringBuffer가 사용되는데, StringBuilder sb = new StringBuilder("가나다"); Syste.. 2022. 1. 11. StringTokenizer StringTokenizer : 문자열을 구분자로 쪼개주는 클래스이다. 이렇게 쪼개진 문자열을 토큰(Token)이라 부른다. : 생성자 ( Constructor ) StringTokenizer(String str); : 문자열을 기본 구분자로 쪼개줌. 설정된 기본 구분자는 \t\n\r\t 와 같은 공백. StringTokenizer(String str, String delim); : 설정한 delim 문자열로 str을 쪼개줌. StringTokenizer(String str, String delim, boolean returnDelims); 설정한 delim으로 str을 쪼개는데, 구분자를 포함할지 정함. true일시 포함, false일시 미포함 : 메소드 ( method ) int countTokens.. 2022. 1. 11. EOF ( End Of File ) 과 while문 https://www.acmicpc.net/problem/10951 의 문제를 풀다가 알게 된 것 중 하나이다. 뒤이어 작성 할 StringTokenizer와 StringBuilder도 이번에 배웠지만 EOF.... ㅠㅠ 문제를 우선 간단히 보자. 보다시피 아주 간단한 문제다. 그리고 놀랍게도 정답비율 35%.. 입력을 보면 계산이 필요한 것들만 딱 입력이 된다. 끝을 알리는 방법도, 계산할 방법도 없다. 내 경우에는 이렇게 코드를 짰는데, 이를 이클립스상에서 출력하고 입력 예제를 넣는다면 NoSuchElement 예외가 발생한다. 이는 str에 "" 이 입력되어 st.nextToken()을 만나게되면 가리킬 대상이 없기 때문인데 BOJ에 제출하게되면 맞았습니다! 를 받아볼 수 있다. 이에 몰랐던 개념이.. 2022. 1. 11. BOJ2439 - 별찍기 처음 자바 공부할때 봤던 별찍기 문제다. 그 당시에는 어떻게 풀었는지 기억이 안나지만, 좀 고민을 했던 문제라 포스트를 남겨보려한다. 풀고나서 내 풀이방법보다 좋은 방법을 배우고자 검색해보니 이중 for문을 이용한 풀이만 보였다. ( 모든 글을 검색해본 것은 아니다. ) n이 작기때문에 이중for문으로도 충분하겠지만 개인적으로 시간복잡도를 낮추는 방법을 찾고자 하였고 혹시라도 나와같은 왕초보 분들에게 도움이 되지 않을까하여 공유한다. 첫 번째 for문으로 n길이만큼 공백의 문구를 만든다. 두 번째 for문에서 이전에 추가한 *들을 잘라내어 보관하고 *이 추가되기 앞까지의 공백을 result에 대입한다. 이후 *을 추가하고 잘라낸 뒷 부분을 합치면 된다. 2022. 1. 11. Binary Index Tree 구현 중.. 노드의 개수가 5인 BIT를 구현해보던 중, 규칙이 성립하기 어려움을 보았다. 둘 중에 어느 그림이 맞는지 몰라 두번 그려보고 결국 그래프의 모습으로 나타내 보았다. 먼저의 이진법으로 인덱스를 표시한 그림을 보면 앞서 배운 업데이트와 구간합을 구할때 마지막 1의 비트를 변환하는 방법은 통용되지 않음을 알 수 있다. 그래서 노드의 개수를 넘는 가장작은 2의 제곱수의 길이에 해당 그래프는 포함시키는 방법으로 해결했다. 이 경우 공간의 낭비가 심한 것 같다. 다른 방법이 있을까? 2022. 1. 4. 이전 1 2 3 4 5 다음
