문제 문제 링크 : programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1..

문제 문제 링크 : programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets..

최단 경로 (다익스트라) 최단 경로를 찾는 문제는, 한 정점으로부터 다른 모든 정점으로 가는데 걸리는 최단 경로를 통해 결국은 원하는 지점으로 최단경로를 찾는 방법이다. 다익스트라는 여기서 첫 점을 기준으로 정점들을 추가하며 거리를 갱신시킨다. D(z)를 x에서 z까지의 최단 경로라 한다면 $D(z) = Min(D(z) , D(y) + c(y,z))$ 의 식을 계속 진행하여 전체 경로에 대한 최단 경로를 알아낸다. //최단 경로 수도 코드 //입력 : 가중치 그래프 G //출력 : distance 배열, distance[u]는 v에서 u까지의 최단 거리 shortest_path(G,v) S = v; for(G의 각 정점 w) do distance[w] = weight[v][w]; while 모든 정점이 ..

그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료 구조이다. 수학자 오일러에 의해 처음 창안되어 그래프 이론은 컴퓨터 학문 분야의 활발한 연구 주제이다. 그래프에 관한 아주 간단한 설명은 이전 게시글에 있다. 2. 자료구조 (2) - 트리, 그래프 트리 트리 = 노드(node)로 이루어진 자료 구조. 하나의 루트 노드가 존재하고, 이로부터 0개 이상의 자식 노드들이 존재합니다. 이 노드들이 서브트리(subtree)를 구성합니다. 루트와 서브 트리, 각� howtolivelikehuman.tistory.com 인접 행렬 vs 인접 리스트 그래프를 표현하는 방법은 두가지가 있다. 인접 행렬과 리스트 인접행렬 M의 각 원소를 아래와 같은 규칙에 따라 그래프를 메모리에 표현할 수 있다. if(간선 x..

문제 문제 링크 : programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 � programmers.co.kr 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 ..

문제 문제링크 : programmers.co.kr/learn/courses/30/lessons/42578/ 코딩테스트 연습 - 위장 programmers.co.kr 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 ..

문제 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한사항 입국심사를 기..

문제 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42576/ 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수�� programmers.co.kr 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수..

순열 순열과 조합은 경우의 수 등 가능한 가짓수를 생각할때 가장 바탕이 된다. 우선 순열은 순서가 있는 묶음으로, 7명을 등수를 매기는 방법과 같이 각각 구분되는 형식에 데이터를 나누는 방법이다. 수학적으로 보면 ${}_n\mathrm{P}_{k} = \frac{n!}{(n-k)!}$ 7명을 등수를 매기는 방법 $7! = 7\times6\times5\times4\times3\times2\times1 = 5040$ 7명 중 1,2,3등을 매기는 방법 $\frac{7!}{(7-3)!} = 7\times6\times5 = 210$ 으로 볼 수 있다. 이러한 순열을 직접 사용하는 경우는 내 생각엔 보통 완전 탐색 등에서 모든 가짓수를 체크하기 위해 사용하는 것 같다. 7명중 1,2,3등을 매길 때 ~ 무슨 조건..

순차 탐색 주어진 값들에서 최대, 최소를 찾는 방법은 다양하다. 아마 우리가 자주 사용하는 방법은 데이터를 첫 번째 부터 읽어서, 현재까지 저장해놓은 최대값과 계속 비교해 나아가는 방법일 것이다. //c++ int findMax(int data[], int length){ int max = INT_MIN; // 사용 //int min = INT_MAX; int i; for(i = 0; i data[i]) min = data[i]; } return max // or min } 이러한 방법을 사용하였을 때, 우리는 필연적으로 $n-1$ 번의 비교를 해야한다. 더 효율적인 방법은 없을까? 우리가 실생활..