GOD동하님의 블로그

leetcode.com/problems/teemo-attacking/ Teemo Attacking - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Medium 이지만 Easy 급의 문제였던 난이도. Poisoning 되는 Duration이 안겹치도록만 total 값을 꺼내주면 됨 현재값, 다음값 차이보다 duration보다 크면 겹치지 않는다는거니까 독에 걸린 시간은 딱 duration 만큼. 현재값, 다음값 차이가 duration보다 크면 겹치는거니까 딱 겹..

leetcode.com/problems/largest-number/ Largest Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 주어진 숫자 리스트들을 이어붙였을 때 가장 큰 숫자를 찾으면 된다. 아이디어는 Sorting해서 큰 숫자 순으로 이어붙여주는건데 두자리수, 세자리수 숫자가 있는 부분에 대한 처리이다. 자바에서 compare 하는 로직을 앞/뒤 값 비교가 아닌 두 숫자를 앞 뒤로 붙인 값들을 (ex : 5, 40 -> 5 40, 40 5..

leetcode.com/problems/find-the-difference/ Find the Difference - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 그렇게 어려운 문제는 아니었다. s 문자열에서 임의의 문자를 하나 추가해서 셔플링시킨 t 문자열을 보고 어떤 문자가 추가된건지 return 해주는 문제다. 하나하나 대조하면서 찾으려면 O(N^2) 이 걸리니까 Linear 하게 풀 수 있는 아이디어가 필요했음 일단 소문자 a-z 로 제한이 되니까 a-z..

leetcode.com/problems/car-pooling/ Car Pooling - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 여행 동선과 승객들이 주어졌을 때, 한 차로 카풀이 가능한지 안한지를 판단하는 문제이다. 아래와 같은 제약조건이 주어지는데, 보시다시피 그냥 막 소팅하고 다 검색해도 Pass는 된다. Constraints: trips.length

leetcode.com/problems/multiply-strings/ Multiply Strings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 구현물로 Medium정도의 난이도이다 문자열 길이가 최대 109라 Number 형태의 곱셈이 아닌 각 자리수의 곱을 계산해야 한다. import java.util.Arrays; public class MultiplyString { public static void main(String[] args) { Syste..

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1697&sca=5030 JUNGOL | 순서찾기 > 문제은행 아주 먼 옛날 정올국이라는 국가가 있었다. 한재는 정올국에 대해 연구를 하는 학자인데, 어느날 정올국의 문서로 추측되는 문서가 발견되었다. 한재는 정올국이 사용하던 문자가 현재의 영어와 같다는 사실을 알고 있었으나, 사용되는 알파벳의 순서가 영어와 같이 "abc...z"순이 아니라는 사실을 본 문서를 통해 알게 되었다. 허나 정확한 순서를 알수가 없었고, 이에 대해 정올국에서 사용하던 알파벳의 정확한 순서를 알고자 시도하였지만 목표하던 바에 도달하지 www.jungol.co.kr 전형적인 순서를 찾기 위한 위상정렬 문제이다. 여기서 고민할..

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1361&sca=5040 JUNGOL | 자리 배치 > 문제은행 어떤 극장의 자리는 한 줄로 배치되어 있고 자리번호는 왼쪽부터 1에서 N까지 차례대로 매겨져 있다. 이 N개의 자리 중에서 N-1개의 자리는 지정석으로 모두 판매하고, 어떤 한 자리만 자유석으로 비워둔다. 지정석 표를 산 사람들은 아래 규칙에 따라서만 앉을 수 있다. 규칙) 사람들은 구입한 지정석 표에 적힌 번호의 자리에 앉든지, 그 자리의 바로 왼쪽이나 오른쪽의 인접한 자리에 앉든지, 또는 자유석에 앉을 수 있다. 예를 들어 설명해보자. 4개의 자리가 www.jungol.co.kr 자유석을 기준으로 왼쪽 오른쪽으로 나누는 것이 포인트 ..

https://koitp.org/problem/IOI_1999_FLOWER/read/ Korea Olympiad in Informatics Training Program 문제 꽃집에서는 꽃을 꽃병에 꽂아 진열한다. F개의 서로 다른 꽃이 있고, V개의 꽃병들이 일렬로 있다. 꽃병들은 움직일 수 없고, 왼쪽에서부터 순서대로 1, 2, ..., V번까지 번호가 매겨져있다. 또한, 꽃은 1, 2, ..., F번까지 번호가 매겨져있다. 하나의 꽃병에는 하나의 꽃만 꽂을 수 있는데, 모든 꽃은 자신보다 큰 번호의 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다. 어떤 꽃을 어떤 꽃병에 꽂느냐에 따라 아름다움의 정도가 다르다. 이 아름다움의 koitp.org 이것도 전형적인 DP 문제.. (전형적인 DP라고 하면 부분문제 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 오늘은 전형적인 DP 문제를 푼다 사실 조건이 크지 않아 전체 탐색을 해도 상관 없지만 이런 문제로 DP 연습을 하기 딱 좋다..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 오늘도 브루트 뽀쓰 먼저 복잡도를 생각해보자 문제에서 추출한 조건 1. 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다 -> 보드의 최대 칸 수는 N^2 개이다. 2. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것..