꾸물꾸물 졔의 개발공부

11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [ 알고리즘 ] ( 우선순위 큐 + 그리디 알고리즘 ) : 최소의 강의실을 사용하기 위해서 , 강의를 시작시간을 기준으로 오름차순 정렬한다. 1. 주어진 강의를 int[][] 배열에 시작시간-종료시간으로 저장한다. ( * 시작시간을 기준으로 오름차순 정렬, 만약 시작시간이 같을 경우엔 종료시간 기준 오름차순 ) 2. 우선순위큐에 첫번째 강의의 종료시간을 add 한다. 3. 모든 강의가 끝날 때까지 다음 과정을 반복한다. 큐의 제일 처음원소를 peek() 한다. ( = 현재 사용하고 있는 강의실 중, 가장 빨리 ..

5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net [ 알고리즘 ] ( 단순 구현 ) : 사방탐색을 통해, 가라앉을 섬을 체크해준뒤, 남아있는 섬의 행 최소/최대 값, 열 최소/최대 값을 구하여 해당 범위만 출력 map 의 값을 입력받으며, 섬 'X' 인 부분은 큐에 삽입 큐가 빌 때까지, 사방 탐색을 하며 3~4면이 바다인 부분을 '-' 로 변경 ( 50 년 후에 사라지는 섬 ) 가라앉은 섬도 바다로 변경하며 ('-'→'.') , 남아있는 섬의 행/열 범위 구하기 해당 행 / 열 내의 범위만 출력 + 신경써야 할 부분 1. 해당 map 의 범위가 벗어났을 경우, 모두 바다로 간주 ( 문제..

7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net [ 알고리즘 ] ( Set + List 정렬 ) : 회사에 동명이인이 없고, 출력 전에는 순서가 중요하지 않기 때문에 Set 을 사용하였다. Set 에 남아있는 이름을 List에 옮긴 후, 정렬하여 역순으로 출력한다. 명령 ( 'enter' , 'leave' ) 에 따라, set에 add 혹은, remove 한다. 모든 명령 종료 후, set 의 iterator 을 활용하여 list 에 담는다. Collections.sor..

20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net [ 알고리즘 ] ( 완전 탐색 + 조합 ) : N명의 학생 중, 3명의 학생을 뽑아 심리적 거리 계산하며 최솟값 갱신 N명의 학생 중 3명 조합 boolean[] combi = new boolean[N] : 3명 조합에 포함 여부 체크 , [조합에 포함] = true List list = new ArrayList() : 3명의 Mbti 리스트 ex) { ISFJ , ISTP, ESTP } 3명의 mbti 간 심리적 거리 계산 int getCount(List list) : 해당 list 를 가지고, 3명의 mbti간 심리적 거리 계산 후 반환 charAt 을 ..

3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net [ 알고리즘 ] 2차원 배열에서 사과의 위치를 1로 두고, 뱀이 지나가는 곳을 리스트에 넣었다. 꼬리를 자를 때는 list.remove(0) 으로 가장 앞에 있는것 = 꼬리 를 삭제하였다. 탐색을 통해) - 벽에 부딪혔거나, 리스트에 있는값 ( 뱀 ) 이 나오면 게임 종료시키기 - 사과 ( =1 ) 이 나오면, 사과 없애기 > 다시 0으로 값 바꾸기 - 아무 것도 없다면, 꼬리 자르기 > list.remove(0) time ++ 으로 시간을 증가시키며, 만약 입력으로 ..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [ 알고리즘 ] dp 로 구현하였다. dp[] : 각 날짜에 완료 된 일들 중 벌 수 있는 최댓 값 일이 완료되는 날을 기준으로 dp 를 구현했기 때문에, 각 n일 째에 끝나는 일들을 list 리스트로 저장하였다. ex) list[3] = 3일에 완료되는 일 { 1 , 3 } ( 1번 - 3일걸려서 3일날 완료 / 3번 - 1일 걸려서 3일날 완료 ) dp 에는, 각 날짜별로 완료된 일이 있을 때, (현재까지의 최댓 값, 완료된 일 포함한 최댓값) 중 최댓값을 구하였다. [ 코드 ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ..

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [ 알고리즘 ] N/2명으로 이루어진 스타트 팀과 링크팀으로 나누기 : 조합 N 크기를 가진 boolean 형 배열을 두고, 스타트 팀에 속하는 번호는 True로 값을 주었다. 즉, 스타트 팀= true , 링크 팀 = false 로 생각하면 편하다. ( count = 스타트 팀 인원 수, i= 현재 인덱스 ) 스타트 팀에 포함 시킬 번호는 true 로 치환한 후, 재귀 호출 단, 조합에서 ( 1,2 ) 와 ( 2,1 ) 은 같은 것으로 취급하기 때문에 인덱스를 방금 호출한 다음 번호..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net [ 알고리즘 ] ' Z ' 모양에 대해서, 주어진 2차원 배열을 1 ~ 4분면으로 나누면 된다. 배열의 크기를 이용하여, size/2 로 줄여가면서 재귀를 반복한다 . ( 재귀 ) size = size/ 2 로 하고, 1사분면 : size > r 이고, size > c 2사분면 : size > r 이고, size c ▶ 1, 2 분면 크기 더하기 4사분면 : size < r ..