알고리즘

알고리즘의 중요성을 얼마나 알고 있는가?위와 같은 질문을 이직 준비 이전에 받았다면 잘 모르겠다고 말했을 것이다. 알고리즘이라는 단어를 처음 들었던 것은 고등학교 시절 로봇 동아리 활동을 하며 들었었다. 당시 나는 로봇을 통해 주어진 과제를 수행할 때 필요한 것이 알고

사이트: HackerRank 난이도: 미디움 문제 개요

사이트: HackerRank난이도: 미디움string array가 주어지면 같이 주어진 패턴이 존재하는지 확인하는 문제이다.오늘은 무난하게 잘 풀리는 것 같다 ㅎㅎ그리드 P를 순회하는 재귀함수를 하나 정의해 놓고 패턴을 비교할 수 있을 만큼만 G를 순회하도록 작성했다.

사이트: HackerRank난이도: 미디움주어진 자연수 상한선까지 일정한 차이(|posi - i| = k)를 만들어주는 사전적으로 최소단위의 순열을 반환하는 문제이다.최소 단위의 순열을 구하기 위해서는 먼저 작은 수부터 넣을 필요가 있다. 조건에 맞을 경우 반환할 순열

사이트: HackerRank난이도: 미디움bomberman은 아래 규칙대로 움직인다.1\. 초기 위치에 폭탄을 심는다.2\. 1 초 후는 동작하지 않는다.3\. 그 다음 1 초 후는 빈 곳 모든 cell에 폭탄을 심는다.4\. 그 다음 1 초 후는 3초 전 심었던 폭탄

사이트: HackerRank난이도: 미디움분류: Dynamic programming어떤 숫자 n(number)과 교환가능한 코인들 c(number-array)가 주어졌을 때, n으로 교환 가능한 코인들의 경우의 수를 반환하라.동적 프로그래밍 문제이다. 우선 작은 문제들

사이트: HackerRank난이도: 미디움분류: Dynamic programming주어진 배열의 원소 값들이 모두 동일한 값이 되기 위한 최소값을 반환하는 문제이다.해당 문제는 아래 조건을 가지고 있다.1명을 제외하고 초콜릿을 나눠줄 수 있다.한번에 나눠줄 수 있는 초

사이트: HackerRank 난이도: 미디움 분류: Dynamic programming 문제 1. 나의 풀이 어려웠던 점 2. 다른사람의 풀이 결론

사이트: HackerRank난이도: 미디움분류: Greedy배열과 정수 k가 주어지면 k 길이의 파생 배열 안에서 min, max 값의 차이가 최소인 값을 찾아서 반환하라.우선 주어진 배열을 정렬을 한다. 그러고 인덱스 0번째부터 마지막 인덱스 - k 까지 배열을 순회

사이트: HackerRank난이도: 미디움분류: Greedy배열과 정수 k가 주어지면 k 길이의 파생 배열 안에서 min, max 값의 차이가 최소인 값을 찾아서 반환하라.해당 문제를 풀다가 집중력이 너무 떨어져 시간이 오래 걸린다고 판단하여, 다른 사람의 풀이를 참조

사이트: HackerRank난이도: 미디움순차적으로 정렬될 수 있는 배열 A가 주어졌을 때, 정해진 수의 원소들을 rotate하여 정렬가능한지 판단한 후 YES or NO를 반환하라. 이 때 rotate 가능한 원소의 개수는 3개이다.문제에서 주어진 변수의 범위가 아래

사이트: HackerRank난이도: 미디움배열이 주어졌을 때 해당 배열의 상태에 따라 아래와 같이 출력한다.이미 정렬된 경우두 요소의 순서만 뒤바뀐 경우정렬되지 않은 요소들의 범위를 뒤집으면 올바르게 정렬될 경우모두 해당 하지 않을 경우여기서의 순서는 인덱스 + 1 값

사이트: HackerRank난이도: 미디움일자에 따른 지출 된 값의 배열이 주어지고 지정된 일자가 지난 후, 다음날 지출 금액이 지정된 일자동안 지출한 금액의 중앙값 \* 2 보다 클 경우 보안 경고 알람을 사용자에게 보낸다. 문제에서는 보안 경고 알람이 몇번 울렸는지

사이트: HackerRank난이도: 미디움정수와 연관된 문자열 배열이 주어졌을 때 계수정렬(counting sort) 하고 하나의 문자열로 출력하라. 이 때 배열의 전반부에 해당되는 요소들은 -로 대체한다.위 배열이 주어졌을 때 아래와 같이 출력한다.문제 자체에서 계수

사이트: HackerRank난이도: 미디움분류: Sorting배열이 주어졌을 때 인접한 요소의 차이가 최소가 되는 형태로 만드려면 swap을 몇번 해야 하는지 반환하는 문제이다. 인접한 요소의 차이가 최소가 되어야 한다는 말로 보아 정렬로 해결해야 하는문제라고 볼 수

사이트: HackerRank난이도: 미디움분류: String주어진 문자열이 유효한지 확인하는 문제이다. 각 문자 하나를 제거하거나 더할 때, 문자열 내 모든 문자의 개수가 동일할 경우 유효하고 그렇지 않다면 유효하지 않은 문자열이다.위 문자열은 c를 하나 추가하면 되기

사이트: HackerRank 난이도: 미디움 분류: String 문제 정수형 문자열과 최대 변경 횟수가 주어졌을 때, 각 자리수를 변경하여 회문으로 만들어라. 회문으로 변경하는 경우의 수가 2가지 이상일 경우 가장 큰 값을 반환하라. > 회문이란 거꾸로 뒤집어도 동

사이트: HackerRank난이도: 미디움분류: String어느 문자열과 특정 구간값이 주어졌을 때 해당 구간안에 존재하는 가장 긴 길이의 palindromes(회문)의 개수를 반환해라.어찌저찌 initialize 함수에서 구간 합을 구해야 하고, 해당 구간합을 이용해

사이트: HackerRank난이도: 미디움분류: String두 개의 문자열이 주어졌을 때 공통된 문자열이 동일한 패턴으로 존재하는 경우 가장 큰 길이를 가지는 패턴의 길이를 반환하라위 두 개의 문자열 중 동일한 패턴을 가진 문자를 표시해보면 아래처럼 존재하는 것을 알

사이트: HackerRank난이도: 미디움분류: String주어진 곰의 유전자 문자열에 존재하는 문자의 개수가 n/4가 될 수 있도록 하는 최소 변경 횟수를 반환하라. 유전자 문자열에 존재하는 문자는 A, C, T, G 이다.문제가 이해되지 않아 바로 풀이방법을 찾아보

사이트: HackerRank난이도: 미디움분류: Searchhackerland의 마을 지도와 송신기의 범위가 주어졌을 때, 전체 마을을 커버할 수 있는 최소 송신기 설치 개수를 반환하라.단순히 인덱스를 늘려가면 타임아웃에 걸릴거라고 생각한 나머지 복잡한 연산들을 계산하

사이트: HackerRank난이도: 미디움분류: Search그리드 상에 존재하는 기차 트랙 정보가 주어졌을 때, 기차트랙을 제외한 영역에 가로등을 설치하려고 한다. 이 때 설치할 수 있는 가로등의 개수를 반환하라.해당 문제를 풀다가 타임아웃 해결을 도저히 못하겠다는 생

사이트: HackerRank난이도: 미디움분류: Search직각 형태로 움직일 수 있는 체스말 knight를 이용하여 n x n 크기의 체스판에서 (0,0)에서 (n-1, n-1)까지 이동하는 최단경로를 찾아서 반환하라.예를 들어, n=5일 때 이동할 수 있는 경우의

사이트: HackerRank난이도: 미디움분류: SearchLauren은 향후 몇년간의 부동산 가격 예측 차트를 가지고 있다. 그녀는 1년 안에 집을 사고 이후 연도에 팔아서 손실을 최소화 해야 하는데, 이 때 최소 손실액을 반환하라.처음 문제를 접했을 때 투 포인터로

사이트: HackerRank난이도: 미디움분류: Search임의의 정수 배열과 타겟 값(정수)이 주어졌을 때, 배열 안 두 요소의 차가 타겟 값과 같은 경우의 수를 반환하라.어렵지 않은 문제이다. set을 사용하여 적절히 기록하고 다시 루프를 돌면서 pair가 되는 숫

사이트: HackerRank난이도: 미디움분류: Search어떤 행렬의 요소가 되는 값이 0과 1일 때, 1의 값을 가지는 셀이 연결된 영역의 최대 넓이를 구해라.여기서 연결되어 있다고 하는 것은 해당 셀 주변으로 1칸씩 인접해 있다는 말이다. 즉, 값이 1인 셀(A)

사이트: HackerRank난이도: 미디움분류: Search주어진 문자열에서 4개의 문자를 뽑아 회문을 만든다고 했을 때, 나오는 경우의 수를 반환하라.이 때, 각 문자 a, b, c, d의 인덱스 순서는 0 <= a < b < c < d <

사이트: HackerRank난이도: 미디움분류: Search금지된 숲에 갇힌 론과 헤르미온느는 포트키를 찾아 숲을 빠져나가려고 한다. 헤르미온느는 지팡이를 사용하여 갈림길의 방향을 찾을 수 있는데, 론은 헤르미온느가 몇 번의 마법으로 포트키를 찾을 수 있을지 내기를 한

사이트: HackerRank난이도: 미디움분류: Search각 노드마다 값이 존재하는 트리가 주어질 때, 해당 트리의 값은 전체 노드 값들의 합이 된다. 이 때 특정 간선을 잘라 2개의 트리를 만들었을 때, 각 트리의 값의 차이가 가장 적은 값을 반환하라.해당 문제는

사이트: HackerRank난이도: 미디움분류: Search일반적인 체스의 나이트는 두칸 수직, 수평이동 하고 옆 또는 위아래로 한 칸씩 움직이는 이동경로를 보여준다. 이 나이트의 움직임을 커스터마이징하여 Red Knight라는 유닛을 하나 만들었고, 해당 유닛의 이동

사이트: HackerRank난이도: 미디움분류: Graph Theory시민들이 도서관을 이용할 수 있기 위해 각 마을에 도서관을 지으려고 한다. 연결된 도로가 있다면 시민들은 옆 마을로 이동하여 도서관을 이용할 수 있다. 아직 각 마을들은 도서관이 지어지지 않았고, 길

사이트: HackerRank난이도: 미디움분류: Graph Theory같은 국적을 가진 우주비행사 정보가 쌍으로 주어질 때, 다른 국적을 가진 2명의 비행사를 선발할 수 있는 경우의 수를 반환하라.해당 문제는 graph 내에 존재하는 컴포넌트들의 요소개수들의 조합 개수

사이트: HackerRank난이도: 미디움분류: Graph Theory각 간선의 가중치가 6인 무방향 그래프가 있고 첫 시작점이 주어졌을 때, 각 노드 간의 최단 거리의 가중치를 계산하여 반환하라. 연결되지 않았을 때는 -1을 반환하도록 한다.bfs 알고리즘만 잘 알고

사이트: HackerRank난이도: 미디움분류: Graph Theory각 간선과 가중치가 주어졌을 때 모든 노드들을 연결하여 최소 가중치를 가지는 값을 반환하라.해당 문제는 최소신장 트리의 kruscal algorithm을 사용하여 해결하는 문제이다. kruscal a

분류: Permutation정수 배열이 주어졌을 때, 해당 배열의 순열을 구해서 반환하라재귀로 푸는 방식이 있고, 그냥 loop를 돌면서 푸는 방식(Heap method)이 있다. javascript 특성 상 재귀보단 loop를 돌면서 구하는게 맞을거 같다라는 생각이

사이트: HackerRank난이도: 미디움분류: Graph Theorycycle이 없는 연결 그래프가 주어 졌을 때, 특정 간선을 잘라서 서브트리를 만든다. 이 때 서브트리 노드의 개수가 모두 짝수인 최대 간선 제거수를 반환하라.아무래도 또 단어 하나에 묶여서 Tree

사이트: HackerRank난이도: 미디움분류: Graph TheorySnakes and Ladders 게임에서 주사위를 가장 적게 굴려서 도착지점에 도달할 수 있는 횟수를 반환하라.Snakes and Ladders 게임은 보드 판위에 사다리와 뱀이 놓여져 있는 상태에

사이트: HackerRank난이도: 미디움분류: Graph Theory방향이 없는 간선 정보가 주어지고 특정 노트가 root가 되었을 때, 부모-자식을 예측하려고 한다. 주어진 예측 정보를 가지고 특정 노트가 root가 되었을 때 얼마나 맞는지 그 확률을 찾아서 반환하

알고리즘 문제를 풀다가 javascript로 최대 공약수와 최대 공배수를 구할 일이 종종 생길 것 같아서 정리할 필요를 느꼈다.일단 간단하게 설명부터 하고 넘어가겠다.최대 공약수: 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다.최소 공배수: 두 수, 혹은 그 이

사이트: HackerRank난이도: 미디움분류: Dynamic programming정수형 문자열이 주어질 때, 각 하위 문자열들의 합을 구해서 반환하라dp 문제는 유형을 다양하게 접하기 위해 고민 시간을 짧게 가지려 한다. 대략적으로 생각했을 때 머리속에 떠오른 아이디

알고리즘 문제를 풀다가 계수정렬(counting sort)의 개념을 잘 몰라서 공부할 겸 정리 해 보았다.계수정렬은 숫자들 간 비교를 하지 않고 정렬을 하는 알고리즘이다. 숫자를 비교하지 않고 각 숫자들의 개수만 세고 정렬을 진행하기 때문에 시간복잡도는 O(n)이 나온

사이트: HackerRank난이도: 미디움분류: Dynamic programming기존 피보나치 수열을 변환하여 새로 만든 규칙을 적용하려고 한다. 새로 만든 피보나치 규칙은 다음과 같다.아래 예시를 한번 살펴보자.BigInt를 사용할 수 없는 환경이라서 일단 BigI

사이트: HackerRank난이도: 미디움분류: Dynamic programming어떤 문자열 a와 b가 주어졌을 때, a를 변환하여 b로 변경할 수 있으면 YES를 반환하고 변환할 수 없으면 NO를 반환해라.a의 문자중 소문자는 생략하거나 대문자로 변환할 수 있다.늘

사이트: HackerRank난이도: 미디움분류: Dynamic programming정수로 이루어진 배열이 주어질 때, 해당 배열의 subarray가 가진 원소들의 합이 최대인 값과, subsequence가 가진 원소들의 합이 최대인 값을 찾아서 반환하라.시간복잡도의 제

사이트: Programmers난이도: lv3greedy 알고리즘으로 풀려고 했는데, 아무래도 그렇게 하면 안되겠다는 생각이 들었다. 최적화된 이동 경로로 풀어야 되는데, greedy를 사용할 경우 최적화 되지 않는 경로가 존재해서 테스트케이스 통과를 하지 못했다.예를

사이트: HackerRank난이도: 미디움분류: Graph TheoryN개의 정점과 M개의 간선이 포함된 그래프가 주어졌을 때, 각 간선 M\[i]에는 패널티(비용)가 부여된다. 어떤 정점 A와 B를 지나가는 경로 중 가장 적은 비용을 반환하라.패널티는 각 간선의 비용

사이트: HackerRank난이도: 미디움분류: Graph Theory무방향 가중치 그래프가 주어지고 노드 n개가 주어질 때, 1번 노드에서 n번 노드까지의 거리중 가장 적은 비용이 드는 값을 찾아서 반환하라.각 노드간 가중치가 존재하며 다음 노드로 이동시 가중치 값을

사이트: HackerRank난이도: 미디움분류: Graph Theory우편 배달부 Jeanie는 Byteland N개의 도시에 우편을 배달해야 한다. 각 도시는 반드시 다른 도시로 이어지는 경로가 존재할 때, Jeanie가 모든 우편을 배달할 수 있는 가장 작은 거리

사이트: HackerRank난이도: 미디움분류: Graph Theory무방향 그래프가 주어질 때, 각 정점 간의 최소 거리 값을 계산해서 이진수로 변환하라. 이 때 주어진 간선 정보는 \[정점1, 정점2, 2의 지수] 값이 주어진다.다익스트라 알고리즘으로 해결하려 했지