potato's devlog

🟠 문제 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 아니 내가 문해력이 진짜 딸리는건가? 문제 이해가 잘 안돼 ㅋㅋㅋㅋ 어쨋든 이것도 문제 세번정도 정독하고 문제 이해 완료하고 풀이시작 🟠 1차원적인 약수구해서 더하는 풀이, 시간초과 🔖 당연히 시간초과 나겠는데? 당연하게 생각한 1차원적 풀이가, N보다 작은 수의 모든 약수를 구해서 합을 구하면 되겠구나 생각했다. 그러고 이렇게 ..

계속해서 좋은 기회로 내가 정말 원하는 회사의 코테를 여러번 보게 되었는데, 코테는 보면 볼수록 자신감이 떨어지고 확신이 안선다. 아직 내가 부족한 탓이겠지, 그래서 나는 기초부터 다시 다잡으면서 차근차근 코테를 공부해보려고 한다. ㅠㅠ 지금 푸는 문제도 너무 쉬워서 블로그 올려야할까? 하지말자! 했었는데, 이렇게 하나씩 미루게 되면, 더 안좋은 습관이 생길까봐 그냥 기초문제도 싹다 다시 올리면서 재정비를 하기로 했다! 화이팅. 🟠 문제 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은..

🟠 문제 링크 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 🟠 문제 풀이 start지점을 기준으로 dfs를 돌려줄 것이다. dfs는 두가지의 파라미터를 전달받을 건데, 앞부분은 (시작 행), 두번째 파라미터는 (현재 보고있는행)으로 기억하면된다. 그래서 이것을 돌려주면, 아래처럼 돌아가게 된다. 🟠 정답 코드 https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/11403_%EA%B2%BD%EB%A1%9C%EC%B0%BE%EA%B..

🟠 문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 🟠 나의 풀이 💡 무언가를 자르는 문제, 그리고 최대값을 구하는 문제이기 때문에 대충.. '이분탐색인가' 하는 feel이 왔다. 2번에서 정답인 200이 도출되었는데 왜 멈추지 않는가? 그 이유는, start와 end가 같아지는 지점을 찾아야, 해당 탐색을 모두 돌고나서 최대값을 찾은 것이므로, 2번에서 아무리 200이라는 결과가 도출됐어도 여기서 끝낼 ..

🟠 문제 링크 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 🟠 나의 풀이 아이패드로 그림을 그리면서 생각해보니, 주어진 입력값을 잘 정렬한다면, 순서대로 더해가면서 정답을 찾을 수 있을 것 같았다. 우선 많은 회의를 하기 위해서는, 동일한 시간에 시작하는 회의는 최대한 빨리끝나야한다. 이유는 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다. 그래서 시작시간을 순서로 먼저 정렬해준뒤, 종료시간을 기준으로 다시 한 번 정렬시켜주어야 한다. 정렬된 후에 prevEndTime이라는 변수에 끝나는 시간을 넣어주고, 각 회의마다 start 시간을 비교해준다. 시작..

🟠 문제링크 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 를..