문제 https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 풀이 너무 어려운 문제였다. 이 문제는 보드판을 연결 리스트로 표현해서 풀면 해결할 수 있다. class Node{ int val; boolean isEmpty, isFinish; Node next, fastPath; Node(int val){ this.val = val; this.isEmpty = true; } // 노드 연결 Node addNext(int value) { Node nextNode = new Node(value); this.next = nextNode; return nextNode; } // 시작지점..
부동소수점(Floating Point)이란? 부동소수점이란 실수를 컴퓨터 상에서 근사하여 표현할 때 소수점의 위치를 고정하지 않고 그 위치를 나타내는 수를 따로 적는 것으로, 유효숫자를 나타내는 가수와 소수점의 위치를 풀이하는 지수로 나누어 표현한다. 부동소수점의 표준(Standard)은 IEEE에서 제안한 IEEE 754이다. IEEE 754에 따른 부동소수점의 표현은 아래와 같다. 부동소수점은 Single Precision(32-bit), Double Precision(64-bit)로 나타낼 수 있다. S : sign bit로, 1bit를 차지하며 0은 양수를, 1은 음수를 나타낸다. Exponent : 지수를 표현한다. 실제 exponet에 Bias를 더해서 기록한다 Single Precision ..
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 이 문제는 투 포인터 문제이다. 그냥 모든 경우의 수를 다 보면 O(N^2)으로 시간초과가 발생한다. 투 포인터 방식을 사용하면 O(N)에 문제를 해결할 수 있다. 나는 슬라이딩 윈도우 방식처럼 투 포인터를 사용하고 HashMap을 사용하여 해결하였다. 예를 들어 8 30 4 30 7 9 7 30 2 7 9 25 위와 같은 예제는. {7,9,7,3..
데이터베이스 Connection Pool이나 네트워크 소켓처럼 애플리케이션 시작 시점에 필요한 연결을 미리 해두고, 애플리케이션 종료 시점에 연결을 모두 종료하는 작업을 진행하려면, 객체의 초기화와 종료 작업이 필요하다. 스프링을 통해 이러한 초기화 작업과 종료 작업을 어떻게 진행할 수 있을까? 스프링 빈 생명 주기 콜백 스프링 빈은 객체를 생성하고, 의존관계 주입이 다 끝난 다음에야 필요한 데이터를 사용할 수 있는 준비가 완료된다. 따라서 초기화 작업은 의존관계 주입이 모두 완료되고 난 다음에 호출해야 한다. 개발자가 의존 관계 주입이 모두 완료된 시점을 어떻게 알 수 있을까? 스프링은 의존관계 주입이 완료되면 스프링 빈에게 콜백 메서드를 통해 초기화 시점을 알려주는 다양한 기능을 제공한다. 또한 스프..
바이트 저장 순서 컴퓨터는 데이터를 메모리에 저장할 때 Byte 단위로 나눠서 저장한다. 따라서 연속되는 바이트를 순서대로 저장해야 하는데, 이것을 바이트 저장 순서(Byte Order)라고 한다. 이때 바이트가 저장된 순서에 따라 빅 엔디안, 리틀 엔디안 두 가지 방식으로 나눌 수 있다. 빅 엔디안(Big-endian) 빅 엔디안 방식은 낮은 주소에 데이터의 높은 바이트(MSB : Most Significant Byte)부터 저장하는 방식이다. 이 방식은 평소 사람이 사용하는 선형 방식과 같아 메모리에 저장된 순서 그대로 읽을 수 있으며, 이해하기 쉽다. 예를 들어, 아래와 같이 저장할 32bit 크기의 정수가 있다고 가정하자. 0x12345678 그럼 이 정수는 아래와 같이 4개의 byte (4byt..
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 이 문제는 간단한 DP 문제였다. maxDp와 minDP를 따로 나누어서 해결하면 간단하다. 우선, maxDp의 경우는 아래와 같은 점화식을 세우면 된다. maxDp[i][j] = i번째 줄에서 j번째 숫자를 선택할 때 최댓값 ( 0
문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 이 문제는 최장 증가 부분 수열(LIS) 문제이다. LIS에 대해서는 다음 게시글이 설명을 자세하게 있으니 참고하자 https://sskl660.tistory.com/89 [Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence) *최장 증가 부분 수열(LIS, Longest Increasing Subsequence) ->최장 증가 부분 수열이란, 주어진 ..
문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 처음에는 단순 DFS로 문제를 접근했다. 하지만 DFS를 사용하면 시간 초과가 발생한다. 이 문제는 DP를 사용해서 해결해야 한다. 점화식을 아래와 같이 세우면 된다. dp[i][j] = i번째 집을 j 색깔로 칠할 때 비용의 최솟값 dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) // 이때 j와 같은 숫자는 제외..
다양한 의존관계 주입 방법 의존관계 주입은 크게 4가지 방법이 있다. 1. 생정자 주입 2. 수정자 주입(setter 주입) 3. 필드 주입 4. 일반 메서드 주입 생성자 주입 생성자 주입은 이름 그대로 생성자를 통해 의존관계를 주입받는 방법 생성자 호출 시점에 딱 한 번만 호출되는 것이 보장된다 주로 불변, 필수 의존 관계에 사용한다 불변 처음에 세팅한 값을 변경하는 것을 허용하지 않는 것을 불변이라고 한다. 필수 변수에 final 키워드를 적용하면 무조건 값이 초기화되어야 한다. 따라서 해당 필드가 초기화되어있지 않으면 컴파일 오류를 발생시킨다. 생성자로 해당 필드를 필수로 초기화해야 한다. @Component public class PizzaService { private final PizzaRep..
CISC (Complex Instruction Set Computer) CISC란 연산에 처리되는 복잡한 명령어 집합을 수백 개 이상 탑재하고 있는 프로세서이다. 인텔 계열의 모든 프로세서는 CISC 프로세서이다. CISC는 다음과 같은 특징을 갖는다. 1. 복잡하고 기능이 많은 명령어로 구성된 프로세서 2. 복합 명령을 가짐으로써 하위 호환성을 확보 3. 트랜지스터 집적에 있어 효율성이 떨어짐 4. 전력 소모가 큼 5. 속도가 느리고 가격이 비쌈 6. 호환성이 절대적으로 필요한 PC 환경에 사용 7. 명령어 해석에 필요한 회로가 복잡해 병렬 처리가 쉽지 않음 RISC (Reduced Instruction Set Computer) RISC란 적은 수의 명령어를 수행하도록 설계된 마이크로프로세서이다. 복잡..