Noooodle's Footprints

쉬운 문제.. 짝수는 % 2 == 0 이용하고짝수중 제일 작은 값(min)은 if문 중첩해서 사용했다.min 제일 큰 값으로 초기화하는것도 잊지 말고.. package Part1.Ch04.BOJ3058;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ3058 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.i..

진법변환&Palindrome이 섞인 문제. 각각은 구현해봤지만 섞어서는 처음이다. 앞에 11005번처럼 B진법 문자를 하나하나 다 대응하지 않았다. 출력하지 않으니 굳이 문자를 대응할 필요가 없기 때문이다. N이 'B의 ?승 * ?' 의 합으로 표현되는지 계산해 B진법으로 바꿔주었다. 10 -> 2^3*1 + 2^2*0 + 2^1*1 + 2^0*0 이런식으로 표현하는 것이다. 구하는 방법도 간단하다. for문을 이용해 제일 큰 지수를 구하고, 또 for문을 이용해 B^(제일 큰 지수) * ? 가 N보다 커지는 순간을 찾으면 된다. 그리고 ?를 char배열에 저장한다. char배열은 B진법으로 변환했을때 자릿수 만큼의 크기를 가진다. 10 -> 2^3*1 + 2^2*0 + 2^1*1 + 2^0*0 으로 예..

어디서 많이 해본 진법변환 문제.. 보통 2진수, 8진수, 16진수로만 바꿨는데 36진법으로도 바꿔보았다. 사실 방법은 같으니까... 1. 진법 배열을 미리 만들고 2. 값을 입력받은 후 나누기 계산을 통해 진법 출력한다. 이때 재귀를 이용한다. 나는 재귀가 좋아.. 1. 진법 배열 미리 만들기 0   1   2   3  ...   Y     Z  [0] [1] [2] [3] ... [34] [35]이런식으로 미리 저장해둔다. for문을 쓸까 하다가 ..알파벳부터는 또 새로 만들어야 하니까 귀찮아서 아예 초기값으로 줘버렸다.예를들어 8진법이면 0~7 까지만 사용할거고 실제 출력값은 Bformation[0] ~ [7]이 될거다. ('0' ~ '7')이렇게 한 이유는 알파벳 때문이다. 숫자 0~9가 아닌 문..

Brute Force 방식으로 풀어야 한다. 사실 이게 브루트 포스 방식인지 몰랐는데.. 내가 학교에서 푼 코딩은 대부분 브루트 포스였구나 하고 깨달았다. 아무튼~ T : 변수 K를 입력받는 횟수K : 3개의 삼각수인지 확인할 변수Tn[ ] : Tn을 미리 구해서 저장해놓은 배열 생각한 방식은.. 1. Tn을 미리 구해놓는다. 2. 재귀를 이용해 K - Tn을 한다. 3. K - Tn을 할 때마다 횟수를 더해준다. 간단히 요약하면 이렇게 된다. 다른 쉬운 풀이방법도 많은데 재귀가 더 익숙해서 재귀로.. 1. Tn을 미리 배열에 저장해둔다Tn = n * (n + 1) / 2 이므로 그냥 계산해서 미리 배열에 저장하면 된다. 그럼 몇번째 Tn까지 저장하면 될까..? 문제에서 K는 1000이하라고 했으므로 '..

n: 수열의 크기, n의 크기 만큼 입력받음 (1 a[ ]: 입력받는 배열x: ' a[i] + a[j] = x ' 에서의 x 2가지 방법이 떠올랐다.1. a[n] 에 입력받고, 하나하나 x - a[i] 의 값이 a[n] 에 있는지 확인한다. 이중 for문 사용-> O(n^2)2. count sort 사용, 1000000 칸의 배열을 만들고 입력받은 n의 값을 증가시킨다. 그리고 a[i]와 a[x - i]가 둘 다 1인지 확인한다. -> 1000000번 을 두 번 돌면 되므로 O(n) 시간복잡도 때문에 1번은 안된다.. 그러므로 2번 선택 import java.io.*;import java.util.StringTokenizer;public class BOJ3273 { // count sort p..

counting sort와 bufferedReader, Writer를 사용한 문제이다. 정렬은 개념 자체는 단순하지만, 정렬 알고리즘의 종류도 많아서 구분하기 어렵다.. 게다가 어떤 문제에 어떤 정렬 알고리즘을 써야할지 헷갈린다. 시간복잡도도 계산해야 하기 때문에 ㅎㅎ 처음엔 merge sort로 풀었는데 계속 시간초과가 나더라.. counting sort 정리글 : https://noooodlefts.tistory.com/28 [Algorithm]Sort, 정렬(3)7. Radix sort8. Counting sort 지피티한테 물어봄 추후 수정..Counting SortCounting Sort는 정수 배열을 정렬하는 데 사용되는 알고리즘입니다. 주로 값의 범위가 제한된 경우에 유용합니다. Counti..

4. Merge sort 5. Quick sort 6. Heap sort Divide-And-Conquer, 분할정복법분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복: 각각의 작은 문제를 순환적(재귀)으로 해결합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 Merge sort, Quick sort, Heap sort 모두 분할정복법을 사용한다. 세 가지 방법 모두 시간복잡도는 O(nlogn)으로 동일하다. *예시는 오름차순 정렬*노란색은 정렬된 부분*파란색은 정렬할 부분4. Merge sort, 합병정렬1) 배열을 절반으로 나눔 2) 나뉜 배열 각각을 정렬함 3) 나뉜 배열을 합치면서 정렬순환적(재귀) 코드이다. 재귀는 자기 자신을 호출하는 것을 말한다. 처음..

이 문제는 두 가지 방법으로 풀 수 있다. 배열을 직접 이동시키거나 단순히 횟수만 세거나.. 배열을 직접 만들어서 이동시키는 것은 insertion sort이다. 응용도 아닌 그저 삽입정렬 그 잡채.. insertion sort에 관해서 포스팅을 했으므로 링크를 첨부한다. https://noooodlefts.tistory.com/25 [Algorithm]Sort, 정렬(1)정렬은 말 그대로 순서대로 정리하는 것을 의미한다. 뒤죽박죽인 숫자를 오름차순, 내림차순으로 정렬할 수 있다. 뭐 그런 것들.. 데이터들을 정리할때 필요하다. 정렬 알고리즘은 여러가지가noooodlefts.tistory.com  import java.io.BufferedReader;import java.io.IOException;imp..

입력받을때 공백을 넣어서 받는 걸로 착각해서 오래걸린 문제.. 아직 자바가 익숙하지 않아서 힘들다. 문제 자체는 어렵지 않다! 1. 가로세로에  병사가 배치되어있는지 확인하고 2. 병사가 하나도 배치되지 않은 행(또는 열)의 수를 세어서 3. 가로 세로 중 더 큰 값을 출력하면 된다. 예시를 보면 ..(4, 4) 에 병사가 하나도 없을때는 모든 행에 병사가 없으므로열 배열: [0]0 [1]0 [2]0 [3]0   -> 0의 개수(병사가 없는 열의 개수): 4행 배열: [0]0 [1]0 [2]0 [3]0   -> 0의 개수(병사가 없는 행의 개수): 4둘 중 더 큰 값을 출력, 여기서는 같으므로 4가 정답이다. (3,5)인 경우에는..열 배열: [0]1 [1]1 [2]1                 -> ..

get(int idx): idx번째 원소 반환 -> O(1)change(int idx, int val): idx번째 원소를 val로 변경 -> O(1)append(int val): 가장 뒤에 원소 삽입 -> O(1)  배열은 고정 길이, 배열이 꽉 찬 경우에는 쓸 수 없음 리턴값 boolean타입: 원소 삽입에 성공하면 true, 실패하면 falseinsert(int idx, int val): 현재 idx번째 원소의 앞에 원소 삽입 -> O(n)idx번째부터 뒤의 값을 한 칸씩 오른쪽으로 미루고 idx번째에 val을 삽입함idx는 배열의 원소 개수 이하여야 함배열은 고정 길이, 배열이 꽉 찬 경우에는 쓸 수 없음 리턴값 boolean타입: 원소 삽입에 성공하면 true, 실패하면 falseerase(in..