PS
-
최소신장트리: 백준 9372 상근이의 여행PS 2022. 7. 23. 14:38
최소신장트리: 백준 9372 상근이의 여행 간단한 팁을 하나 남겨보고자 포스팅을 합니다. 제목에 쓰여있듯이 신장트리(spanning tree)라는 것에 대한 이야기예요. 문제와 풀이 문제 링크 : 백준 9372 - 상근이의 여행 👇펼쳐서 코드와 해설 읽기 문제를 보면 즉시 BFS로 풀어야겠다는 생각이 들죠. 최소신장트리에 대해서 모르는 상태였기 때문에 저도 그랬습니다. 신장 트리란 모든 정점을 포함하고 있는 그래프를 말합니다. 그리고 모든 정점을 가장 짧은 경로로 연결하는 그래프를 최소 신장 트리라고 합니다. 물론 몇가지 제약이 있지만 일단 개념은 그렇습니다(무향 그래프에서 가중치나 비용이 특별히 없을 때). 최소신장트리가 그려질 때에는 한 그래프에서 여러 형태로 존재할 수 있고, Self loop는 불..
-
모각코PS / 카카오 3차 방금 그 곡PS 2022. 7. 23. 11:31
모각코 PS스터디 알고리즘 스터디가 10주차를 맞아 방학에 들어갔습니다.😃 그간 많은 문제를 처음 접해보면서 참 즐거운 시간이었네요. PS 포스팅을 안한지 오래 되었는데... 방학을 기념해서 오랜만에 올려보려고 해요. :) 늘 그렇듯 문제는 알고리즘 대장님께서 선정해주셨습니다.😃 문제와 풀이 문제 링크 : 프로그래머스 Lv2 - 방금 그 곡 원 출처 : 카카오 블라인드 신입 공채 3차 - 4번 문제 방금 그 곡 👇펼쳐서 코드와 해설 읽기 여러가지 제약 조건을 주의하면, 로직 자체는 크게 어려울 것이 없습니다. public class Nick { public String solution(String m, String[] musicinfos) { String result = "(None)"; // 반환값 i..
-
모각코PS / 백준 2110 공유기 설치PS 2022. 6. 22. 15:01
모각코 PS스터디 지난주 알고리즘 스터디 내용 중 대표적인 한 문제를 정리해보려고 합니다. 늘 그렇듯 문제는 알고리즘 대장님께서 선정해주셨습니다.😃 문제와 풀이 문제 링크 : 백준 2110번 - 공유기 설치 👇펼쳐서 코드와 해설 읽기 진짜 할 말이 많은데... 일단 넋두리 & 이분탐색 tip은 마무리로 넘겨두고... 로직의 흐름 부터 보시죠. 로직의 흐름은 이렇습니다. 표본 수가 매우 큽니다. 대강 눈으로만 봐도 판단 횟수가 10억 * 20만이니까, 그리디로는 택도 없습니다. logN의 시간 복잡도로, 대강 열댓번 정도의 탐색으로 끝내야할 것 같습니다. 이를 위해 이분탐색으로 풀 것입니다. 정확히는 파라메트릭 서치를 적용할 거에요. 지금 궁금한 건 거리죠. 최소 거리와 최대 거리를 탐색 범위로 두면 됩니..
-
모각코PS / 프로그래머스 Lv3 단어 변환 & Leetcode 127 Word LadderPS 2022. 6. 11. 17:23
모각코 PS스터디 그래프 탐색 세 번째 문제인 '단어 변환'입니다. 이 문제는 Leetcode 127번 Word Ladder 문제와 완전히 동일해요. 단어들이 배열로 주어지는데 곧바로 그래프가 떠오른다면...? 어느 정도 그래프 탐색 카테고리의 문제에 익숙해졌다고 봐도 되는 거겠죠?😇 그것만 빨리 캐치한다면 특별히 어려운 점은 없습니다. 아, BFS 탐색의 레벨을 세는 꿀팁이 있으니까, 그 부분이 필요하시다면 참고하세요! 그럼 문제 풀이로 들어가보죠! 문제와 풀이 문제 링크 : 프로그래머스 Lv3 - 단어 변환 문제 링크 : LeetCode Hard - Word Ladder 👇펼쳐서 코드와 해설 읽기 왜 단어를 보고 그래프를 연상할 수 있을까요? 문제의 제약조건은 사실상 이런 말로 해석이 ..
-
모각코PS / 백준 2178 미로 탐색PS 2022. 6. 11. 16:32
모각코 PS스터디 그래프 탐색 두 번째 문제인 '미로 탐색'입니다. 문제의 제약조건을 보면서 어떤 알고리즘으로 접근하면 좋을지 힌트를 얻을 수 있기도 하죠? 표본 수가 적고, 시간 제한이나 메모리가 상대적으로 넉넉하고, 좌표나 맵 같은 것이 주어지면 그래프가 떠오르는 것 같습니다. 그리고 각 탐색로의 길이를 비교하거나, 특히 가장 빠른 탐색 경로를 찾아야 하는 경우에는 BFS를 선택하는 편이 '대개' 유리하겠죠. 모든 경로를 다 들어가보고 길이를 기록해뒀다가 제일 짧은 길이를 리턴하는 것보다, 모든 경로를 동시에 진행하다가 한 경로가 끝에 다다르면 나머지를 더이상 탐색하지 않고 리턴하는게, 탐색 횟수가 훨씬 적을 거니까요. 이번 문제가 그런 스타일의 문제였습니다. 문제와 풀이..
-
모각코PS / 백준 1260 DFS와 BFSPS 2022. 6. 11. 16:08
모각코 PS스터디 지난주는 너무 바빠서 PS스터디 포스팅을 못 올렸네요. 백트래킹이었는데, 나중에라도 시간이 나면 올려보려고 합니다. 이번주 5주차 PS스터디 문제 주제는 그래프 탐색이었습니다. 세 문제 모두 DFS/BFS 문제였어요. 한 문제 씩 보면서 그래프 탐색에 대한 공부 방법, 주의점, 그리고 잡담 같은걸 좀 해볼게요. 그래프 탐색 문제는 흔히 '템플릿'이라고 하는 코딩스타일이 존재하죠. 조금만 구글링 해봐도 수두룩해요. 물론 제 블로그에도 있고요 ㅋㅋ. 그걸 보고 바로 원리를 이해할 수 있다면 좋겠지만 이해가 안된다면, 템플릿을 외워서라도 문제를 풀어보면서 익숙해지는 것도 좋은 방법 같습니다. 푸는데에 성공했다면 IDE로 옮겨서 디버깅을 실행해두고 한 스텝씩 따라가며 공부하는 거..
-
동전 교환 알고리즘: 주어진 화폐로 특정 금액 만드는 경우의 수 구하기PS 2022. 6. 2. 17:37
동전 교환 알고리즘 문제 : 경우의 수 구하기 동전 교환 알고리즘 문제는 다이나믹 프로그래밍 영역에서 다양한 바리에이션으로 출제되는 문제입니다(저도 몰랐어요. 이번에 DP 공부하면서 알게되었습니다. 코린이라서...). 아래에 해설할 문제는 '몇 종류의 화폐가 주어지고, 이 화폐들을 조합해서 특정 금액을 만들 수 있는 경우의 수'를 구하는 유형의 문제입니다. 해설을 보시고 DP에 익숙해져서 또 다른 동전 교환 알고리즘 문제와 DP 문제들도 쉽게 풀 수 있게 되면 좋겠습니다! 해설 영상 영상이 좀 많이 길어요. 왜냐면 제가 겨우겨우 이해를 했기 때문에... 저와 같이 이해가 느리신 분이 계시면 도움이 되시라고 최대한 자세하게, 반복하면서 설명을 해서 그렇습니다. 중간 중간 멈춰가면서 생각해보시..
-
모각코PS / 프로그래머스 Lv2 소수 찾기PS 2022. 5. 28. 11:40
모각코 PS스터디 이번주 마지막 문제는 소수 찾기였습니다. 문제는 간단합니다. 문자열로 주어진 숫자열이 있고, 숫자들을 한번 or 0번 써서 만들어낼 수 있는 숫자들을 모읍니다. 그리고 그 숫자가 소수(prime number)라면 체크합니다. 총 체크된 수를 리턴합니다. 말 그대로 구현했는데요, 한번 같이 보시죠. 문제와 풀이 문제 링크 : 프로그래머스 Lv2 소수 찾기 이 문제의 원 출처 : nwerc.eu 09년도 아카이브 👇펼쳐서 코드와 해설 읽기 로직의 흐름은 이렇습니다. 일단 걸러낼 정보를 거릅니다. 저는 길이가 0인 경우 || 0을 전부 공백으로 치환했을 때 길이가 0이 되는 경우 || 그리고 문자열이 "1"인 경우를 걸렀습니다. 지금 말하면서 보니 길이가 0인 경우는 따로 체크하지 않아도 되..