개발공명의 블로그

오늘의 문제 https://school.programmers.co.kr/learn/courses/30/lessons/388351 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 풀이간단한 문제 요약은 아래와 같다. 일주일 간 설정한 출근 희망 시각에 늦지 않은 직원에게 상품 이벤트 직원들 출근 희망 시각 + 10분까지 출근해야 함 토, 일요일은 이벤트에 영향 X 매일 한번 어플로 출근 시간은 10:13 -> 1013 이렇게 표현 설정한 출근 희망 시각과 실체 출근 기록 주어짐 이것으로 상품 받을 직원 몇명인지 구하기 n = ..

오늘의 문제https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 풀이문제를 보고 생각한 것은 아래와 같다.마지막 셔틀에 타는 것이 베스트마지막 셔틀에 타는데m명 이상 대기 중이면 m번째 사람보다 1분 일찍 오면 됨m명 미만 대기 중이면 마지막 셔틀 도착 시간에 타면 됨마지막 셔틀 -1 도착 시간 이전 사람은 버리면 됨but m이상이라 못 타고 남아 있는 사람 생각해야 함→ 시간마다 확인하며 사람 줄여나가야 함마지막 셔틀 도착 시간 이후 사람 버리면 됨 이런 생각을 가지고 문제를 풀기 시작했..

오늘의 문제https://school.programmers.co.kr/learn/courses/30/lessons/258712 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 풀이문제를 보고 기록해야 할 것을 아래와 같이 파악했다.한 사람이 다른 사람에게 준 선물 개수 & 받은 선물 개수한 사람의 선물 지수한 사람의 다음 달에 받을 선물 개수 아무래도 이름이 string이라 map을 사용하기로 결심했다.‘한 사람이 다른 사람에게 준 선물 개수 & 받은 선물 개수’이것은한 사람 이름다른 사람 이름준 선물 개수받은 선물 개수이렇게 4개의 정보를 저장해야 했다.그래서 아래와 같은 자료 구조가 나왔다.ma..

오늘의 문제https://school.programmers.co.kr/learn/courses/30/lessons/389479 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  pair오늘 문제는 c++의 pair를 사용해 풀었다. pair는 은근히 문제를 풀다 보면 많이 사용하고 알아두면 굉장히 유용한 것 같다.  pair는 두 개의 값을 하나의 객체로 묶어서 저장할 수 있는 STL 템플릿 클래스이다. 두 개의 값을 가지고 있는 자료형으로 생각하면 될 것 같다.  pair는 utility 라이브러리에 있어서 #include 를 해줘야 한다.  pair를 생성하는 방법은 아래와 같다. (넣을 자료형은 필..

오늘의 문제 https://school.programmers.co.kr/learn/courses/30/lessons/1835 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr C++ 순열 만들기문제에서 우선 가능한 string 전체를 만들려고 시도했다. 그래서 가능한 모든 순열을 만들어야 했다.  어떻게 가능한 모든 순열을 만들어야 하나 고민했는데 C++에 함수가 정의되어 있었다. next_permutation이라는 함수를 사용하면 된다. next_permutation 함수는 algorithm 헤더에 정의되어 있다.  next_permutation 함수는 파라미터로 Bidirectional Iterator..

오늘의 문제https://www.acmicpc.net/problem/6497 MSTMST는 minimum spanning tree = 최소 신장 트리의 약자이다. 최소 신장 트리에서 신장이라는 단어가 생소할 것이다.  최소 신장 트리의 의미는 그래프에서 모든 정점을 포함하는데 가중치의 합이 최소로 연결된 사이클이 없는 트리를 의미한다.  즉 모든 정점들이 연결되어 있어야 하는데 최소 비용으로 연결되어 있어야 하고 사이클이 없어야 하는 경우에 MST를 만드는 것이다.  MST를 만드는 방법은 2가지가 있다고 한다. Kruskal 알고리즘Prim 알고리즘 두 알고리즘에 대해 간단히 설명하면 아래와 같다.  Kruskal 알고리즘가장 비용이 작은 간선을 선택해가는 알고리즘가중치 순으로 간선들을 오름차순 정렬가..

오늘의 문제 https://www.acmicpc.net/problem/1450 Knapsack 배낭 문제 문제 이름부터 냅색 문제라고 되어 있어서 당연하게 Knapsack 문제에 대해 알아 보았다.  문제도 대층 쓱 보니 물건, 가방 이렇게 되어 있어서 당연히 Knapsack 문제인줄 알았다. 하지만 함정이 있었으니....  우선 공부한 Knapsack 문제에 대해 알아보자.  Knapsack 배낭 문제는 물건, 배낭이라는 개념이 나온다.  물건에는 아래 2가지 개념이 존재한다. 물건의 무게물건의 가치 배낭에는 아래 1가지 개념이 존재한다. 담을 수 있는 최대 용량 (무게) 그래서 Knapsack 배낭 문제의 목표는 아래와 같다.  배낭의 최대 용량을 초과하지 않으면서 담을 수 있는 최대 가치의 합 찾기..

오늘의 문제 https://www.acmicpc.net/problem/12956 Floyd-Warshall 알고리즘문제의 힌트가 Floyd-Warshall 알고리즘이라 해당 알고리즘에 대해 짧게 공부해봤다.  최단 경로를 구할 때 사용하는 알고리즘이다.  다익스트라 알고리즘과 함께 공부하고 비교되는 알고리즘이다.  모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘이다.  2차원 배열에 최단 거리 정보를 저장해야 한다.  노드 N개에 대해서 N번만큼 단계를 반복하며 아래 코드를 적용해 2차원 배열을 갱신해야 한다. graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]); 알고리즘의 대략적인 흐름은 아래와 같다.  step 1 : 모든 노드에 대해 ..