potato's devlog

기업 코딩테스트 연습을 위해 python으로 문제풀이 하였습니다. 😅 ⚫️ 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net ⚫️ 나의 풀이 내가 처음에 한 생각은 다음과 같다. dp[i] 에 i를 만들기 위한 경우의수를 넣고자 했다. 근데,,, 규칙도 보이지 않을 뿐더러 주어진 수로 어떻게 경우의수를 세어야하는지 감이 안왔다. 예를들어, i = 5 이고 주어진 수가 1, 2, 5 라면 5에서 1을 빼면서 1이 몇개 필요할지 세어주고, 또다시..

기업 코딩테스트 연습으로 Swift가 아니라 Python으로 풀이했습니다 😅 ⚫️ 문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net ⚫️ 나의 풀이 이전에 보고와야할 것이 있다. '가장 큰 증가하는 수열'은 주어진 수열 속에서 '증가하는 부분 수열'을 찾는 문제다. LIS라고 불린다. https://didu-story.tistory.com/236 [알고리즘] (Swift) 최강 증..

⚫️ 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ⚫️ 나의 생각 우선, 마지막 계단을 꼭 들러야한다고 한 조건이 눈에 보였다. 그럼? 결국 dp[마지막계단]을 출력했을때의 최대값을 구하면 되겠구나! 생각했다. 이전에 dp 유형을 조금 풀어본적이 있어서 이 문제를 보고 dp배열에 어떤 것을 넣어주어야하는지 감이 왔다. 나는 dp를 이렇게 정의할것이다. dp[i] = i번째 계단까지 올라가는데 최대 점수 이렇게 정의를 해놓고 그림을 그려서 생각해봤다..

무려 골드2라서 엄청 겁먹었던 문제... 엄청 어려웠다기보다는, 문제를 읽고 그것을 해석하는 과정까지가 어려웠다. 끄것만 생각하면 바로 풀리는 문제? 하지만, 이 문제를 풀면서 궁금한점이 생겼다. 결과값을 왜 다 찍어봐도 모르겠지? ⚫️ 문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net ⚫️ 나의 풀이 처음에 보자마자 엥 이게 왜 골드? 싶었다. 그러는 순간 조건을 봤는데 최악의 경우가 100억ㅇ이 나오는게 아..

⚫️ 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43236?language=swift 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚫️ 나의 풀이 이 문제 또한 이분탐색으로 분류가 되어있었기 때문에 파라메트릭 서치로 풀어야겠다, 싶은 감이 왔던 거지 그게 아니라면 알기 쉽지 않을 것 같다. 하지만 가장 먼저 눈에 보이는건 10억이라는 어마어마한 범위. 이것만이 이분탐색일 것이다 ~ 하는 감?을 줄 뿐이다. 처음에는 역시나, 문제를 보자마자 어떤 것을 이분탐색의 대상으로 주어야할지 너무 고..

이분탐색과 파라메트릭 서치의 차이점과, 어느 때에 사용하면 좋은지에 대해서 명확하게 알고 넘어갈 필요가 있다고 생각된다. 맨 밑부분에 이 문제가 왜 파라메트릭 서치로 풀리는지에 대해서 생각을 적어놨다. 그것을 항상 기억하자! ⚫️ 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚫️ 나의 풀이 이거 바로 직전에 푼 문제와 매우 비슷햇기 때문에 금방 풀 수 있었다. (바로 이전에 풀었던 문제 아래 백준의 공유기설치) https://didu-..

⚫️ 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ⚫️ 나의 풀이 ◾️ 처음에 생각한 풀이 어떤 것을 기준으로두고 탐색할것인가가 고민스러웠던 문제였다. 처음에 무작정 생각한 풀이 방식은, C개의 공유기를 설치해야하니, N개의 집에서 C개의 집을 고르는 모든 조합을 고려한 뒤 거리를 볼끼? 싶었는데 ㅋㅋㅋㅋ 말도 안됐다. 주어진 조건을 보자 입력 조건은 이렇다. 일단 집은 최대 10억개..

⚫️ 문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net ⚫️ 나의 풀이 보자마자 이코테 책에 있는 '파라메트릭 서치' 문제의 대표유형인듯 싶다. 어려운 문제는 아니지만, 풀이를 하다가 한가지 놓치고 생각한 부분이 있어서 기록하고자 블로그 글을 작성한다. ◾️ 놓치고 생각한 부분 처음에 생각했을 때, start는 주어진 지방예산의 최소값, end 는 주어진 지방예산의 최대값으로 설정하면 되겟구나 싶어서 그렇게 구현했다. 근데, 이렇게 하..

이분탐색을 진행할 때는 존재여부를 확인할때는 괜찮지만, 개수를 세어야할 경우에는 탐색하고자하는 배열 내부에 중복값이 있으면 안된다. 그럴때를 대비해서 upper bounds 방법과 lower bounds 방법을 잘 알아두어야 문제를 맞출 수 있을 것 같다. ⚫️ 문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ⚫️ 나의 풀이 아 그리고 문제 풀고 발견한건데, dictionary를 사용하면 진짜 개 간단하게..

⚫️ 이 글을 작성하는 이유 아주 기초적인 문제를 풀다가, 시간초과가 발생했다. 아주 기초적인 것을 내가 간과하고 풀었기 떄문! 꼭 기억해두기 위해서 포스팅을 작성한다. ▪️ 백준 1181번 - 단어정렬 문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 이 문제를 풀면서 무슨 문제가 있었냐구??? 바로, 시간초과를 마주쳐버린 것! 아무리 살펴봐도, 이유는 array를 사용해서 '중복처리'를 해주는 과정에서 시간초과가 난 것 같았다..