개발/알고리즘5 소수점 이진수 변환과 2의 보수 변환 소수점 이진수 변환 일반적인 정수의 이진수 변환은 다음과 같습니다. 2로 나누어 몫과 나머지를 구한다 몫이 0이 될 때까지 몫을 대상으로 과정 1을 반복한다 처음 구한 나머지가 가장 오른쪽에 오도록 나머지를 순서대로 적는다 정수의 이진수 변환의 예시는 다음과 같습니다. 예시) 35 35/2 = 17... 1 17/2 = 8... 1 8/2 = 4... 0 4/2 = 2... 0 2/2 = 1... 0 1/2 = 0... 1 35 = 100011_(2) 이를 나눗셈 검산을 통해 나타내보면 왜 이진수 변환에 2의 나눗셈이 필요한 지 알 수 있습니다. = 35 = 100011_(2) = 1*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 2(2(2(2(2(2(0) + 1) +.. 2023. 3. 8. 백준 14503 : 로봇 청소기 (Gold 5) 문제 문제 해석 시뮬레이션 문제. 문제에서 말하는 그대로 구현하면 됩니다. 그러나 문제 설명에서 후진하는 시점이 조금 애매한데 두 번째 예제처럼 출력이 나오려면 네 방향 모두 청소할 수 없음을 알아챈 순간 왼쪽으로 회전하지 않고 후진해야 합니다. 통찰 구현 문제이기 때문에 통찰이 필요없습니다. 시간 복잡도 4 * n * m = 4 * 50 * 50 = 10000 < 20억 (2초) n * m 만큼의 칸에서 4방향 모두 탐색 풀이 /** * @template file author kadrick (kbk2581553@gmail.com) * * author:amkorousagi (hasmi5452@gmail.com) */ #include using namespace std; #define fastio \ io.. 2022. 10. 22. 백준 14501 : 퇴사 (실버3) - 완탐, DP(재귀), DP(반복) 문제 문제 해석 최적화 문제. 제한된 조건으로 상담을 선택해 최대 이익을 출력합니다. - i 일의 상담을 선택하면, i + t [i] 일부터 다시 상담을 시작할 수 있다 통찰 1. 완전 탐색(brute force) + backtracking 현재 날짜부터 가능한 모든 경우의 수를 탐색합니다. 더 이상 선택할 수 없을 때까지 재귀 호출합니다. dp[i] = 시작일이 i 일 때 최대 이익 dp[i] = max (p[j] + dp[i+t[j]]), (i n; t.assign(n,0); p.assign(n,0); for (int i = 0; i > t[i] >> p[i]; } s(0); cout n; t.assign(n,0); p.assign(n,0); dp.assign(n + 1.. 2022. 10. 22. 백준 13460 : 구슬 탈출 2 (Gold 1) 문제 문제 해석 시뮬레이션. 일반적인 미로 문제의 변형. - 한번 출발한 방향으로 막힐 때까지 간다. - 동시에 두 구슬이 움직인다. - 파란 구슬이 떨어지면(출구에 도달) 안된다. 위 세가지만 유의하면 됩니다. 통찰 DP나 그리디와 달리 통찰이 필요 없습니다. 문제에서 요구하는 그대로 구현하면 됩니다. 처음에는 board전체를 복사하고 R과 B를 실제로 적는 식으로 하였는데 복사에 너무 많은 시간이 들어서(n*m = 10*10) 보드는 그대로 두고 구슬의 위치만 기록하는 식으로 변경하였습니다. 시간 복잡도 시간 복잡도 = 4^10*max(n, m) = 상하좌우 * 깊이 10까지 bfs * 한번 기울일 때 최대 이동하는 거리 max(n, m) n, m이 10일 때, 시간 복잡도는 4^10*10 = 2^1.. 2022. 10. 22. 네이버 AI Rush 서류 통과 및 코테 후기 서류합격받고 (깃허브 주소를 요구한다. 평소에 코딩하는 거나 진행한 프로젝트를 보는 듯하다) Naver AI Rush 코테를 어제(2022-06-15) 쳤다. 네이버라서 난이도는 조금 쉬웠던 거 같다. 다들 말하던 대로 네이버는 특정 알고리즘을 요구하기보다는 구현 위주로 보는 것 같다. 1번이 보통 쉬운 문제인데, 이번에는 1번이 조금 어려웠다. 1번이 주어진 조건으로 완전 탐색하는 문제였고 2번은 주어진 조건으로 문자열 끼워 넣는 쉬운 문제 3번도 주어진 조건으로 평균이나 중앙값 찾는 쉬운 문제 4번은 조금 특이한 n-queen이었는데 시간이 부족해서 못 풀었다. 1번에서 처음에 예외 케이스를 고려 안 하고 작성해서 고치느라 50분을 소요했고 2번에서 20분, 3번에서 20분을 소요했다. 4번에서는 남.. 2022. 10. 21. 이전 1 다음
