전체 글
그리디 알고리즘
그리디 알고리즘 그리디 알고리즘이란 지금 주어진 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 결과를 선택한 결과 값이 전체적으로도 최선이기를 바라는 알고리즘이다. 일반적인 그리디 알고리즘 풀이 방법을 적어보자면 아래와 같은 흐름을 따른다. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 탐색 범위를 줄여도 올바른 답을 낸다는 것을 수학적으로 증명한다. 알고리즘을 구현한다. 그리디 알고리즘은 모든 경우에서 통하는 알고리즘은 아니다. 현재에 약간 손해보더라도 전체적으로 봤을 때는 이득인 경우에 통하지 않는데, 예를 들자면 유명한 마시멜로 이야기와 같이 지금 당장은 마시멜로를 1개를 받을 수 있지만 조금 기다리는 경우 2개를 받을 수 있는 경우 그리디 알고리즘으로 풀면 틀린 경우가..
Git 버전 관리
버전관리에 들어가기에 앞서 우선적으로 세 가지 개념을 먼저 정리해야한다. working tree : 사용자가 파일을 만들거나 수정하는 디렉토리이다. staging area : working tree에 있는 파일들 중 버전으로 만들고자 하는 것들을 저장하는 곳이다. repository : 만들어진 버전들을 저장하는 곳이다. 버전관리에 자주 사용하는 명령어들과 함께 과정을 정리해보면, git init : 디렉토리를 git을 사용할 수 있도록 git repository로 지정하고 .git이라는 숨김폴더를 생성한다. git status : working tree의 상태를 보여준다. git add : 버전으로 만들고자 하는 파일을 staging area에 추가한다. git commit : staging area에..
BOJ 10828 스택 [Java]
BOJ 10828 스택 - 문제 링크 https://www.acmicpc.net/problem/10828 - 문제 해설 자바의 util.Stack을 이용하여 풀면 쉽게 풀 수 있지만, 직접 스택을 구현하여 풀었다. tail은 스택 제일 상단 원소의 인덱스 값이다. 구현하는 데 있어 딱히 어려운 점은 없고 자료형의 변환에만 신경써주면서 구현하면 된다. 한 가지 시행착오를 겪은 것이 있다면, 처음에 코드를 짤 때는 st.nextToken()을 받아줄 변수를 만들지 않았다. 예를 들자면, 아래의 67번째 줄의 코드를 if(st.nextToken().equals("push"))와 같이 짰다. 나머지 else if문들도 똑같이 작성하였다. 이렇게 구현을 하니 내가 얻고자 하는 값이 나오지 않았다. StringTo..
BOJ 11004 K번째 수 [Java]
BOJ 11004 K번째 수 - 문제 링크 https://www.acmicpc.net/problem/11004 - 문제 해설 메모리와 시간 제한이 여유로워서 sort 메소드를 이용하여 쉽게 풀 수 있는 문제이다. sort 메소드말고 다른 방식으로 풀 경우 quick sort를 이용해서 풀 수도 있을 것 같다. 이 문제를 풀면서 처음에 한 가지 간과한게 있다면, BufferedReader와 StringTokenizer를 이용하여 한 줄씩 입력 받아 토큰으로 만들었기때문에, 18줄의 코드처럼 StringTokenizer를 한 줄마다 다시 만들어줄 필요가 있다. - 코드 보기 import java.io.*; import java.util.*; public class Main { static int n; sta..
BOJ 10989 수 정렬하기 3 [Java]
BOJ 10989 수 정렬하기 3 - 문제 링크 https://www.acmicpc.net/problem/10989 - 문제 해설 N이 10,000,000 이하의 자연수이기 때문에 sort를 쓰면 메모리 초과가 난다는 사실을 인지해야한다. 정렬해야하는 숫자들이 10,000 이하라는 사실에서 counting sort를 쓰면 되겠다는 힌트를 얻었다. cnt[i]를 1-10000 범위의 자연수 i가 입력된 횟수라고 설정하고 구현해주면 된다. 출력할 때는 cnt[i] > 0 이 아닌 경우에는 i가 입력되지 않은 경우이니 제외한다. - 코드 보기 import java.io.*; public class Main { static int n; public static void main(String[] args) thr..