n개의 자성체들 사이에는 n-1개의 균형점이 무조건 존재한다고 보고 양 자성체들을 각각 s,e로 놓고 균형점(mid)의 위치를 이분탐색으로 찾아나간다. 오차범위가 무슨 말인지 못하다가 대략 이해했는데 만약 이분탐색으로 양쪽의 힘이 딱 같은 곳을 못발견한채로 s>e가 되어버리는 순간이 있다면 균형점 mid를 찾아야되는데 범위를 넘어가버린다는 것은 이분탐색으로 정확히는 모르지만 s와 e사이에 균형점이 있기는 있다는 것이다. 그럼 세부 좌표 오차일 것이므로 해당 mid를 출력해버리면 된다. s에 1e^12를 빼거나 e에서 뺐을 때 범위를 넘어가면 두 좌표 사이의 거리는 그것보다 작은 것이니까 그 사이에 무조건 있다. 그래도 mid를 출력해도 되는 이유는 10자리까지만 출력하기 때문인 것 같다. #include..
입력받은 문자열의 실제 숫자 개수를 배열에 저장한다 (인덱스 = 숫자) 숫자 개수만큼 다시 문자열 형태로 출력해준다. #include #include using namespace std; int t; int getNum(string str) { if (str == "ZRO")return 0; if (str == "ONE")return 1; if (str == "TWO")return 2; if (str == "THR")return 3; if (str == "FOR")return 4; if (str == "FIV")return 5; if (str == "SIX")return 6; if (str == "SVN")return 7; if (str == "EGT")return 8; else return 9; } s..
일단 1~18 사이 소수를 먼저 구해준 후 A가 소수 개를 성공할 확률, B가 소수 개를 성공할 확률을 구한다. 만약 A가 2개를 성공한다고 칠 때 18개의 구간 중 어느 구간 2개에서 성공하는 지를 구해줘야 하므로 18C2를 구해서 a의 2개 성공확률에 곱해줘야 된다. 둘 중 적어도 하나가 소수인 확률은 전체확률인 1에서 둘다 소수가 아닌 확률(여집합)을 빼주면 된다. 교집합을 구하는 방법과 소수개를 성공할 확률을 구하는 것까지는 잘 했는데 조합을 구해줘야 된다는 것을 떠올리지 못해 못 풀어서 해당 부분은 참고해서 했다. 조합은 nCr=n-1Cr-1 +n-1Cr의 식을 참고하여 이중배열로 미리 구해준다. #define _CRT_SECURE_NO_DEPRECATE #include #include #inc..
최대 6자리 숫자의 자리수 중에 2개를 고르는 것: 6C2 =15가지 최대 10번 자리 교환한다 15의 10승=> 시간초과 따라서 VISIT방문 처리를 해주거나 다른 방법으로 풀어야되는데 다른 사람걸 보고 VISIT[만든숫자][교환횟수]=TRUE 이런식으로 해주면 된다. 백준의 토마토 3차원문제가 이런식으로 했던거 같은데 가끔 잊을만하면 나온다 #include #include #include #include using namespace std; int result; bool visit[1000000][11]; int toNumber(string s){ int temp=0; for(int i=0;iresult)result=temp; return; } for(int i=0;it; for(int tc=1;tc..
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 커서 (현재 보고 있는 위치)에 동적으로 추가 삭제, 그리고 링크 이동을 연습하는 문제 #include #include #include #include using namespace std; int t; string s; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> t; while (t--) { list li; ci..
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 두 가지 방법으로 풀 수 있다. 하나는 원소 체크(기록)을 해서 배열의 원소 a에 대해서 x-a가 배열에 있는 지 체크하는 법 또 하나는 정렬 후 투포인터를 이용하는 법. 1. 기록 #include using namespace std; int num[100001]; int cnt[2000001]; int main(void) { ios::syn..
https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net #include #include #include using namespace std; int num[26]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; for (auto c : s) { num[c - 'a']++; } cin >> s; for (auto c : s) { n..
https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 9의 경우는 6인 것처럼 카운팅해준다. 0부터 9까지 몇 개 나왔는지 확인하고 6은 6과 9의 카드 모두 쓸 수 있으니 2로 나눠서 몇 팩이 필요한지 본다. 만약 6이 홀수로 남으면 한 팩이 더 필요하므로 +1 해준다. 나머지 숫자는 한 팩당 카드 하나씩 있으므로 카운팅한 갯수가 필요한 팩의 수이다. 각 숫자가 필요한 팩의 개수 중 가장 큰 수가 답이다. #include #include using namespace std; int num[10]; int main(void) { ios::..
싸피 5기를 마무리하고 방학 중에 넥슨 수시 채용 합격 소식을 들었다 신나서 싸피를 퇴소하고 넥슨에 입사하였다 전반적으로 회사 분위기도 조용하고 팀원분들도 사근사근하셔서 좋았다 재택근무에서 출근 근무를 병행하는 것으로 바뀌던 차에 내가 들어왔고 일주일 동안 재밌게 다니고 있었다 그러던 와중에 삼성전자의 합격 소식을 들었다 넥슨과 삼성전자 사이에서 고민하였으나 삼성전자를 들어간다면 경력직보다는 다른 신입 동기들과 공채로 들어가는 것이 가장 좋을 것 같았다 넥슨은 일주일동안 문화도 경험했으니 삼성전자가 궁금해졌고 들어갈 수 있는 마지막 기회라고 생각하여 일주일만에 넥슨을 퇴사하였고 이직했다 계속 취준을 걱정했었는데 올해 좋은 회사들에 취업되어서 아직도 얼떨떨하다 아직 입사까지 시간이 남아서 어떻게 놀까 생각..
해봤던 지인은 좋았다고 하더라구요 아직 취직을 안했고 알고리즘을 공부하고 싶다면 신청해보세요