kwang2134 님의 블로그

[백준] 벌집접근DFS규칙 찾기풀이백준 사이트에서도 문제를 풀기 시작했다. 백준에서는 천천히 solved.ac의 클래스 추천에 뜨는 문제들부터 차근차근 푸는 중이다. 아직 브론즈 1 티어로 주로 쉬운 문제들이라 빨리빨리 넘어가던 중 흠칫하게 만든 문제가 있어 들고 왔다. 문제를 처음 봤을 땐 프로그래머스에서 삼각 달팽이?라는 이름의 문제가 있었는데 그 문제가 떠올랐다. 2차원 배열을 이용해 숫자를 채우는 그런 문제였는데 이 문제도 그런 방식으로 숫자를 채워두고 DFS 같은 걸로 구해야 하나 생각했다. 하지만 이 문제의 조건인 N의 입력 범위가 1,000,000,000까지로 배열에 단순 숫자 채우기도 시간 초과가 날 숫자이고 무엇보다 브론즈 티어의 문제라 단순한 방법이 있을 거라 생각했다. 정말 그림이 알..

[Programmers] PCCP 모의고사 #2 체육대회접근DFS재귀 함수백트래킹풀이학생의 수가 최대 10명이길래 처음엔 DFS를 이용해 구현해보려 했다. 정답은 맞혔지만 학생수가 10명 밖에 되지 않는데도 불구하고 효율이 매우 좋지 않았다. 아마 BFS를 사용했다면 시간초과가 났을 것이다.private static class State { private final int step; private final int abilitySum; private final boolean[] checkAbility; private final boolean[] checkStudent; public State(int step, int abilitySum, boolean[] checkAbility, boolean[] che..

[Programmers] PCCP 모의고사 #1 외톨이 알파벳접근중복 제거정규식replaceAllMap풀이같은 알파벳이 문자열 내에 두 개 이상 떨어져 존재한다면 외톨이 알파벳이다. 연속된 덩어리 알파벳은 외톨이가 아니다. 즉 문자열 내에 존재하는 알파벳들을 2개 이상 중복되는 부분을 모두 한 개로 치환한 다음. 각 알파벳의 등장 횟수를 계산해 2회 이상 등장했다면 외톨이 알파벳이 되는 것이다.String makeOne = input_string.replaceAll("(.)\\1+", "$1");정규식을 사용해 치환하는 이 코드 한 줄로 문제의 80퍼센트는 이미 해결되었다. 정규식에 대해 설명해 보자면 (.)은 임의의 문자를 뜻한다. 입력받는 문자는 알파벳 소문자로 제한된다는 사항이 있기 때문에 굳이 알..

[Programmers] 디스크 컨트롤러접근우선순위 큐풀이문제의 내용은 비선점 스케줄링인 SJF, Shortest Job First 기법과 일치하다. 비선점으로 수행하던 작업이 끝날 때까지 대기하고 끝나고 나면 해당 시점에 대기 중인 프로세스 중 가장 수행 시간이 짧은 프로세스를 먼저 실행하는 기법이다. 선점 스케줄링 기법인 SRF, Shortest Remaining Time First 기법과는 다르게 수행 중인 프로세스를 건들지 않기에 더 간단하게 구현을 할 수 있을 것이다.Arrays.sort(jobs, (a, b) -> a[0] - b[0]);우선 입력받는 jobs를 작업 요청 시간 기준으로 정렬해 주었다.PriorityQueue pq = new PriorityQueue((a, b) -> a[1] ..

[Goorm] 현대모비스 예선 주차시스템접근BFS풀이자바스크립트로 코딩테스트를 쳐야 하기에 자바스크립트 공부를 시작했다. 문법이 익숙하지 않아 자바로 하는 것처럼 완성한 후 GPT의 도움을 받아 자바스크립트 스타일로 가공(?)을 받았다. 2차원 좌표가 주어지고 칸들을 순회하며 값을 구해야 하기에 BFS를 이용해 탐색을 시도했다.let N = 0;let M = 0;let parking = [];for await (const line of rl) { let str = line.split(" ").map(Number); if (str.length === 2) { N = str[0]; M = str[1]; } else { parking.push(str); } // 입력이 끝나면 처리 if ..

[Programmers] 코딩테스트 광물 캐기접근DFS백트래킹풀이광물은 순차적으로 접근해야 하고 현재 단계의 광물만 고려하는 것이 아닌 뒤에 있는 광물도 고려해야 하는 문제이기 때문에 모든 결과를 구하기 위해 DFS를 먼저 생각했다. 우선 시간 복잡도를 확인하기 위해 대략적으로 계산을 해봤다.minerals의 길이: 최대 50각 곡괭이의 최대 개수: 5곡괭이 종류: 3가지 (다이아몬드, 철, 돌)문제의 구성 요소로 minerals의 최대 인덱스는 50 각 곡괭이의 남은 개수는 0~5개로 총 6 그리고 곡괭이의 종류 3 각 곡괭이의 최대 상태 수는 곡괭이 종류 3 x 곡괭이 개수 6 = 216 216 x 50 = 33048 총 33048의 최대 반복수를 가진다. 제한 시간 안에 충분히 통과 가능한 횟수이기..

[Goorm[ 구름 먼데이 챌린지 거리두기접근BFS를 이용해 모든 경우의 수하나의 수식으로 완성동적 프로그래밍풀이사실 문제를 풀기 전 동적 프로그래밍 유형의 문제인 걸 알고 들어갔지만 다른 방법으로도 해결이 가능할까 생각해 봤다. BFS를 사용하게 된다면 N의 범위가 너무 커 시간 초과가 날게 분명했다. 하나의 수식으로 완성을 해보려 했지만 불가능했다. 문제를 보면 1줄의 테이블로 만들 수 있는 경우의 수는 5가지로 0을 테이블 #을 스티커라 표현했을 경우 000 #00 0#0 00# #0# 왼쪽에서부터 스티커가 한 장도 없는 경우 각각 한자리마다 한 장씩 붙어있는 경우 그리고 가운데를 비우고 양 끝에 붙은 경우가 있다. 이제 한 줄의 경우의 수 5가지를 통해 Bottom-up 방식으로 값을 채워 나가면..