본문 바로가기

전체 글1104

[종만북] LUNCHBOX - Microwaving Lunch Boxes (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-LUNCHBOX 풀이 N개의 Lunch Box가 있고, 각각 전자렌지에 돌리는 시간 M과 먹는시간 E를 가지는 상황이다. 여기서 고정인 부분은 전자렌지 돌리는 시간 M는 무조건 N개의 M을 전부 더한 시간만큼이 필요하다. 반면에 먹는시간 E는 각 M이 끝날때마다 시작된다. 예를들어 아래와 같은 입력을 보자. 1 3 1 3 2 10 4 1 순서대로 진행해본다면 아래와 같이 진행된다. 사실 저 순서대로 처리하는게 풀이인데, 결국 M의 총합은 항상 고정이고, E가 시작하는건 각 M이 끝난 이후이므로 E가 긴 녀석을 최대한 빨리 먹기 시작해서 처리하는게 무조건 이득이다. 따라서 E값 내림차순으로 정렬한 후 (E가 동일할 시 M을 내림차순으로.. 2023. 4. 14.
[자바] 백준 15025 - Judging Moose (java) 목차 문제 : boj15025 필요 알고리즘 구현 문제에서 제시된 대로 구현해주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 해석만 잘하면 제시된 대로 풀면 된다. 로직을 정리하면 다음과 같다. 1. L과 R을 입력받는다. 2. L과 R이 둘 다 0이면 "Not a moose" 3. L과 R 중 큰 값을 B라고 해보자. 4. L == R 이라면 "Even [B*2]"를 출력한다. 5. 그렇지 않다면 "Odd [B*.. 2023. 4. 14.
[자바] 백준 3359 - 사각 사각 (java) 목차 문제 : boj3359 필요 알고리즘 동적 계획법(DP) 사각형을 순서대로 보면서, 점화식을 만들어 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 완전 탐색으로 한번 생각해보자. 각 사각형은 a변이 위로 올라오게 놓거나, b변이 위로 올라오게 놓을 수 있으므로 O(2^n) 으로 구할 수 있다. 이 때 n이 최대 1000 이므로 완전 탐색으론 풀 수 없음을 알 수 있다. 그렇다면 우선 생각해볼.. 2023. 4. 13.
[자바] 백준 18352 - 특정 거리의 도시 찾기 (java) 목차 문제 : boj18352 필요 알고리즘 너비 우선 탐색(BFS) 일반적인 BFS 탐색에서, 최단 거리에 목적지를 도착하는게 아니고 특정 거리인 지점을 찾는다는점만 다르다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 잘 모른다면 'BFS 알고리즘 (너비 우선 탐색)' 글을 참고해보자. 일반적인 BFS 알고리즘으로 구현해주면 되는데, 목적지까지의 최단 거리를 구하는게 아니라 특정 거리인 위치를 찾는다는 점이 다.. 2023. 4. 12.
[자바] 백준 16200 - 해커톤 (java) 목차 문제 : boj16200 필요 알고리즘 그리디, 정렬 그리디 규칙을 잘 생각해보면 의외로 쉽게 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 팀을 어떻게 정하는게 항상 최선의 선택일지 규칙을 정해야 한다. 얼핏 X값이 큰 학생들부터 골라서 선택해야 각 팀의 인원이 많아지므로 팀의 수가 줄어든다고 생각할 수 있는데, 어차피 X값은 고정된 것이고 바뀔 수 없으며, 모든 학생은 하나의 팀에 소속이 되어야만.. 2023. 4. 11.
[종만북] POLY - 폴리오미노 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-POLY 풀이 문제에서 제시된 규칙은 결국, 세로야 어떻든 가로로 선을 그었을 때 빈 곳이 있으면 안되고 또 전부 붙어있어야한다는 의미가 된다. 따라서 n개를 행 1개~행 n개 에 걸쳐 각 행에 몇 개씩 배치할 것인지로 바꿔서 생각하면 된다. 그리고 2개의 행을 봤을 때, 두 행에 대해 만들 수 있는 경우의 수는 '행1의 블록 수 + 행2의 블록 수 - 1' 이 된다. 예를들어 각 행에 3개씩 배치했을 경우 나올 수 있는 경우의 수는 3+3-1 = 5 이다. 아래 경우들과 같다. 따라서 각 행별로 현재 남은 블록의 수를 '1개부터 남은 블록의 수'로 배치하면서 위에서 얘기한 경우의 수를 바로 직전 행의 블록수와 함께 계산해보면 된다... 2023. 4. 10.
[종만북] NUMB3RS - 두니발 박사의 탈옥 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-NUMB3RS 풀이 예제 입력의 첫 번째 테스트케이스를 그래프로 그려보면 아래와 같다. 탈출 전 확률이 1(100%)이라 한다면 이후 간선을 따라, 간선이 존재하는 만큼 확률이 나뉘어져서 들어가게 된다. 탈출 전일 때 0에서 시작하므로 0은 1로 시작하고, 탈출 1일차에 0에서 갈 수 있는 간선이 1,2,3 이므로 1/3씩 나뉘어 들어간다. 그리고 2일차에 1과 3에 있던 1/3은 0으로 다시 돌아오고, 2에 있던 1/3은 0과 4로 1/6씩 나뉘어 들어가게 된다. 따라서 2일차에 0에 위치는 5/6, 1,2,3 위치는 0, 4는 1/6이 된다. 이런식으로 일차별로 계속 진행한 후 q에 따라 출력해주면 된다. 코드 : github i.. 2023. 4. 10.
[자바] 백준 20920 - 영단어 암기는 괴로워 (java) 목차 문제 : boj20920 필요 알고리즘 정렬, 해시를 사용한 집합과 맵 해당 단어가 몇 번 나왔는지 알기 위해 HashMap을 쓸 수 있어야 한다(다른 방법들도 있긴하다). 그 외에는 문제에서 제시된 방법대로 정렬이 가능한지 묻는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 Word라는 클래스를 만들고 name이 단어, cnt가 해당 단어가 몇 번 나왔는지를 뜻하도록 했다. 우선은 동일한 단어가 .. 2023. 4. 9.
인프런 김영한님 머그컵 득! 3월에 인프런에서 이벤트로 준 김영한님 머그컵이 도착했어요. 머그컵 자체를 쓸일은 잘 없어서 전시용(?)으로 잘 간직할 예정입니다! 2023. 4. 8.
[자바] 백준 23740 - 버스 노선 개편하기 (java) 목차 문제 : boj23740 필요 알고리즘 정렬, 스위핑 스위핑을 통해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 겹친다는 부분을 어떻게 알 수 있을까? 노선A의 e가 노선 B의 s 이상이고, 노선 B의 e가 노선 A의 s 이상이라면 겹친다고 볼 수 있을 것이다. 이 때, 무조건 s가 증가하는 순서대로 정렬해두고 확인해본다고 해보자. s가 더 작은 쪽이 노선 A라고 한다면 이후 겹친다는 판단.. 2023. 4. 8.

티스토리툴바