본문 바로가기
반응형

Algorithm73

[알고리즘] 접두사합(prefix sum) 알고리즘 by javascript (ft. 부분합/구간합) Prefix Sum(접두사 합) 부분합, 누적합, 구간합 등으로 불리며 해당 합을 빠르게 구하는 알고리즘이다. 사실 알고리즘 치고는 매우 간단하다. 이 알고리즘의 원리는 다음과 같다. 각각의 숫자까지의 합을 미리 계산하여 저장해놓고 그 저장한 값을 활용하여 구간합을 구한다. 사실 접두사합, 구간합, 부분합 알고리즘을 검색하면 많은 블로그가 나올 텐데, 기본적으로 접두사 합 알고리즘의 공식을 다음과 같이 설명하고 있다. P[Right] - P[Left - 1] 크게 틀린 공식은 아니니 일단 이런 식으로 사용하는구나 정도는 알고 진행하면 좋다. 다른 알고리즘도 마찬가지겠지만 문제에 따라 정해진 공식을 사용할 수 없는 경우가 많다. 예를 들어 숫자 [100, 101, 102, 103, 104]가 주어졌다고 가.. 2022. 10. 12.
[HackerRank] The Bomberman Game (Medium) by javascript ▷ 문제 : The Bomberman Game (Medium) The Bomberman Game | HackerRank Determine the effect of Bomberman's rampage. www.hackerrank.com ▷ 해결 날짜 : 2022.08.04 ▷ 소요 시간 : 1시간 20분 ▷ 풀이 과정 : 일단 문제를 보는 순간 풀기 싫게 거부감이 느껴지는 문제이다. 문제의 큰 흐름은 아래와 같다. 초기에 일부 세포에 임의로 폭탄 설치 (0) ( 폭탄이 설치된 상태로 배열이 주어짐 ) 1초 후 침묵 (+1) 1초 후 폭탄이 없는 모든 곳에 폭탄 설치(+1) 1초 후 정확히 3초 전에 설치한 폭탄이 폭발 여기서 인접한 상하좌우 같이 터짐(+1) 계속 3~4 무한 반복 그리고 답안은 몇 초 후.. 2022. 8. 4.
[HackerRank] Organizing Containers of Balls (Medium) by javascript ▷ 문제 : Organizing Containers of Balls (Medium) Organizing Containers of Balls | HackerRank Determine if David can perform some sequence of swap operations such that each container holds one distinct type of ball. www.hackerrank.com ▷ 해결 날짜 : 2022.08.03 ▷ 소요 시간 : 1시간 20분 ▷ 풀이 과정 : 일단 문제가 참 긴데, 쉽게 설명하자면 컨테이너가 담긴 배열이 주어지고, 각 컨테이너별로 서로 다른 타입의 공들이 들어가 있는데, 이 공들을 같은 타입끼리 각 컨테이너에 넣을 수 있냐 없냐를 구하는 문제이다. .. 2022. 8. 3.
[HackerRank] Encryption (Medium) by javascript ▷ 문제 : Encryption (Medium) Encryption | HackerRank Encrypt a string by arranging the characters of a string into a matrix and printing the resulting matrix column wise. www.hackerrank.com ▷ 해결 날짜 : 2022.08.03 ▷ 소요 시간 : 30분 ▷ 풀이 과정 : 문제를 요약하자면 다음과 같다. 'haveaniceday' 라는 문자열이 입력되었다면, 이 문자열의 길이는 12 그리고 암호화를 위해 길이의 제곱근을 구하고 그 제곱근은 3과 4 사이의 값을 가진다. 그럴 경우 ['have', 'anic', 'eday'] 이런식으로 배열의 길이가 3이며, 각 인.. 2022. 8. 3.
[HackerRank] The Hurdle Race (Easy) by javascript ▷ 문제 : The Hurdle Race (Easy) The Hurdle Race | HackerRank Determine the maximum value in an array less a value, limit >= 0. www.hackerrank.com ▷ 해결 날짜 : 2022.08.03 ▷ 소요 시간 : 10분 ▷ 풀이 과정 : 허들 게임을 하는데, 현재 점프력에서 얼마나 많은 포션을 더 먹어야 모든 장애물을 통과할 수 있는지 즉, 먹은 포션의 개수를 출력하는 문제이다. 입력으로 현재 점프력과, 장애물이 들어있는 배열이 주어지는데, 풀이는 정말 간단하다. 장애물 최댓값 - 현재 점프력만 해주면 된다. 단. 포션없이 이미 통과가 가능한 상태면 0을 출력한다. ▷ 구현 function hurdleRa.. 2022. 8. 3.
[프로그래머스] 피로도 (LV.2) by javascript - 완전탐색 ▷ 문제 : 완전탐색 - 피로도 LV.2 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ▷ 해결 날짜 : 2022.08.02 ▷ 소요 시간 : 40분 ▷ 풀이 과정 : 완전탐색 카테고리에 있는 문제이다. "총 피로도(k)", "던전의 정보(dungeons) - 최소 필요 피로도, 소모 피로도"가 입력으로 주어지며, 최대로 돌 수 있는 던전의 개수를 구해주면 되는 문제이다. 단순히 이중 포문 같은 완전 탐색으로는 해결이 불가능한 문제이며, 경우의 수가 필요하다 싶어 "순열"을 이용해 문제를 해결하였다. 아마 제한사항에서 배열의 길이가 길면 길어질수록 이 해.. 2022. 8. 2.
[백준] 14503번 : 로봇 청소기 (골드Ⅴ) by node.js ▷ 문제 : 14503번 - 로봇 청소기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net ▷ 해결 날짜 : 2022.07.27 ▷ 소요 시간 : 1시간 30분 ▷ 풀이 과정 : 문제는 아래에서 제시하는 조건만 숙지하여 풀면 되는 문제이다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2.. 2022. 7. 27.
[백준] 2573번 : 빙산 (골드Ⅳ) by node.js ▷ 문제 : 2573번 - 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net ▷ 해결 날짜 : 2022.07.26 ▷ 소요 시간 : 1시간 30분 ▷ 풀이 과정 : 문제를 요약하자면 지구 온난화로 빙산이 녹는데 빙산이 최초로 두 덩어리로 분리되는 데 걸리는 시간(년)을 구하는 문제이다. 문제가 얼핏보면 쉬워 보이지만, 몇 개 중요하게 체크하고 가야 할 점과 구현할 때 주의해야 할 점이 있다. 1년식 증가하며 매년 빙산이 녹는데, 각 빙산의 높이는 동서남북 방향으로 붙어있는 0이 저장된 칸의 개수만 큼.. 2022. 7. 26.
[백준] 2206번 : 벽 부수고 이동하기 (골드 Ⅳ) by node.js ▷ 문제 : 2206번 - 벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net ▷ 해결 날짜 : 2022.07.22 ▷ 소요 시간 : 3시간 ▷ 풀이 과정 : 이 문제는 내가 현재 풀 수 없는 문제이다. 타 회사의 코테 문제로 나왔던 비슷한 유형의 문제인데, 최단거리를 구하는 문제이며 벽을 "한 번" 부술 수 있다. BFS의 응용인 것은 알겠는데, 도저히 접근하는 방법이 떠오르지 않아 혼자서는 풀 수 없었다. 일단 구글링의 도움을 받아 해결을 하였는데, 기본 틀은 일반.. 2022. 7. 22.
반응형
TOP