순간을 기록으로

문제 유형: 스택 바구니가 한쪽으로만 데이터를 넣는 스택 모양 풀이법 우선 스택 문제니 Stack을 선언한다. 그리고 크레인의 작동 위치 횟수만큼 반복되므로 for-each 문을 사용한다. 크레인의 좌우 위치 값은 2차원 board 배열에서 열에 해당되므로 board [][move-1]로 넣어준다. 인덱스의 이므로 -1을 해줘야 한다. 그리고 크레인이 내려가는 모양은 for문으로 구현한다. i가 증가하면서 만약 인형이 없으면(=원소 값이 0이면) 내려가게 되고, 인형이 있으면 스택 바구니 상단과 비교해 같으면 pop()을하고 값을 2 증가시킨다. 만약 같지 않다면 push()를 이용해 바구니에 넣는다. 그리고 인형을 뺏으니 보드에 인형이 있던 위치에 0을 넣는다. 그리고 크레인은 아래로 안 내려가므로 b..

느낀 점 재귀함수란 함수 안에서 자시 자신을 호출하는 함수를 말한다. 이렇게 함수가 자기 자신을 호출하게 되면 끊임 없이 호출이 계속되는데 이렇게 되면 스택오버플로우가 발생하게된다. 따라서 재귀함수는 반드시 1.탈출 조건 2. 자신 호출이 있어야한다. 보통 구조는 다음과 같이 if-else 구조를 가진다. public void function(int n) { if(탈출 조건){ return; } else { function(n-1); } } public class Main { public void DFS(int n) { if (n == 0){ return; } else { DFS(n/2); System.out.print(n%2); } } public static void main(String[] args..

오늘 푼 문제는 버플 정렬 구현 문제이다. 구현이 쉬운 정렬 중 하나다. 버블 정렬은 정렬되는 과정에서 원소 값이 교환하는게 수면위로 올라가는 거품의 이동과 비슷하다고 하여 그렇게 지어졌다고 한다. 버블정렬(=거품정렬, bubble sorting): 두 개의 인접한 원소의 값을 비교하여 정렬하는 방식. 시간 복잡도는 이중 for문을 돌기 때문에 O(N^2)이다. 버블 정렬 특징 데이터를 비교하면서 찾기 때문에 비교 정렬. 정렬 도중 추가적인 공간을 필요로 하지 않기에 제자리 정렬(in-place sort) 참고로 두 원소의 값을 교환하는 과정에 생성하는 임시 변수 temp는 충분히 무시할 수 있도록 작기에 제자리 정렬에 영향을 주지 않는다. 앞에서부터 차례대로 데이터를 비교하기 때문에 '안정 정렬'이다...

느낀 점 Stack의 대표적인 문제는 괄호 문제다. 닫는 괄호(')')이면 액션을 취하고 닫는 괄호(')') 이외의 문자(여는 괄호, 다른 문자)는 stack에 넣어주는 게 포인트. 알아가는 것 스택도 제네릭 타입이어서 for-each문으로 접근할 수 있다. stack.pop()의 리턴 값은 제거된 원소이다. 스택은 stack.get(i) 메서드처럼 인덱스로 접근할 수 있다. import java.util.Scanner; import java.util.Stack; /* * 수도코드 * 문자열을 한 문자씩 탐색한다 * 만약 문자가 ')'이라면 가장 가까운 '('까지 스택에 쌓인 문자열을 제거한다. * 만약 ')'이외의 문자라면 스택에 추가한다. * * 스택의 사이즈만큼 반복한다. * 인덱스를 이용해서 스택..

문제 https://www.acmicpc.net/problem/11729 코드 리뷰 맨 처음에 System.out.println()으로 여러번 출력을 하다가 시간초과가 났다. 그래서 StringBuilder를 사용하여 문자열을 계속 붙여준뒤에 메인함수 마지막에서 System.out.println()을 한 번 호출했다. 입력은 BufferedReader를 사용했다. 변수 num에는 원판의 수를 입력받아 저장한다. sb는 메인 메소드 안에서 선언하지 않고 한 단계 위에서 선언해서 다른 메소드에서도 접근할 수 있도록 했다. 변수 count에는 원판의 총 이동 횟수를 저장한다. 하노이 탑에서 원판의 총 이동횟수는 원판의 갯수가 n이라 할 때 2^n -1이다. 이때 Math.pow()를 사용하는데 입력값과 반환값..

문제 https://programmers.co.kr/learn/courses/30/lessons/70128 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr 주의할점 내적의 합이 int의 범위(-21억~ 21억)를 넘을 수도 있으므로 확인한다. 배열의 길이는 1,000이다 즉 10^3이다. 배열 원소의 최댓값은 1,000이다 즉 10^3이다. 내적의 값이 가장 큰 시나리오는 배열의 길이가 10^3이고 배열 a, b모든 원소의 값..

문제 https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 느낀점 동적프로그래밍에 대해 알게 되었다. 최대한 쉽게 말하자면 재귀적을 값을 구할 때 이전에 구했던 값이라면 다시 연산할 필요 없이 배열에 저장한 값을 꺼내는 방식이다. 해결방법 일반적으로 피보나치의 수는 재귀함수를 통하여 구할 수 있다. 여기서 동적계획법을 사용하면 더 빠르게 값을 구할 수 있다. 동적계획법이란 재귀적으로 함수를 작은 단위로 들어갈 때 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 느낀점 오랜만에 진법 문제를 푸니깐 낯선 느낌이었다. while문을 이용해서 10진법에서 특정 진법으로 바꾸는 방법을 배웠다. 그리고 특정진법에서 바로 10진법으로 값을 바꾸는 Integer.parseInt(String s, int radix)을 새로 알게 되었다. 풀이 // 1.10진법을 3진법으로 바꾼다 /..