ALGORITHMS - PRACTICE

프로젝트를 몇개 하다보니 이제는 좀 더 코드의 퀄리티를 높이기 위해 알고리즘과 자료구조를 공부하기로 했다. 필수라는 사람도 있고 아니라는 사람도 있지만 , 난 개인적으로 어설프게 하는건 싫어하기에 , 그리고 이왕하는거 뭐든지 제대로 해야한다고 생각하기에 공부하기로 한것

역시나 세상은 넓다. 정말 깔끔하게 글을 적으신 분이 계셨고 그걸 보고 또 많이 배웠다.2명을 선정했는데 첫번째는 코드를 이해하느라고 좀 애먹었다. 그런 측면에서 난 두번째 답안이 더 좋은 코드라고 생각한다. 내가 아직 실력이 부족한것일지도 모르겠지만 ㅎㅎ다만 위의 솔

id가 들어오면 그 아이디를 여러 단계의 조건들을 통과하면서 다듬는 작업이다. 그 단계들은 이러하다.1\. new_id의 모든 대문자를 대응되는 소문자로 치환합니다.파일들 (css/js)을 받아온다.2\. newid에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(\_),

이번에는 단어들을 저장하는 기능, 불러오는 기능, 있는지 확인하는 기능, 그리고 자동완성 기능까지 구현해보려고 한다.Tree의 형태로 단어들을 저장할거다. 근데 이 방법은 내가 하나하나 다 구현한건 아니고 이미 있던 것을 보고 내가 이해해서 스스로 연습해보고 정리한것이

격자판이 주어지면 가로로 더한 값 세로로 더한값 대각선으로 더한 값중에 최대값을 찾는 문제이다. 루프를 도는건 어렵지 않지만 동시에 가로와 세로의 값을 더하는게 관건이다.나같은 경우는 격자를 아예 새로 수정해서 더했는데 선생님의 방법은 동시에 구하는 것이었다.위와 같은

정말 뒤통수 딱 한대 얻어맞는 알고리즘이었다. 반대로 loop한다음에 더 작은값이 저장되도록 하다니... 박수...s과 t를 넣은 다음 s의 각 글자가 t와 얼마나 떨어져있는지 알아보는 것이다. t사이에 글자가 있다면 가까운 t와 거리를 측정한다.그림을 그려가면서 해보

ram에다가 일거리를 저장한다. 차곡차곡 일이 저장된다. 그러다가 이미 저장된 일을 해야한다고 하면 그 일을 맨 처음으로 끌어온다.아래 진행상태를 적어보겠다.이런식으로 일거리가 들어오면 최종 ram을 리턴하면 된다.어떻게 밀어넣으면 될까? unshift 라는 built

이번에는 마구간의 갯수와 거리가 주어지고 말의 갯수가 주어진다. 이 말들을 모두 배치한다고 했을때 가장 서로의 거리가 멀게 배치하려면 얼마의 간격을 두고 배치해야하는가의 문제이다.예를 들어서, 3마리의 말이 주어지고 마굿간은 \[1, 2, 4, 8, 9] 의 간격으로

이번엔 재귀를 사용해보려고 한다. 이번문제는 간단하다. N이라는 숫자를 넣었을때 N의 부분집합을 모두구하면 된다.예를 들어 3을 투입했을때, 아래와 같은 집합이 부분집합들이다.기본적으로 0,1을 어떤 배열에 넣고 최종적으로 1인것만 구별하여 경우의 수를 뽑아내는 방법을

이번엔 거스름 돈을 줄때 동전 갯수가 최소가 되게 하면 된다. changes = 15,coins = \[1,2,5] 가 주어졌을 때 1,2,5의 조합으로 15가 되게 합을 만들어야 한다. 이때 동전의 갯수가 최소한으로 되게 하고 그때의 갯수를 return하면 된다.우선

순열은 nPr로 나타낸다. n개의 숫자중에서 r개의 숫자를 뽑는 경우의 수이다. 순서를 신경쓴다. 공식은 n!/(n-r)! 이다.이번엔 arr를 주고 여기서 r개를 뽑아서 나오는 경우의 수를 만들어볼려고 한다. 그래서 순열뿐만 아니라 순열 각각의 조합을 또다시 구해볼

조합은 순서 상관없이 n개의 숫자중에 r을 뽑는것을 말한다. 다시 말해, 1,2,3 이 주어지면 1,2 / 1,3 / 2,3 이렇게 조합을 구할 수 있다. 1,2 / 2,1은 같은거라고 본다. (순열은 다른거라고 본다.)따라서 nCr = nPr / r! 라고도 말할 수

이번엔 수열을 예측한다. 숫자들이 나열되어있는데 각각 더하다 보면 최종적인 합이 나온다 그 합을 보고 맨처음 시작된 수열을 예측하는 함수를 만드는것이다. 아래 예시를 살펴보자.그래서 16을 통해서 3,1,2,4 를 뽑아내면 된거다.그럼 어떻게 시작해야할까? 사실 전혀

ARRAY의 형태의 미로가 주어진다. ARRAY 탐색 능력을 기르는 문제이기도 하다. 독특한 방법으로 접근한다.좌표를 미리 설정하는 형태이다. X,Y의 좌표를 조합해서 ARRAY의 좌표안에서 누적해서 미로안을 움직인다.그리고 미로에서 이미 지나간 자리는 1로 처리하여

현재 나의 위치가 주어지고 염소의 위치가 주어졌다. 그리고 내가 한번에 갈 수 있는 거리가 주어진다. 이때 최소한의 움직임으로 염소까지 간다고 했을때 움직였던 횟수를 구하면 된다.구체적 예를 들어 말해보자.나의 위치: 5염소위치: 14한 번에 움직일 수 있는 거리: -

map이라는 array가 주어지고 1로 이루어진 섬이 몇개 있는지 체크하면 된다.먼저 간단하게 생각해보자. 일단 지도를 다 둘러봐야하므로 이중포문이 필요할 것이고 이중 포문안에서 돌다가 1을 찾으면 닻을내리고 그 섬안을 또다시 다 둘러봐야하므로 재귀나 또 다른 포문이

이중포문을 만들고 next x, next y를 만드는것은 이전의 재귀함수 섬나라랑 같다. 차이점은 queue를 만드는 것이다. queue안에다가 좌표를 넣고 해당이 되면 다음 좌표를 push한다.그리고 다시 queue에서 좌표를 뽑아서 같은 방법을 진행한다.끝남! 그럼

dfs때 풀었던 알고리즘인데 동전의 갯수가 많아지고 거슬러야 할 돈이 커지면 그 유명한 stack overflow가 나게 된다. 이때 필요한게 다이나믹 알고리즘이다.우선 거스름돈 숫자를 길이로 하는 다이나믹 배열을 만든다. 예를 들어 20원을 바꿔줘야한다고 했을때 0부

총시간이 주어지고 점수가 주어지고 문제를 푸는데 걸리는 시간이 주어졌을때 가장 많이 점수를 얻으려면 어떤 문제를 풀어야 하는가?예를 들어, 아래와 같이 정보가 주어졌다고 하자이때 1번, 2번, 4번 문제를 시간내에 풀 수 있고 이때 최대점수 41점을 얻을 수 있다.그럼

프로그래머스에서 코딩테스트를 공부하고 있다. 자주 나오는 문제 위주로 풀고 있는데 그 중에 하나가 '기능개발' 문제이다.progesses와 speed 배열 두개가 주어진다. 그리고 하루가 지날 때 마다 speed 만큼 progress가 이루어진다. 그러나 n번째 작업은

수포자들이 수학문제를 푼다. 사실 푼다기보다는 찍는다 ㅋㅋㅋㅋㅋ 근데 찍을때 각자의 규칙이 있다. 문제는 그 문제의 정답이 주어졌을 때 제일 문제를 많이 맞힌 학생이 누구인지 return하는 것이다. 만약 모두 점수가 같을때는 번호순서대로 push한다.예를 들어 각 학

숫자가 적힌 종이 쪼가리가 주어진다. 이 종이쪼가리를 이어붙여서 숫자를 만들 수 있는 만큼 만들고 그 이어붙인 숫자들이 소수이면 answer에 추가한다. 예를들어, 17 이 주어지면 1,7이라는 숫자가 적힌 종이조각이 주어진것이다.이때 만들수 있는 경우의 수는 1,7,

array가 주어지고 그 안에 숫자가 주어진다. 그 숫자의 조합을 통해서 가장 큰 숫자가 무엇인지를 출력하면 된다. 예를 들어, \[6,10,2] 라는 배열이 있으면 이 배열을 조합해서 숫자를 만든다. 조합해서 만들 수 있는 숫자중에 가장 큰 숫자는 '6210' 이다.

이번엔 다소 간단한 문제이다. array가 주어지고 commands가 주어질 때 commands에 따라서 array안에 원소를 뽑아서 return한다. 예를 들어, commands = \[1,3,1] arr = \[1,2,3,4] 이라고 했을 때 arr에서 1~3번째

주어진 array는 각각의 논문이 얼만큼 언급되어있는지 알려주고 있다. 이때 h편 이상 언급된 논문이 h편이상일때 h를 h-index라고 한다. 이때 h-index의 최대값을 구하라.예를 들어서 array = \[0,3,1,5,6] 일때 h-index는 3이다. 5는

참가자와 완주한 선수를 pass하여 완주하지 못한 선수를 찾아낸다. 굉장히 간단한 문제이다참가자 hash 완주한 선수 hash 를 만들어서 비교한다음 완주한 선수가 참가자 안에 있으면 1을 뺀다.그리고 1보다 크거나 같은 hash Key를 완주하지 못한 선수라고 보고

옷의 종류와 옷이 주어지면 그 옷을 가지고 얼마나 많은 경우의 수를 뽑아낼 수 있는지 물어보는 문제이다. 예를들어, 다음과 같은 옷이 주어졌다고 해보자.여기서 모자와 안경과 신발을 하나만 바꾸어도 변장에 성공하는 거다. 그러니깐 yellow hat + green_tur

이 문제는 숫자가 담긴 배열이 주어지고 그 숫자를 더하거나 빼서 타겟 넘버와 일치하면 되는 것이다. 예를 들어, \[1,1,1,1,1],3 이라는 배열과 타겟 넘버가 주어졌을 때 아래와 같은 조합을 통해 타겟 넘버를 구할 수 있다.이때 떠오르는 것은 부분 집합이다. c

이번엔 나름 신선한 문제이다. 컴퓨터가 주어져있는데 서로 연결된 컴퓨터를 찾으면 된다. 일단 서로 연결되어있는 컴퓨터끼리는 같은 네트워크를 공유하므로 네트워크가 1개 생겼다고 보면된다. 예를 들어서, 아래와 같은 배열이 주어졌다고 생각해보자.이때 컴퓨터의 갯수는 3대이

시작 단어가,target 단어, 단어배열이 주어질때 시작단어가 target단어로 변환해야하는데, 최소한의 단어만 바꿔서 변환한다고 할때 최소 몇단계를 거쳐야하는지 찾는 문제이다. 예를 들어 아래와 같은 변수가 주어졌다고 하자.처럼 변환이 가능하다. 알파벳 하나만 바꿔가

여행경로를 알아내는 프로그램을 작성해야한다. 어디서 출발하며 어디를 거쳐 어디에 도착해야할지 알아내야한다. 우선 항상 ICN에서 출발한다. 그리고 ICN에 도착해서 도착지에서 출발할 수 있는 장소를 이어서 출력하면 된다. 그리고 출발지에서 갈 수 있는 곳이 2군데 이상

디스크에 작업이 들어온다. 각 작업의 요청시간과 처리소요시간이 주어진다. 예를 들어 아래와 같이 작업에 대한 요청시간과 소요시간이 주어졌다고 해보자.첫번째 작업을 a / 두번째 작업을 b / 세번째 작업을 c라고 했을때 a는 0ms에 task에 들어왔고 3ms가 걸린다

총 학생수, 체육복을 잃어버린 아이들과 여벌의 체육복이 있는 아이들이 담긴 배열이 각각 입력된다. 아이들의 번호가 높으면 치수가 크고 낮으면 치수가 작다. 그래서 바로 이전의 번호를 가진 학생, 또는 바로 다음 번호를 가진 학생에게만 체육복을 빌려줄 수 있다.그리고 여

이 문제는 살짝 복잡할 수 도 있다. 그래서 타인의 코드를 참고하였는데 오류가 발생해서 내 나름의 방법을 적용해서 해결했다!!! 대박이다...!문제설명: 조이스틱을 위아래로 움직이면 알파벳이 바뀌고 양옆으로 움직이면 위치가 변경가능하다고 하자. 이때 주어진 알파벳으로

바로 예시를 통해서 배워보자.이렇게 정보가 주어졌을때 k만큼 number에서 숫자를 제외하고 나머지 숫자의 갯수들로 숫자를 조합한다고 했을때, 만들어 질 수 있는 숫자중 가장 큰 수를 리턴하면 된다. 그럼 return 값 처럼 결과가 출력된다.이때, number안에 배

섬들이 있는데 서로 다리를 통해서 연결되어있다. 연결시키는 다리에 비용이 들어간다. 그 비용도 다 알 수 있다. 이때 가장 적게 비용이 들어가는 다리만을 골라서 모든 섬이 통행되도록 연결한다고 했을때 , 들어가는 최소비용을 리턴하면 된다.예를 들어, 아래와 같은 배열이

의외로 간단한 문제이다. 각 차량들의 진입 시점과 진출 시점이 담긴 array를 받자. 그리고 가장 차량이 많이 지나다니는 시점에 단속카메라를 설치해야하고, 모든 차량이 한번은 단속카메라의 범위에 들어와야한다고 하자. 이때, 설치되는 총 카메라 수를 리턴하면 된다.예를

중요도가 높은 순서대로 먼저 프린트를 한다. 각각의 문서에 숫자가 매겨져 있는데, 숫자가 높을 수 록 중요도가 높아진다. 그래서 중요도가 가장 높은 문서가 가장 먼저 프린트 된다. 이때 location(idx)에 해당되는 문서가 몇번째로 출력되는지 리턴하면 된다. 만약

다리 길이, 다리가 지탱할 수 있는 무게, 트럭무게가 담긴 배열이 주어진다. 트럭이 다리를 건너서 다 지나갈때까지 몇초가 걸리는지 리턴하면 된다. 트럭이 다리길이 1을 지나는데 1초가 걸린다고 보면된다. 예시를 통해 알아보자.그래서 총 8초가 걸린다. 코드로 구현해보자

하나의 주식이 오르고 내린다. 오르고 내린 가격들이 적혀있다. 이때 각 시간대별로 떨어지지않은 구간이 몇초인지 리턴하면 된다.(언제나 예시를 보면서 알아보자!)0초일때 1$ 하던 주식은 끝까지 떨어지지 않으므로 4초간 유지된다고 할 수 있다.1초일떄 2$ 하던 주식은

각 장르마다 곡이 들어가 있다. 이때 각 장르별로 가장 재생이 많이 된 상위 2곡을 선정해서 앨범을 만들려고 한다. 예시를 살펴보자두 가지 solution이 있다. 두개다 기가막힌 solution이다.pseudo codedic을 만들어서 장르별 총 재생횟수를 저장한다g

갈색과 노란색으로 이루어진 카펫이 있다. 아래 그림처럼.carpet노란색 타일이 중간에 있고 그 겉을 갈색 타일이 감싸고 있다. 노란색 타일의 총 갯수는 2개이고 갈색타일은 8개이다. 이때 카펫의 가로는 4이고 세로는 3이다. 노란색 타일과 갈색타일의 총갯수가 주어졌을

괄호가 주어진다. 그 괄호들이 짝은 맞는데 방향이 맞지 않는 경우가 대부분이다. 예를 들어, (()())() 는 올바른 괄호이다. 괄호의 방향들이 맞아떨어지기 때문이다. 하지만 (())())))((( 는 올바른 괄호가 아닌 단지 균형잡힌 괄호일 뿐이다.따라서 위의 균형

이번엔 로또 당첨 여부를 알아본다. lottos와 win_nums가 pass된다. lottos에는 내가 뽑은 로또 번호가 있고 wins_nums에는 당첨번호가 적혀있다. 보통 로또와는 다르게 내가 뽑은 번호가 wins_nums에도 있으면 당첨 번호를 1개 획득한것이다.

1.엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.2.왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.3.오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사

게임 안 한지도 꽤 된것 같네. 이번엔 실패율을 구하는 알고리즘을 짜는 문제이다. 각 스테이지당 통과한 사람 대비 플레이하고 있는 사람의 숫자를 보고 실패율을 계산해서 가장 실패율이 높은 스테이지부터 내림차순으로 실패율에 따른 스테이지를 정리한다음 리턴하면 된다. 예시

유저아이디와 그에 해당되는 닉네임을 가지고 채팅방에 들어오고 나가고 닉네임을 변경한 히스토리가 pass될것이다 그럼 그 히스토리를 보고 그 유저아이디에 해당되는 닉네임을 return하면 된다.예를 들어 보자history를 보면 유저아이디가 uid1234는 최종적으로는

1.가장 먼 노드 일단 지금은 캠프교육중이라 시간이 없어서 이렇게 정리해놓는다. 시간 나면 나중에 그림으로 그려가면서 해봐라 이해 바로 된다.

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사

블록을 하나씩 깐다. 그러나 나중에 블록이 깔리면 그 이전에 깔았던 블록을 덮어씌어 버린다.그림으로 나타내면 아래와 같다.규칙이 보이는가? 각 index에 놓일 숫자는 index의 약수중 가장 큰 약수를 구하면 된다.약수중에 최대 약수는? 약수를 구한다음 그 약수로 본