알고리즘

🌱 Recursive Function ( 재귀 함수 )👉🏻 재귀(再歸) : 주어진 문제를 해결하기 위해 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식. 어떤 루틴이나 프러시저가 자기 자신을 반복적으로 호출하여 문제를 풀어나가는 알고리즘. ( - Naver Dictionary) 정의는 정말 쉽다. 그리고 코딩테스트에서 정말 많이 사용된다.(dfs,백트래킹, 수열 조합.. 등등)하지만 재귀 함수의 호출스택이 어떻게 쌓이는지? 또 어느 상황에서 사용해야하는지 이해하지 못한다면 재귀함수를 내 스스로 판단하여 사용하지 못하고 암기식으로 사용하게 된다.재귀 대표 문제와 함께 Recursion 에대해 알아보자!💡 호출 스택(Call Stack)이란? ->참고하던지- 프로그램에서 함수나 메서드를 호..

문제https://www.acmicpc.net/problem/1406 문제를 읽고 처음 했던 생각문자열 수정(삽입/삭제)가 많이 일어나겠다 -> StringBuilder를 사용하자!!문자열 크기는 600,000으로 크게 신경안써도 되겠다자로구조는 크게 필요 없겠는데cursor 변수를 선언해 인덱스 위치를 저장해주면 되겠다명령어는 switch case문으로 처리하자결론주어진 문자열을 StringBuilder를 사용해서 명렁어에 맞게 조작해 최종 문자열을 생성하면 되겠다❗️❗️ 코드package stack;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringT..

여러가지 정렬 알고리즘중 이름부터 가장 빠른 퀵정렬 QuickSort에 대해 알아보자! 퀵 정렬의 개념기준점(pivot)을 기준으로 왼쪽에는 pivot보다 작은 값이, 오른쪽에는 pivot보다 큰 값이 부분배열에 배치되게 하는 행위를  반복하여그 분할(partition)의 크기가 1이하가 될때까지 재귀적으로 호출하여 정렬하는 알고리즘.  시간복잡도 평균 : O(NlogN) / 최악 : O(N^2) - pivot선정할때마다 최소값 고르는경우 한번 수행할 때마다 정렬할 데이터가 절반씩 줄어든다 -> logNN만큼 partition을 나누는데, 나눌 때마다 데이터가 절반씩 줄어드므로 ->O(NlogN)이다 퀵 정렬 pivot 정하는 법은 사실 정해진건 없다. 맨 왼쪽 원소가 pivot중간 원소가 pivot맨 ..

코딩테스트 문제를 풀때 문제를 제대로 파악하지도 않은 채 무작정 코드 부터 치는 경향이 있었다.그러다 보니 수정하거나 잘못된 방법으로 접근하는 경우가 많아졌다.이러한 무지성으로 코테 문제를 접근하는 습관을 바꾸고자 내가 처음 문제를 봤을 떄 했던 생각들, 또 시행착오들을 기록하고 개선하려는 목적으로 이 글을 쓴다. 문제 소개 : https://www.acmicpc.net/problem/1920  문제를 읽고 처음 했던 생각탐색문제구나..!범위가 -2^31결과 여부를 저장하는 result 배열이 필요할까? -> 굳이 저장해서 관리할 필요없네.배열의 크기가 100,000(십만)이므로 2중for문을 쓴다면 시간초과 위험이 있다. -> 브루투 포스는 아니네결론그럼 범위를 절반씩 줄이며 탐색하는 "이진 탐색" 알..

백준-10814번 문제 처음 생각했던 것시간제한 3초?-> 시간제한 이슈는 없을 것같다.나이와 이름을 한번에 저장해야하네? -> Person 클래스를 만들어서 인스턴스변수 age,name으로 저장하자나이순으로 정렬하자 -> 빠른 퀵소트로 구현해보자.나이가 같으면 가입한 순으로 출력하자 -> 이거에 대한 생각은 못하고 짯음시행착오퀵소트로 구현하니 나이순으로 정렬하는 건 가능 but 같은 나이일때 가입한 순서 보장 X생각해보니 퀵소트는 앞에서부터 정렬되기에 들어온 순서대로 순서 보장이 구조적으로 불가능하다.해결안정적인 정렬(즉 ,순서를 보장하는 정렬 방법 고려) ->Array.sort로 해보자그럼 두 객체(a, b)를 어떻게 비교할 것인가? 부등호로 비교하려 하면, 나이(age)를 기준으로 비교되는 건가? ..