본문 바로가기

알고리즘72

Programmers - 문자열 압축(Java) https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 같은 값이 연속해서 나타나는 경우 반복되는 갯수를 표기하며 줄여서 표기 ex) aaa -> 3a * 단, 정해진 길이가 반복되는 경우만 압축가능 ex) aabbb -> 2a3b(X) -> 2a2bb(O) * 완전 탐색으로 가장 작은 길이의 결과를 구하되, 탐색의 범위를 줄이는 것이 필요 주어지는 문자열의 길이를 이용하여 최대 압축 길이를 구함, 이 .. 2021. 12. 16.
BOJ 16234 - 인구 이동(Java) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 인구이동이 더 이상 불가능 할때 까지 계속해서 이동 반복 이동되는 구역을 visit[][]로 확인, 다시 탐색하지 않도록 예외 처리 - 인구 이동이 가능한지 확인 - 인구 이동이 가능하다면 해당 구역 전체 인구 이동 - bfs를 이용하여 인근 구역 탐색 -> L < abs( map[y][x]-map[ny][nx] ) < R이라면 이동 가능 - 인구이동 구역 설정까지 bfs 탐색.. 2021. 12. 14.
BOJ 11000 - 강의실 배정(Java) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 현재 탐색 요소의 강의 시작시간 -> 같은 강의실로 할당 불가능, 새로운 강의실 필요 import java.io.*; import java.util.*; public class Main { static.. 2021. 12. 7.
Programmers - 카카오프렌즈 컬러링북(JAVA) https://programmers.co.kr/learn/courses/30/lessons/1829?language=java 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이 * 0은 색칠하지 않은 영역, 영역 탐색 대상에서 제외 1. 이차원 배열 각 요소마다 탐색 - 이미 탐색했거나(visit[y][x]==true) 해당 위치의 값이 0이면 continue - 외의 경우에는 현재 위치가 이전까지 찾은 영역과 다른 새로운 영역이기 때문에 영역 갯수+1, 영역 사이즈 구하기(2로 이동) 2. 상하좌우 인접한 .. 2021. 12. 3.
BOJ 23290 - 마법사 상어와 복제(C++) https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 한 위치에 물고기가 여러 마리일 수 도 있기 떄문에 vector fish[][]로 저장, 값은 물고기의 방향성 상어가 물고기를 먹었다면 냄새를 남기는 이차원 배열 smell[][]을 이용 smell[y][x]= 현재 연습 시점의 index을 남기고, 물고기가 이동할 때 이동 가능한지의 여부를 확인 할때, 현재 연습 시점 index - smell[y][x] 가.. 2021. 11. 27.
BOJ 23288 - 주사위 굴리기2(C++) https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이 주사위 배열에 주사위 위치의 값 저장, 주사위 이동 시 배열 갱신 이동방향 dir[]={동, 남, 서, 북} 반복횟수 K만큼 진행 1. 주사위가 이동 방향으로 한칸 굴러감(굴러간 위치가 범위 밖이라면 반대방향으로 계산) - 주사위의 이동방향에 따라 주사위 배열의 값 수정 2. 주사위의 위치 (y, x)에 대해 점수 계산 - 동서남북 방향으로 연속해서 이동할 수 있는(BFS).. 2021. 11. 25.
Programmers - 보호소에서 중성화한 동물(SQL) https://programmers.co.kr/learn/courses/30/lessons/59045 코딩테스트 연습 - 보호소에서 중성화한 동물 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 풀이 보호소에 들어올 때에는 중성화되지 않았지만, 보호소에서 나갈 당시에는 중성화된 동물을 조회 중성화를 하지 않았다면 SEX_UPON_~의 값이 "Intack Male/Female" 했다면 SEX_UPIN_~의 값이 "Sprayes Female.. 2021. 11. 4.
Programmers - 오랜 기간 보호한 동물(1)(SQL) https://programmers.co.kr/learn/courses/30/lessons/59044 코딩테스트 연습 - 오랜 기간 보호한 동물(1) ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 풀이 입양을 가지 못한 동물중 보호시작일이 가장 작은(오래된) 동물 3마리에 대해 조회 JOIN을 이용해 ANIMAL_ID를 기준으로 ANIMAL_INS, ANIMAL_OUTS를 합침 ANIMAL_OUTS.ANIMAL_ID가 null인 칼럼을.. 2021. 11. 4.
Programmers - 있었는데요 없었습니다(SQL) https://programmers.co.kr/learn/courses/30/lessons/59043 코딩테스트 연습 - 있었는데요 없었습니다 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 풀이 입양일이 보호 시작일 보다 빠른 동물을 조회 WHERE ANIMAL_INS.DATETIME > ANIMAL_OUTS.DATETIME # JOIN 사용 SELECT i.ANIMAL_ID, i.NAME FROM ANIMAL_INS i LEFT JO.. 2021. 11. 4.

티스토리툴바