C++
-
프로그래머스 가장 먼 노드 C++프로그래머스(Programmers) 2022. 4. 22. 22:23
=> BFS문제입니다. => 각 노드들이 맺고 있는 관계들을 벡터로 표현하였습니다. => 이를 vector로 표현하거나 배열로 하거나 편하신대로 하면 됩니다. => 해당 문제에서는 노드의 개수와 간선의 개수가 20,000개 , 50,000개 이므로 벡터를 사용하여 공간의 낭비를 줄였습니다. => 간선들을 표현한 이후에는 항상 사용하던 BFS를 사용하여 문제를 해결하였습니다. https://codingham.tistory.com/168 DFS, BFS code =>BFS 와 DFS code를 사용하기 위해 미리 정리해두었습니다. //int dist[100001]={0}; //bool check[100001];//갔다온지 확인하는 행렬 bool arr[MAX][MAX]; //인접행렬 vector list[M..
-
프로그래머스 영어 끝말잇기 C++프로그래머스(Programmers) 2022. 4. 21. 22:03
제한 사항 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다. words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다. 단어의 길이는 2 이상 50 이하입니다. 모든 단어는 알파벳 소문자로만 이루어져 있습니다. 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다. 정답은 [ 번호, 차례 ] 형태로 return 해주세요. 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요. 입출력 예 nwordsresult 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe..
-
백준 나이트의 이동 C++백준 algorithm 2022. 4. 13. 23:12
입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 예제 입력 1 복사 3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1 => 간단한 BFS문제입니다. => BFS로 탐색을 하며 target 좌표를 찾았을 경우 해당 값까지 이동한 거리를 출력하면 됩니다. => B..
-
백준 11286 - 절댓값 힙백준 algorithm 2022. 4. 9. 23:06
입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다. 예제 입력 1 복사 18 1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0 예제 출력 1 복사 -1 1 0 -1 -1 1 1 -2 2 0 => 기존 최소힙, 최대힙 문제를 응용한 ..
-
백준 1927 - 최소 힙백준 algorithm 2022. 4. 6. 23:16
입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 출력 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다. 예제 입력 1 복사 9 0 12345678 1 2 0 0 0 0 32 예제 출력 1 복사 0 1 2 12345678 0 => 최대힙의 반대로 최소힙문제입니다. => queue 헤더안에 있..
-
백준 11279 최대힙 C++백준 algorithm 2022. 4. 2. 23:58
예제 입력 1 복사 13 0 1 2 0 0 3 2 1 0 0 0 0 0 예제 출력 1 복사 0 2 1 3 2 1 0 0 => 최대힙을 구현할 수 있는지에 대한 문제였습니ㅏㄷ. => C++에는 queue 헤더 안에 priority_queue 자료형을 사용 할 수 있습니다. => 해당 자료형을 이용해서 주어진 조건에 따라 출력문을 출력하면 되는 문제였습니다. => 시간초과가 걸릴 경우, cin.tie(0); ios_base::sync_with_stdio(false); 해당 구문을 입력해줄 경우 시간초과에 걸리지 않게 됩니다. #include #include #include #include #include #include #include #include #include using namespace std; i..
-
백준 2178 - 미로탐색 C++백준 algorithm 2022. 3. 28. 17:45
입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다. 예제 입력 1 복사 4 6 101111 101010 101011 111011 예제 출력 1 복사 15 예제 입력 2 복사 4 6 110110 110110 111111 111101 예제 출력 2 복사 9 예제 입력 3 복사 2 25 1011101110111011101110111 1110111011101110111011101 예제 출력 3 복사 38 예제 입력 4 복사 7 7 1011111 1110001 1000001 10000..
-
프로그래머스 조이스틱 C++프로그래머스(Programmers) 2022. 3. 22. 00:50
제한 사항 name은 알파벳 대문자로만 이루어져 있습니다. name의 길이는 1 이상 20 이하입니다. 입출력 예 name return "JEROEN" 56 "JAN" 23 => 풀이는 아래 그림으로 첨부하겠습니다. #include #include using namespace std; int solution(string name) { int answer = 0; int n = name.length(); int turn = n - 1; //조이스틱을 한 방향으로 쭉 움직였을 때 for (int i = 0; i < n; i++) { if (name[i] - 'A' < 14) answer += name[i] - 'A'; else answer += 'Z' - name[i] + 1; int ind = i + 1;..