Algorithm
[BOJ] 백준 2661 좋은 수열 - Python/Java
문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 해설 이 문제는 백트랙킹과 그리디 알고리즘을 동시에 사용해서 해결한 문제입니다. 우선 문제에서는 1, 2, 3만을 가지고 길이가 N인 좋은 수열들 중 가장 작은 수를 나타내는 수열을 만들어야 하는데요. 이를 위해서는 필연적으로 작은 숫자를 우선으로 수열을 만들어보고, 해당 수열이 좋은 수열이면 문제의 조건을 만족할 것이라는 그리디한 선택을 떠올릴 수 있습니다. 하지만, 계속해서 그리디한 선택을 했을 때 ..
Java & Kotlin
[JAVA] 자바 hashCode()
1. 자바 hashcode() 자바의 hashcode() 메서드는 Object 클래스의 메서드로써, 모든 클래스는 Object 클래스를 상속하기 때문에 사실 상 모든 객체에서 가지고 있는 메서드라고 볼 수 있습니다. 그리고 이 hashCode() 메서드는 해싱 기법에 사용되는 해시함수(hash function)을 구현한 것인데요. 해시함수는 찾고자 하는 값을 입력하면 그 값이 저장된 위치를 알려주는 해시코드(hash code)를 반환합니다. 2. equals()와 hashCode() equals() 메서드 역시 Object 클래스가 가진 메서드입니다. equals는 매개변수로 객체의 참조변수를 받아서 비교하고, 그 결과를 boolean 값으로 리턴하는데요. 실제 Object 클래스 안에 equals 메서..
Algorithm
[BOJ] 백준 4811 알약 - Python/Java
문제 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 해설 DP를 통해 문제를 해결할 때 고민하는 부분은 크게 세 가지입니다. 1. 현재 상황은 이전의 상황에서 어떻게 변하는가? 2. 상황의 변화를 표현하기 위해 필요한 변수는 몇 개인가? 3. DP 테이블의 초기화는 어떻게 해야하는가? 이 문제를 위 관점에서 정의해보겠습니다. 문제에서 주어진 각 시점에서 선택할 수 있는 변화는 '완전한 알약 하나를 먹거나', '반절짜리 알약 하나를 먹거나' 두 가지입니다. 따..
CS/Network
[네트워크/Network] 링크 계층 주소체계(MAC Address)와 ARP
0. 들어가면서 아래 포스팅에서 라우터의 입력 포트 처리 및 목적지 기반 전달 개념에 대해 공부를 했었습니다.
Algorithm
[BOJ] 백준 1719 택배 - Python/Java
문제 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 해설 이 문제는 기본적으로 다익스트라 알고리즘을 이용해서 풀 수 있는데요. 문제에서 요구하는 X 지점에서 Y 지점을 최단거리로 이동할 때 첫번째로 방문하는 지점을 구하기 위해서는 필연적으로 이동하는 '경로' 역시 저장해줘야 하는 문제입니다. 한편, 다익스트라 알고리즘에서 경로를 저장하는 법은 Dictionary나 Map을 이용하면 쉽게 구현할 수 있습니다. 기본적으로 각 지점의 이전 지점만을 저장하기 때문에 1:1로 매핑이 될 수밖에 없기 때문인데요...
CS/Network
[네트워크/Network] 세션(Session), 쿠키(Cookie), 캐시(Cache)의 구분
0. 들어가면서 세션, 쿠키, 캐시는 기본적으로 HTTP 프로토콜의 특징을 이해해야 왜 필요한지 이해할 수 있는 개념이라고 생각합니다. 그리고 그 중에서도 이 개념들과 관련이 깊은 HTTP의 비상태(stateless) 프로토콜이란 무엇인지에 대해 짚어보려고 하는데요. 참고로, HTTP의 비상태성은 HTTP의 지속 연결과는 구분되는 개념입니다. HTTP의 지속 연결은 서버가 응답을 보낸 후에 TCP 연결을 그대로 유지하는 특징을 말하는데, 이는 클라이언트와 서버가 하나의 지속 TCP 연결을 통해 데이터를 주고받고, 일정 시간(Timeout)동안 사용되지 않으면 연결을 닫는 것을 말합니다. HTTP 헤더의 Keep-alive가 이를 말해주고 있죠. 1. HTTP, 비상태 프로토콜(Stateless Proto..
Algorithm
[BOJ] 백준 11000 강의실 배정 - Python/Java
문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 해설 그리디(Greedy)하게 풀 수 있는 간단한 문제이지만 약간의 고민해야 할 부분이 있는 문제라고 생각합니다. 기본적으로 이 문제는 '어떤 강의실을 차지하고 있는 수업이 끝나면, 해당 강의실을 재사용할 수 있다'는 점을 생각해야 하는데요. 이를 바탕으로 시작 시간이 빠른 수업을 먼저 강의실에 배정하는 전략을 세울 수 있습니다. 그렇게 하면 수업의 시작 시간과 사용 중인 강의실의 종료 시간을 비교해서 종료 시간보다 크거나 같은 수업은 강의실을 추가로 사용하지 않을 수 있기 때문이죠. 하지만 이렇게 그리디..
Spring & Springboot
[스프링/Spring] Spring JPA의 지연 로딩과 N+1 문제
1. N+1 문제란? N+1 문제는 JPA를 이용해서 개발을 하다보면 처음에 무조건 만나게 되는 문제라고 생각합니다. N+1 문제란 무엇인지 설명하기 위해 아래 엔티티와 코드를 보도록 하겠습니다. 회원(Member)과 주문(Orders), 배송(Delivery) 테이블이 있고 회원과 주문은 일대다, 주문과 배송은 일대일 관계를 가지고 있습니다. * N+1 문제 설명에 집중하기 위해 생성자나 연관 관계 메서드는 생략하고, 테이블도 간단하게 설계했습니다. @Entity @Getter @Setter public class Member { @Id @GeneratedValue @Column(name = "member_id") private Long id; private String name; @Embedded p..
Algorithm
[BOJ] 백준 22116 창영이와 퇴근 - Python/Java
문제 https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 해설 이 문제는 시작점부터 도착점까지 이동하면서 경로상의 최대 경사의 최소값을 찾는 문제로 BFS와 이분탐색을 이용하여 해결할 수 있습니다. BFS는 그래프의 최단 경로를 구할 때도 사용할 수 있지만, 이 문제에서는 모든 경로를 완전 탐색하는데도 사용할 수 있는데요. 현재 지점을 기준으로 네 방향을 바라보고, 네 방향 중에서 현재 임계값(최대 경사로 정한 값)보다 경사가 작거나 같고, 방문하지 않았다면 그 곳을 이동 가능한 영역으로 보기 때문입니다. 다시 말해서, 간단한 BFS 구현을 생각해보면 상하좌우의 네..
Algorithm
[BOJ] 백준 16235 나무 재테크 - Python/Java
문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 해설 이 문제에서 구현해야 하는 내용은 그렇게 어렵지 않습니다. 봄, 여름, 가을, 계절에 해야하는 일들을 그대로 코드로 구현하면 되는데요. 우선 땅이 가진 양분 정보, 나무들의 정보, 추가되는 양분의 정보를 각각 저장하는 자료구조가 필요합니다. 저같은 경우 파이썬에서는 모두 리스트로 입력을 받았고, 자바에서는 나무들의 정보는 우선순위큐를 이용했고 나머지는 배열을 이용해서 받..
