당신의 이야기에 주목할께요

■ 해결 방법callings에 있는 값을 players에 순회해서 찾으려면 50,000 * 1,000,000의 시간복잡도가 소요된다. 따라서 O(n) 이하의 시간 복잡도로 풀 수 있는 방법을 찾아야 한다. 나는 players의 있는 값들을 순위를 매겨주었다. { mumu : 1, soe : 2, poe : 3, kai : 4, mine : 5} 이런식으로 해준 다음 callings에 불린 값과 그 앞의 값의 순서를 바꿔주는 형태로 진행했다. 이 때 주의해야 할 것은 players의 순서만 바꾸어 주는 것이 아닌, 순위도 값이 변경해주어야 하는 것이다.  ■ 코드 function solution(players, callings) { var answer = []; let playersDict =..

■ 해결 방법문자열을 잘 가지고 놀아야 하는 문제이다.  계산된 개인정보 약관과 현재 날짜를 비교를 하면 되는데, 구조화를 잘 해놓기만 하면 쉽게 풀 수 있다. ■ 코드 function solution(today, terms, privacies) { var answer = []; let map = new Map(); for(key in terms){ map.set(terms[key].substr(0, 1),Number(terms[key].split(' ')[1])) } for(key in privacies){ let year = Number(privacies[key].substr(0,4)) let month = Number(privacies..

■ 해결 방법 처음에는 점끼리 겹치는 선분의 길이를 더해서 구하려고 했으나, 세개의 선분이 동시에 겹칠 때를 계산하기 위해서 너무 복잡해졌다. 알고리즘은 더 효율적인 방법으로 모색해야 하므로 다른 방법을 고민해보았다. 색칠로 비유해보자면 일직선에 1 단위로 칸이 나누어져있고 해당 칸에 색칠을 해준다는 느낌으로 생각을 해보았다. 그러면 여러번 색칠 된 것이 답이 될 것이다. 길이가 200인 일차원 배열을 선언해주고 값을 0으로 채웠다. 이후 lines의 배열을 순회하며 일차원 배열의 값을 채워갔다. 예를 들어, lines[0]의 값이 [0, 1] 일 때, 일차원 배열 line의 값은 line[0] =1이 된다. 이런식으로 line 배열의 값을 채우고 마지막에 1보다 큰 값을 카운트 해주면 된다. ■ 코드 ..

해당 문제는 큰 수의 나머지를 구하는 문제였다. 나는 계속 큰 수를 실수형으로 바꾸려고 했는데, 그렇게 하면 안되고 한 자리 수 계속 구할 때 나머지를 구해줘야 했다. 예를 들어, for(int i = 0; i < str_AtoN.size(); i++){ tmp = str_AtoN[i] - '0'; sum = (sum * 10) + tmp; } // 이 아니라 sum 에 계속 나머지 연산을 해주어야 한다. for(int i = 0; i < str_AtoN.size(); i++){ tmp = str_AtoN[i] - '0'; sum = ((sum * 10) + tmp) % 97; } 이제 1번도 제대로 못푼다. 매일 꾸준히 풀어보자.

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분검색을 이용하여 랜선을 자르는 문제이다. 다합쳐서 나누기를 하는 방법을 처음 생각해봤는데 제대로 된 답이 안나왔다. 그렇다면 기존의 랜선 중 하나를 정해서 이분 탐색을 이용해 수를 찾아서 정답을 도출하는 방법이 생각이 났다. 몇가지 오류가 있어서 사람들꺼 참조해보니 논리는 잘 되었지만 몇가지 부분에서 잘못된 것이 있었다. * 내가 짜놓은 코드는 첫번째로 만족하면 바..

https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 간선으로 연결된 정점들의 집합이 몇 개 있는지 구하는 문제이다. DFS나 BFS로 풀 수 있다. 흔히 영역을 구하는 문제와 비슷한 것 같다. 오늘은 간단하게 코드만 올리겠다. 12345678910111213141516171819202122232425262728293031323334353637383940#include#incl..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net "그래프 이론에서, 이분그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강 색과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다." - wiki 좀 더 설명하자면, 이 문제에서 위와 같은 그림은 이분 그래프이다. 한 정점이 빨간색이면 간선으로 연결된 정점은 다른 색을 가져야 한다. 같은 색을 가지게 되면 이분 그래프가 아니다. 위와 같은 그래프를 보면 이 그래프가 이..

이 문제에서 key는 모든 채널을 체크해보는 브루트포스 방식을 사용하는 것이다. 나는 시험칠 때 모든 채널을 체크해볼 것을 생각해보지 못했다. 모든 채널을 체크하고 그 채널이 가능하면 몇 번 클릭하는지 계산하고 최솟값을 찾아내면 되는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include using namespace std; bool broken[10]; // 나올 수 있는 채널인지 확인하는 함수. // 만약 나올 수 없는 채널이면 0을 반환, // 나올 수 있는 채널이면 그 채널의 길이를 반환한다. int ch..

A진법을 10진법으로 바꾸고, 10진법을 B진법으로 바꾸어 해결하는 문제이다. 나같은 경우 조건이 A진법의 자릿수가 25이하라는 것을 보고 당연히 10진법으로 바꾸지 않고 해결하는 방법이 있는 줄 알았으나 문제 말미에 "A진법으로 나타낸 수를 10진법으로 변환하였을 때의 값은 양의 정수이며 220보다 작다." 이라는 말이 있었다. 그래서 그냥 일반적인 진법 변환 코드를 만들어 해결해주었다. 1 2 3 4 5 6 void convertDecToB(int n, int base){ if(n == 0) return; convertDecToB(n / base, base); cout b >> len; num = 0; for(int i = 0; i > val; num = num * a + val; } convertD..

www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 문자열에 대한 함수를 활용하면 쉽게 풀 수 있다. substr로 시작점을 다르게 해서 문자열 그룹에 넣고 문자열 그룹을 정렬해주면 된다. 전체코드 12345678910111213141516171819202122232425#include#include#include#include#include using namespace std; string s; int main(void){ int len; vector sgroup; cin >> s; len = 0; for(char c : s) len++;..