potato's devlog

아주 쉽게 풀릴줄 알고 블로그 업로드를 하지 않으려고 했는데... 시간초과가 떴다. 근데, 이것저것 찾아보고 백준을 뒤져보니, 이 문제는 뭔가 swift로 풀 수 없는 문제 인것 같다는 판단이 내려졌다. (내 스스로) ⏰ 왜 시간초과 보류? 뭔가 이 문제는 시간초과 문제를 해결할 수 없을 것이라는 판단이 섰다. 왜냐면? 1. 일단, 나는 풀이과정에 잘못된 점을 찾지 못했다. 인터넷을 찾아보니 나와 동일한 방식으로 푼 C++, python등의 모든 코드들은 통과하는 것을 볼 수 있었다. 그렇다면 swift로 풀었을때 이 풀이과정이 안된다는 것은 말이 되지 않았다. 2. 시간복잡도는 O(N)인데, 100만이 통과되지 않는 것이 이해할 수 없다. 지금까지 스위프트로 푼 문제들로 보았을 때, 1초가 주어졌다면 ..

⚫️ 문제 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net ⚫️ 나의 풀이 풀이 방식은 바로 생각났다. 핵심은 -는 -끼리 곱했을 때 양수가 되고, 0이 입력되는 경우 minus인 수랑 곱해주면 개이득이라는 사실! input을 minus와 0, plus로 나눠서 받았고, 배열을 따로 만들어주었다. 우선 수를 곱해주는게 그냥 더해주는 것보다는 훨씬 이득이다. 그러므로, 주어진 input의 개수가 홀수인 경우, 큰수들은 묶어서 최대 수로 만들어주..

이것저것 채용 이슈 때문에 문제 풀이는 이 공주님문제는 4월말에 풀기 시작했지만 ㅋㅋㅋㅋ 풀이를 완료한 시점은 약 3주 후인 5월 중순,,,, (아 공주님 진짜 뿌셔버리는게 목표였는데 드디어 뿌셔서 없애버릴 수 있었다.. 다신 안풀어 이거) 자소서쓰고 최종면접보고 이것저것 하느라 코딩테스트에 집중하지 못했다. 다시 푸니까 재밌네? 그리고 확실히 refresh하고 다시 문제를 접하니까 더 잘풀리는 기분이다. 앞으로 다시 화이팅하자!! ⚫️ 문제https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 ..

실버2여서 쉬운 문제였지만, 왜 실버2야? 라는 말이 한번 툭 튀어나왔다 ㅎㅎ 짧지만 그래도 고민을 조금 했던 문제기 때문에 작성해놓음! 실버2답게, 그리고 그리디 답게 풀이를 생각해내는 순간 그닥 어렵지는 않았다~ ⚫️ 문제 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net ⚫️ 풀이 1️⃣ 첫번째 시도 시간초과가 났다. 제출 시간 보면 1분전이라고 뜨는데 ㅋㅋ 1분동안 천천히 채점하더니 88%에서 시간초과가 났다. 아무래도 데이터..

오랜만에 포스팅하네용, 이런저런 채용준비때문에 알고리즘을 잘 못풀었던것도 사실이지만, 그동안 푼 알고리즘 문제들은 대부분 파이썬으로 풀기도 했었고 깃허브에만 남기고... 이런저런 이유로 해서 ... 업로드 하지 않았었네요! 하하하하하 다시 화이팅.. ! 🍀 ⚫️ 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ⚫️ 나의 풀이 (두번째 푸는 것이긴 함!) 문제를 보자마자 생각난 BFS풀이방식이다. 그리고, 문제를 ..

기업 코딩테스트 연습을 위해 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://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억개..