개발하는 햄팡이

https://www.acmicpc.net/problem/6236 풀이 과정문제 이해가 살짝 어려웠던 문제..원래 술술 읽으면 이해가 되는데 얘는 이해가 안돼서 종이에 쓰면서 해석했다..내가 문해력이 안좋은건지 글이 이상한건지..?중요한 부분만 뽑아보면 1. N일 동안 사용할 금액이 주루룩 있음2. 정확히 M번만 돈을 뺄 것임! (돈 아끼려고 하는거라서 M보다 적어도 됨)3. 한번 인출할때 무조건 k원을 뺄것임. 이는 고정 값이고 수중에 있는 돈이 하루를 보내기에 부족하면    원래있던 돈 전부 통장에 집어넣고, k원 인출이 정도 인 것 같은데 아마 다들 2번에서 뭐라굽쇼..? 하지 않을까...정확히 M번이라고 했는데 사실 이 부분은 문제 풀다보면 신경쓰지 않아도 됨왜냐하면 우리는 금액(k)을 최소화 하..

https://www.acmicpc.net/problem/2470 풀이 과정주어진 용액을 두개를 더해 0과 가까운 용액을 만드는 것이 목표. 이 문제의 알고리즘 분류에 이분탐색이 있는데사실 이분탐색을 사용하지 않고 투 포인터만 사용하면 쉽게 풀린다. 투 포인터로 푸는 방법은일단 입력값을 배열에 받아 정렬을 하고투 포인터를 이용해서 양 끝에서부터 용액을 선택한다음0보다 크면 right값을 줄이고,0보다 작으면 left값을 줄이면 된다.시간 초과도 되지 않는다.예전에 투 포인터로 풀었던 문제이지만 이분탐색도 곁들여서 풀면 좀 더 효율적으로 풀 수 있고지금 계속 이분탐색을 연습중이라서 이분탐색을 넣은 방법으로 다시 해볼려고 한다.이분탐색으로 푸는게 훨씬 어려운 방법인 것 같다...현재로써는 그냥 배열을 0부터..

https://www.acmicpc.net/problem/2295풀이 과정이분탐색을 연습하느라 해당 문제는 이분탐색으로 푸는 것을 알고선 시작..!문제를 읽어보면 집합안에 있는 숫자를 이용해서 집합 안에있는 또 다른 숫자를 만드는데그 중 제일 큰 값을 구하는 문제이다.그리고 중복도 된다. A+B+C=X가 되는 값을 구하면 되는데무작정 for문으로 돌면 답은 나오지만 문제 조건이 N이 1000개까지 나올 수 있어서연산량은 1000^3 = 1000,000,000 정도가 나오기 때문에 시간제한에 걸린다.그래서 다른 방법을 사용해야하는데A+B = X - C를 이용하는 방법이다. 일단 2중 for문을 돌면서 A+B로 나올 수 있는 모든 수를 Set에 저장한 후또 2중for문을 돌아서 X-C를 구한 다음 Set에 ..

https://www.acmicpc.net/problem/17232풀이 과정이 문제는 엄청 복잡하긴하지만 푸는 방법 자체는 간단하다.1. 시간이 1씩 지날때마다 생명배열을 누적합한 값을 기록하고 다시 배열을 쭉 보면서 해당 칸의 주변을 봤을때(2차원 배열의 누적합에서 구간에 따른 합을 구하는 방법을 사용해서 한번의 연산으로 구할 수 있다.) 다음 상태를 생존, 고독, 과밀, 탄생 4개중 어떤 상태가 될지 판단하여 변화를 주면 된다. 누적합을 매 시간마다 갱신한다는게 비효율적으로 보여서이 방법이 맞나 싶은 생각이 들긴했는데 딱히 떠오르는 다른 방법이 없어서그냥 그대로 구현을 했는데 통과한 문제. 구현에 중점이 되는 문제라서 좀 까다롭긴했다. 입력값을 받을때부터 처음엔 char 형태 그대로 저장을 할려고 했..

https://www.acmicpc.net/problem/19951풀이 과정이 문제는 1년전에 풀었었는데 지금 다시 보니 생각이 안나서 풀어보기로 했다.문제를 보면 흙파기를 명령이 들어왔을 때 바로바로 하는게 아니라 한번에 모아뒀다가 파겠다는건데명령마다 구간이 다르기때문에어디는 3만큼 파야될수도 있도 어디는 5만큼 파야될 수도 있고, 덮기도 해야해서 각 칸마다 변화량이 다르다는 것이 문제이다. 그래서 명령이 들어오는 그대로 모든칸에 변화를 줘버리면 결국 계속 파내고 덮고 하는거나 마찬가지인셈이라서한번에 끝내야한다는 생각은 문제를 읽자마자 바로 든다. 이걸 어떻게 n만큼 기록을 안하고 최대한 o(1)로 해결할까?변화한 값을 매 칸마다 기록하는게 아니라 시작과 끝만 적용되도록 기록하면 된다. 예시를 보면첫번..

https://www.acmicpc.net/problem/11404풀이 과정해당 문제는 이름에 대놓고 쓰여있듯이 플로이드-워셜 알고리즘을 이용하여 간단하게 풀 수 있는 문제이다.그런데 플로이드 워셜 알고리즘 공부한지가 오래되어서 다시 공부할 겸 풀어볼려고 한다. 플로이드 워셜 알고리즘을 대충 기억하고 있는 사람의 눈으로 이 문제를 봤을때n개의 도시와 한 도시에서 출발해서 다른 도시에 도착하는 m개의 버스가 있는데 각 버스마다 비용이 다르고...모든 도시의 쌍(a, b)에 대해서 a->b로 가는데 필요한 비용의 최솟값을 구해야한다..뭔가 배열에 최솟값을 계속 갱신해나가는 형태인 것 같다.  일단 입력을 받고 생각해보려고 했는데입력값이 a->b로가는 비용이 들어오는 형태라서입력을 받으면서 갱신하는 방식이 좀..

https://www.acmicpc.net/problem/2110저번에 풀었던 문제인 나무 자르기와 비슷한 문제이다.사실 공유기 설치는 이전에 한번 시도했었는데 실패하고 나무자르기라는 문제가 더 쉽다고 해서 나무자르기로 연습한번 하고 다시 풀어 볼려고 한다.↓ 나무 자르기 포스팅https://bitj-bitbox.tistory.com/18 [JAVA][백준 2805] 나무 자르기https://www.acmicpc.net/problem/2805  풀이 과정일단 문제를 읽어보면 절단기 높이 H를 지정해서 그 단위로 목재를 자르고 떨어져나간 목재를 가져가는 방식이다.그 목재가 M미터가 되도록 최소한 환경bitj-bitbox.tistory.com풀이 과정이게 신기한게 그냥 이 문제만 봤을땐 문제를 어떻게 풀어야..

https://www.acmicpc.net/problem/2805  풀이 과정일단 문제를 읽어보면 절단기 높이 H를 지정해서 그 단위로 목재를 자르고 떨어져나간 목재를 가져가는 방식이다.그 목재가 M미터가 되도록 최소한 환경을 생각해서 잘라간다는 내용인데...1. 일단 입력값 중 최대값을 찾아2. 그 값을 기준으로 점점 줄이든 늘리든 H를 설정하고3. 잘려나간 나무의 길이가 M이상인지 보는 문제 같다 H를 설정하는게 이 문제의 관건 같은데 나무의 최대 높이가 20억이기 때문에 길이를 하나씩 줄여가면서 보는건 좀 무리인 것 같다.최대 N* M 정도 될 것 같은데 그 값이 만만치가 않다.(근데 그냥 최대 높이가 20이라고 해도 20부터 1까지 1씩 줄여가면서 보는건 좀....노가다스럽긴 하다.. 이런 코드 ..

https://www.acmicpc.net/problem/16713   풀이해당 문제는 누적합을 이용해서 푸는 문제이다.주어진 구간 사이의 모든 원소를 XOR하는 문제인데 입력값 범위가 매우 넓어 값이 주어질 때마다 계산을 하면 시간초과가 발생한다. 따라서 처음부터 n까지 누적XOR연산을 한 값을 기록하고 0부터 ei까지 XOR값과 0부터 si-1까지 XOR한 값을 XOR하면 된다. 문제를 처음 보고 XOR연산에 대해 잘 모르고 있어서 누적합인지 뭔지도 몰랐다.그래서 XOR에 대해서 알아봤는데 XOR은 비트 연산 중 하나로 값이 같으면 0, 값이 다르면 1을 출력한다.XOR연산의 주요 성질을 살펴보면 사칙연산과 비슷하다.1. 자기 자신과 XOR하면 0이된다2. 0과 XOR하면 자기자신이 된다.3. 순서가..

풀이시뮬레이션 특...일단 문제가 잘 이해가 되지 않고....(한번 읽는 것으로는 잘 이해가 되지 않아서 여러번 읽었다.)구현 자체가 뭔가 할게 많고 조금 복잡한 문제!조건이 뭐가 많길래 패드에 조건을 하나하나 적어가면서 풀었다.  적은 내용 중 풀이 부분에는1. 득표 5% 미만 거르기2. 각 스태프마다 14개의 점수 계산해서 Map에 (점수 : 스태프idx) 저장3. Map 정렬 후 높은점수 부터 chip 주기 (14개의 점수까지만)이 정도를 기록하고 문제 풀기 시작!     일단 입출력을 받고 ArrayList에 저장을 하려고 했는데 입출력을 보니 A, B, C의 알파벳으로 받고 그 다음 득표수로 들어오길래 Candidate 클래스를 만들어서 ArrayList의 형태로 저장을 했다.그리고 N이 0부터..