코딩하는 고릴라

🐒 문제 7626번: 직사각형 첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 www.acmicpc.net 🐈 풀이 1. y좌표 압축 2. x축 정렬 후 x축 방향으로 순차적으로 스위핑 3. 스위핑하며 직사각형의 세로선 활성화 및 비활성화를 통해 좌표상의 직사각형 넓이를 구한다. 1. 주어지는 x, y 좌표의 최대값이 매우 커 이를 바로 활용해 트리를 만들 수 없다. 따라서 좌표 압축을 필요로 한다. 2. 스위핑 기법을 통해 문제풀이를 진행하되, 과연 어떤 값을 어떻게 저장하고 꺼내와야 하는지의 아이디어가 중요..

🐒 문제 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🦍 풀이 핵심 : BFS 알고리즘을 통해 물, 고슴도치를 퍼뜨리며 고슴도치가 땅굴에 도달할 수 있는지를 구현 1. 매 턴마다 물을 먼저 퍼뜨리고, 그 다음 고슴도치를 이동시켜야 한다. => 맵을 입력받고 생성하는 과정에서 고슴도치의 위치, 물의 위치를 저장시켜준다. map = new char[R][C]; for (int i = 0; i < R; i++) { // 한 줄 입력받고 String input = br.readLine(); for (int j = 0; j <..

🐒 문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 🐈 문제풀이 핵심 이분 탐색 기법을 사용할 줄 알고, 어떤 상황에서 어느쪽 절반을 택해 탐색을 파고 들어가야할 지 결정할 수 있어야 하는 문제였다. 한 쪽 절반을 선택하여 파고 들어가는 부분을 결정하는데 특정 변수의 값을 기준으로 하기 때문에 이분 탐색의 응용인 매개 변수 탐색(Parametric search)을 진행하여야 한다. 아래 예시를 보자. 길이가 9인 랜선 1개를 가지고 있고, 이를 잘라 길이가 균등하면서 가장 긴..

🐒 문제 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 🐈 문제풀이 핵심 A번 ~ B번 인덱스를 확인했을 때 해당 구간에 A번부터 B번까지의 값이 모두 존재하는지 확인하는 것을 어떤 식으로 구현할지가 관건이다. 이를 위해 해당 구간의 최솟값, 최댓값을 구하여 확인하는 방법을 이용했다. A번 ~ B번 인덱스 구간의 값을 확인했을 때, 최소값이 A이고 최댓값이 B라면 그 둘 사이의 값은 모두 A와 B 사이에 있음을 보장받는다. 따라서 해당 구간의 최솟값, 최댓값만 구..

문제 번호 제 목 유 형 5033 Money Matters 유니온 파인드 오늘은 겨우겨우 한 문제만 풀었다. 백준 티어 목표는 일단 달성했으니,,, 당분간은 1일 1문제 하면서 다른 공부 힘주기 또 스프링 관련해서도 파일 업로드를 공부해봤다. 머리가 와르르 무너질거 같은데,, 버텨,, 자바의 정석도 원래는 책만 쭈우우욱 읽었었는데 유튜브 강의를 봤더니 훨씬 정리가 잘 되고 머리에도 잘 들어오더라 앞으로 쭉 강의로 봐야지,, 책 안녕 요거 말고도 KMP 공부하고,, 프론트엔드 공부도 좀 하고 싶었는데 왜 12시야 오늘은 오랜만에 무리 좀 해보고,, 자자,,, 오늘 한 일 - 알고리즘 문제 풀이 [1] - 스프링 - 파일 업로드/다운로드 - 자바 - 컬렉션, 지네릭스 🦍🦍🦍

그래프 표현 방식 중 하나인 인접 리스트의 구현을 코드를 따라가며 차근차근 이해해보자,, 1. : 가중치가 없는 무향 그래프 1 : 리스트 배열 선언 2 : 리스트 배열 초기화 3 : 연결 정보 저장하기 4 : 요약 2. : 가중치가 있는 그래프의 표현 인접 리스트? 그래프를 다룰 때, 한 정점에서 다른 정점으로의 연결 정보를 리스트 형태로 담아놓은 것이다. 1. 가중치가 없는 무향 그래프의 인접 리스트 표현 먼저, 다음과 같이 4개의 정점(0, 1, 2, 3)이 주어졌으며, 가중치가 없으며 방향성이 없는 무향 그래프를 가정해 보자 1. 정점의 개수를 입력받고, 이를 길이로 하며 각각의 인덱스에 리스트를 담아 줄 배열을 선언해 준다. int N = 4; // 정점의 개수로 4가 주어졌다고 가정하자 Lis..