https://school.programmers.co.kr/learn/courses/30/lessons/258712 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic string과 숫자를 가지고 놀아야 하기 때문에 map자료구조가 적절할 것이라고 판단했다. friends배열에 있는 순서대로 인덱스를 매겨주고 서로 몇번 주고받았는지 확인했다. 핵심은 2중 for문에 있는데, 이중 계산을 막기 위해 선물을 받는 경우만 계산해줬다 코드는 아래와 같다. 2. Code #include using namespace std; map nameToIdx; i..
프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/250137?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 그냥 구현문제 부분문제를 나누자면 1. 몬스터에게 공격받을 때 2. 몬스터에게 공격 안받을 때 (붕대 감아야 함) 부분문제를 나눠서 상황에 따라 구현하면 실수를 줄일 수 있다. 2. Code #include #include #include using namespace std; int solution(vector bandage, int health, vect..
https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 무조건 한번은 경기를 해야하기 때문에 안할 수는 없고 순서를 바꿔줄 수는 있다. 그렇기 때문에 A를 항상 작게 유지시켜 줘야한다. 오름차순 정렬을 한 후 A
https://school.programmers.co.kr/learn/courses/30/lessons/148653?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 항상 +1돌 or -1돌을 사용하여 1의 자리를 0을 만든 후에 큰 숫자로 빼주는 방법이 최선의 방법이다. 부분문제가 3가지로 쪼개지는데 1. 1의 자리가 6이상인 수 (6~ 9) 2. 1의 자리가 5인 수 (5) 3. 1의 자리가 4이하인 수 (0~4) 1번의 경우에는 10을 만들어준 후 10을 만드는데 사용한 +1돌의 갯수를 계산해서 더해주고 10을 만..
1. 위상정렬이란? 순환하지 않고 방향이 정해져있는 그래프의 노드를 거스르지 않은 상태로 정렬하는 방법. 비순환 유향 그래프에서만 사용할 수 있으며 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저오는 순서로 정렬이 된다. 시간 복잡도 : O(V+E) {Vertex : 노드의 갯수 / Edge : 간선의 갯수} 2. Default Logic 위상정렬을 하는 방법에는 BFS를 사용하는 방법과 DFS를 사용하는 방법이 있는데 나는 BFS로 설명할 것이다. 먼저 BFS를 사용한 방법을 말로 설명해 보자면 1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수) 2. 한 간선을 처리한 후 inDegree를..
https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어 www.acmicpc.net 1. Logic 1. 최적경로 즉 시작부터 목적지까지 최단거리로 가는 경우가 있는지를 먼저 파악하기 위해 BFS통해 최단거리를 확인해놓는다. 2. 벨만포드를 돌면서 최단경로를 확인하고 v번을 돌면서 마지막 사이클에서 음의 사이클을 확인한다. 3. 벨만 포드 알고리즘을 돌면서 최단경로를 갱신할 때에만 주의 해야 할 사항 음의 사이클이 있다고 무조건 -1을 반환하는게 아니..
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. Logic - 모든 점에서 모든 점까지의 최단 거리를 각각 구해야한다. >> 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 3중 for문을 돌아야하기 때문에 노드의 갯수가 적을 때 사용할 수 있다. 2. Code #include using namespace std; int n, m, r; const int INF = 0x3f3f3f3f; vector dist(101, vector (101, IN..
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 1. Logic - 모든 버스 비용이 0보다 크거나 같다고 나왔기 때문에 다익스트라 알고리즘을 사용하여 풀이한다는 것을 유추할 수 있다. 일반 다익스트라 알고리즘과 동일하게 풀이하지만 해당 문제는 지나온 경로까지 표현해줘야 하기 때문에 경로를 추적하는 trace 배열을 한개 더 선언해주었다. trace배열로 경로를 찾는 과정 문제의 Testcase에서 내가 도출한 ..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 1. Logic - 입력수가 10억을 넘기 때문에 입력만으로 시간복잡도가 터진다. 그래서 시간복잡도가 O(logN)인 자료구조인 priority_queue를 썼다. 그렇기 때문에 시간복잡도 log10억은 9이다. 작은 값부터 탐색해야 하기 때문에 priority queue에 greater인자를 넣어 오름차순으로 정리해주었다. 앞의 원소들 부터 차례대로 탐색하면서 1. 입력받은 수의 전체 합이..
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 1. Logic - 문제의 조건에 따라 왼쪽에서도 값을 넣고 오른쪽에서도 값을 넣다 뺏다하기 쉬운 자료구조는 deque가 적절하다. 연산을 최소로 하기 위해서는 구해야하는 수를 기준으로 오른쪽과 왼쪽 중 어디가 더 값이 적게 남았는지 체크를 해야한다. 덱에서는 큐와 다르게 인덱스로 값을 알 수 있기때문에 덱을 사용해서 풀이하며 된다. 2. Code #include using namespace ..
