potato's devlog

🟠 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🟠 문제 풀이 1. k진수로 바꾸면서 동시에 배열로 만들어주는데, 0으로 split 해서 넣어주기 2. split해서 넣어준 배열에서 하나씩 꺼내서 소수 판별 - 0은 split 단어이기 때문에 pass - 1은 소수가 아니기 때문에 pass - 소수 판별해줘서 소수라면 true, 아니라면 false 3. 소수이면 count += 1 해줌 🟠 소스코드 https://github.co..

🟠 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/42889\ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🟠 시간초과 코드 https://github.com/deslog/Algorithm/blob/main/Algorithm/Programmers/kakao_%EC%8B%A4%ED%8C%A8%EC%9C%A8/filter%EC%82%AC%EC%9A%A9_%EC%8B%9C%EA%B0%84%EC%B4%88%EA%B3%BC.swift GitHub - deslog/Algorithm Contribut..

🟠 문제링크 https://www.acmicpc.net/problem/1679 1679번: 숫자놀이 홀순이(holsoon)와 짝순이(jjaksoon) 둘이서 숫자 게임을 한다. 예를 들어, 정수 1과 3이 주어지고, 이 둘을 통틀어 5번까지 마음대로 사용하여 그 합을 구하여 1,2,3,…을 만드는 놀이다. 이 경우 먼저 www.acmicpc.net 🟠 풀이방식 인터넷을 보니까 dp, dfs 등 다양한 방식으로 풀 수 있는 문제 같았다. 나는 그냥 가장 먼저 떠올랐던 dp 로 문제를 풀었다. dp 에서 가장 중요한 것은, 해당 인덱스에 어떤 value값을 넣느냐를 결정하는게 가장 중요하다. 나또한 여기서 어떻게 넣을지 많이 고민했던 것 같다. 우선 dp[i] 라고 쳤을때, i번 더해서 나올 수 있는 수들을..

🟠 문제 링크 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 🟠 문제 풀이 방법 처음에 내가 접근했던 방법은, 2차원 dp 였다. 이렇게 끝가지 밀고 나갔어도 풀릴거 같긴했다. 근데, 왜 자꾸 생각이 막히지? 처음에는 이렇게 2차원 dp로 문제를 풀려고 했다. 근데 굳이 시작위치를 표현하면서 배열을 거대하게 만들 필요가 없다고 판단되었다. 어차피 도착위치에서 shortcut을 구하면 되기 때문에,, 굳이 시작위치까지 기억해야할 필요..

🟠 문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🟠 풀이 방법 어렵다... 역시 아직 골드는 무리인가 ㅠㅠ 그래도 '2차원 dp를 이용해야되는구나!'를 눈치채긴 했다. 단,, 어떻게 이용하느냐를 몰랐지 ㅠㅠ 인터넷을 찾아보니까, 해당 문제는 굉장한 well-known 문제라고 한다. (학교 알고리즘 수업에서도 자주 등장하는 아주 단골이라는?! (나 비전공자 ㅠㅠ )..

🟠 문제 링크 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 🟠 문제 풀이 방법 (1) - 수학적인 풀이 수학적으로 접근하면 사실 굉장히 간단하게 풀린다. 첫번째 예제인 18로 예를들어보자. "5로 막 나누다가 마지막에 3의배수가 되는지 찾아보면 최소값 찾을 수 있지않아?" 라고 생각할 수 있다. 나또한 그랬었고 ^__^ 근데 예제 5번을 보면, 11은 5kg / 5kg 하고 1kg가 남게되어서 -1을 출력하는게 아니라, 3kg / 3kg / 5kg 로..

🟠 문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 🟠 문제 풀이 아이디어 0과 1과 2를 구별해야한다는 점이 어려웠다. 역시 골드는 나에게 무리인것인가 ㅠㅠㅠ 실력언제늘어 늘고는 있니? 고민고민고민 하다가 도저히 감이 잡히지 않아서 어떻게 풀었나 참고를 해보았는데 풀이 방법은 다음과같았다. BFS는 어떻게 구현할까 바이러스를 퍼뜨리는것이 목표기떄문에 바이러스를 queue에 넣어주고, 사방면에 위치한 값이 0 이라면, 2로 입력해주면서 BFS 를..

🟠 문제링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 🟠 문제 풀이 아이디어 가장 기초적인 dp 문제중 하나였다. 하지만 가장 중요한것은, 생각을 반대로해야한다는 것이었다. "처음부터 계단을 어떻게 올라가지?" 생각보다는, "최종 도착지기준으로 봤을때, 어디서 올라왓찌?"를 고려해봐야한다는 것이다. 연속으로 3칸의 계단을 밟을 수가 없기 때문에, 도착지 기준으로 올라올 수 있는 방법은 아래 그림처럼 딱 두가지 방법이다. 이렇게 dp 점화식을 유도해냈..

🟠 문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 🟠 문제 풀이 아이디어 가장 기초적인 dp문제로 이미 풀어봤던 문제라 어렵게 생각하지 않았다. dp 에는 현재위치의idx-1 까지의 합과 해당 arr[idx] 값을 비교해본 후 최대값을 넣어준다. 앞에서부터 차례대로 차곡차곡 더해진 값에 현재값을 더하는게 더 큰지, 현재값만 바라보는게 더 큰지 확인하는 것이다! 🟠 전체 소스코드 https://github.com/deslog/Algorithm..

✅ 문제 링크 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net ✅ 문제 풀이 아이디어 문제가 굉장히 난해하게 생겼기 때문에 ,,,, 처음엔 BFS 문제인지 감이 안잡혔다. 인터넷을 찾아보니, 이 문제의 핵심은 다음과 같았다. 가운데 구멍뚫린 부분은 신경쓰지 않아도 된다. 어차피 BFS 로 탐색을 (0,0)부터 시작하게되면, 구멍으로 접근이 불가능하다. 외부 공기자리부터 탐색을 시작하면 어차피 구멍 내부로 접근할 수 없기떄문!! 가장자리는 항상 외부공기로 둘러쌓여있..