알고리즘34 [백준] 3079 - 입국심사 by C++ https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 전형적인 이분탐색 문제였다. 이분탐색을 제대로 이해하질 못해서, 이 문제를 통해 원리를 어느정도 이해할 수 있었다. 알고리즘 방식 이분 탐색의 대상은 상근이와 친구들이 심사를 마치는데 걸리는 시간이였다. (즉 정답) 시작값(st) = 0, 끝값(en) = Tk의 최대값 * M으로 지정해주었다. (시작값 또한 Tk의 최소값 * M으로 지정해도 되지만, 의미 없는 것 같아 생략) 1. .. 2022. 12. 22. [백준] 2064 - IP주소 https://www.acmicpc.net/problem/2064 2064번: IP 주소 네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워 www.acmicpc.net 비트마스킹 방식을 사용하지 않으면 구조적으로 시간 초과가 날 수밖에 없는 문제였다. 알고리즘 방식 1. C++에는 Split함수가 없으므로 직접 구현 2. 입력된 IP주소를 '.'을 기준으로 Split 하여 4개의 숫자를 vector ip에 저장 3. 네트워크 주소는 32-m자리까지 고정이고, 이후가 랜덤 값이므로, 입력된 ip주소들 간에 차이가 발생하는 최소 자리수를 구한다. 4. 3.에서 구.. 2022. 12. 16. [백준] 15661 - 링크와 스타 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 개별적으로 비트마스킹 방식과 백트래킹 방식을 사용하여 풀었다. 아직 비트마스킹이 익숙하지 않아 생각하는데 오래 걸렸다. 1. 비트마스킹 알고리즘 방식 N = 4일 때, 4명의 학생을 조합을 통해 뽑을 수 있는 경우는 0과 2^4 - 1의 숫자가 비트에 저장되는 방식과 같다. 다시 말해 각 비트 자리수는 k번째 학생의 상태를 나타내고, 뽑히지 않은 경우 .. 2022. 12. 9. [백준] 20208 - 진우의 민트초코우유 by C++ https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 최근 거의 한 달 동안 매번 풀 때마다 느끼는데 반례도 너무 못찾고 구현력도 웰케 떨어졌는지 모르겠다. 생각하다보면 사고가 그냥 멈춘다. 대체 뭐가 문제일까. 반례도 아니고, 그냥 구현력이 딸려서 2시간 동안 그것만 찾고있었다. 현타가 많이온다.... 알고리즘 방식 시간복잡도는 O(N!)이고 백트래킹을 통해 풀었다. N이 최대 10이라 10^10 = (1 * 10) *(2 * .. 2022. 11. 21. [백준] 1553 - 도미노 by C++ https://www.acmicpc.net/problem/1553 1553번: 도미노 찾기 도미노의 크기는 1×2이고, 크기가 1×1인 칸으로 나누어져 있다. 칸은 수를 나타내며, 위와 같이 총 28가지가 있다. 크기가 8×7인 격자가 있고, 격자의 각 칸에는 정수가 하나씩 들어있다. 위의 도 www.acmicpc.net 진짜 금방 풀 수 있었는데, 배열 접근 범위 제한과정에서 실수를 했다. 평상 시에 거의 하지 않는 실수여서 찾는데 너무 오래걸렸다 ㅠㅠ 침착하게 차근차근 코드를 짜자 핵심 변수 int board[8][7] : 입력된 격자를 저장 int vis[8][7] : 격자가 도미노로 채워졌는지 여부를 확인 int domino[7][7] : (r, c)의 값을 가지는 도미노의 잔여 여부 확인 voi.. 2022. 11. 16. [백준] 2217 - 로프 by C++ https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 며칠전부터 반례를 잘못생각하고, 구현도 잘못하고 슬럼프인 것 같다.... 멍청해졌거나.... 정말 쉽게 풀었던 기억이 나는데 이제와서 고민하고 있으니 가슴이 조금 아프다 알고리즘 방식 먼저 예시의 15 10 로프 2개를 사용해서 버틸 수 있는 최대 중량은 최대 중량이 낮은 로프가 버틸 수 있는 중량, 즉 10 * 2 = 20이다. 이를 일반화하면 내림차순으로 정렬된 수 n1, n2, n3.. 2022. 11. 8. 이전 1 2 3 4 5 6 다음
