내가보려고만든 메자노트

문제보러가기 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 이 문제는 기존 bfs처럼 영역을 나눠서 영역의 개수, 영역의 최대 넓이 , 벽을 하나 제거한 후의 영역의 최대 넓이를 구하는 여러 문제가 합쳐져 있는 복합적인(?) 문제였다. 여기서 까다롭게 봐야 할 점은 벽을 제시할 때 0~15의 값으로 주어지며 이를 bit로 변환하여 사용해야 한다는 점이었다. 문제풀이 - bfs로 구한 영역을 증가하는 groupCnt를 키값으로 묶어 아래 그림처럼 group [][]에 저장해준다. -bfs로 영역을 구할 ..

java를 통해 개발을 하면서 jvm위에서 돌아간다는 것쯤은 알고 있을 것이다. 하지만 프로그램이 실행되고 처리되는 과정에 대해 정리가 되지 않았던 것 같아 정리하면서 여러 가지 궁금점을 포함해 공부해보고자 한다! JVM(Java Virtual Machine)이란? : 자바 코드를 CPU나 운영체제(플랫폼)의 종류와 무관하게 실행할 수 있도록 하는 주체이다. → 왜? java는 운영체제 위에서 바로 실행이 되지 않아 JVM이 필요할까? : Java 컴파일러는. java 파일을. class 파일로 컴파일한다. 이는. java 파일을 Java byte code로 변환하여. class 만드는 것인데 Byte Code는 기계어가 아니기 때문에 OS에서 바로 실행이 되지 않는다. 이를 해결하기 위해 JVM을 통해..

문제보러가기 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 이문제는 당시에 난이도 상에 포함되었던 문제라고 한다. 막상 풀이를 보게 되면 별거 없는 거 같지만, 어떻게 구현해서 풀어야겠다는 감이 잘 오지 않을 수 있다! 나의 경우는 문제 이해부터가 오래 걸렸던 거 같다 ㅎ.. 문제풀이 - 크루들의 도착시간인 timetable을 int로 변환하여 오름차순으로 정렬하기 위해 PriorityQueue에 저장한다. - 첫차 출발시간인 09:00시부터 t분 간격으로 ..

문제보러가기 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이문제는 전형적인 탐색 문제로 연결된 영역이 몇 개가 있는지 구하는 문제였다. 다른 점이라면 위, 아래, 오른쪽, 왼쪽이 아닌 대각선 포함 8방향으로 탐색해야 한다는 점. 문제풀이 -map [][]에 입력받은 값을 저장해준다. -map을 이중 for문으로 탐색하면서 1일 경우(섬일 경우) 그리고 방문하지 않았을 경우에 bfs()를 수행한다. -4방향이 아닌 대각선 포함 8방향으로 체크해주면서 연결된 섬의 개수를 체크한다. 사실 이문제는 "메모리..

문제보러가기 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 DP문제로 크게 어렵지는 않았지만 나의 경우 마지막 날짜인 n일까지 일할 수 있다는 것을 놓쳐서 시간이 좀 더 걸렸던 문제였다 ㅎ,,, 문제풀이 -주어진 시간을 저장하는 t [] 배열과 금액을 저장하는 p [] 배열을 생성한 후 값을 저장한다. -해당 날짜까지 받을 수 있는 최대 금액을 저장하는 dp배열을 생성한다. -총금액 중 최대 금액을 저장하는 max를 선언한다. -여기서 중요한 점 dp배열은 dp [n]..

문제보러가기 Longest Substring Without Repeating Characters - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 우선 이문제는 중복되지 않는 부분 문자열의 가장 긴 길이를 찾는 문제였다. 투 포인터를 사용해서 해결하였다. 문제풀이 -빈 문자열이나 한 글자인 문자열은 미리 체크를 하여 빼준다. -첫 글자를 부분 문자를 확인하는 str변수에 넣어준 후 반복문을 통해 탐색해준다. -end가 주어진 문자열인 s길이를 벗어날 경우 종료...

문제보러가기 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 이문제는 보자마자 음? BFS 써야지 했다가 바로 시간 초과가 나버린 문제다. BFS의 비용을 최소화하기 위해 그룹핑하는 과정부터 필요하다. 이걸 분리 집합이라고 부른다. 문제풀이 -그룹화가 된 배열 정보를 담을 수 있게 group [][] 배열에 0 끼리 묶음 정보를 저장한다. -여기서 포인트는 BFS를 통해 그룹을 만들 때 이미 만들어진 그룹에 속한 인덱스는 탐색하지 않고 넘기는 것 -벽이 아닌 즉 0인 인덱스는 한 그룹에..

문제보러가기 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 이문제는 다익스트라의 기본이 되는 문제였다. 알고리즘을 알고는 있었지만 문제를 풀어본 적이 없는 것 같아 기초 문제부터 시작! 문제풀이 -각 노드의 간선 정보를 저장할 list와 출발 노드부터 해당 노드까지의 최소거리를 갱신해주는 배열 dist []를 선언한다. -list의 경우 노드 숫자만큼의 배열과 각 노드의 연결된 노드와 가중치의 정보를 저장할 수 있도록 List list []로 선언해 준다. * Point 2는 노드..