PS스터디
-
모각코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 / 프로그래머스 Lv2 소수 찾기PS 2022. 5. 28. 11:40
모각코 PS스터디 이번주 마지막 문제는 소수 찾기였습니다. 문제는 간단합니다. 문자열로 주어진 숫자열이 있고, 숫자들을 한번 or 0번 써서 만들어낼 수 있는 숫자들을 모읍니다. 그리고 그 숫자가 소수(prime number)라면 체크합니다. 총 체크된 수를 리턴합니다. 말 그대로 구현했는데요, 한번 같이 보시죠. 문제와 풀이 문제 링크 : 프로그래머스 Lv2 소수 찾기 이 문제의 원 출처 : nwerc.eu 09년도 아카이브 👇펼쳐서 코드와 해설 읽기 로직의 흐름은 이렇습니다. 일단 걸러낼 정보를 거릅니다. 저는 길이가 0인 경우 || 0을 전부 공백으로 치환했을 때 길이가 0이 되는 경우 || 그리고 문자열이 "1"인 경우를 걸렀습니다. 지금 말하면서 보니 길이가 0인 경우는 따로 체크하지 않아도 되..
-
모각코PS / 백준 17478 재귀함수가 뭔가요?PS 2022. 5. 25. 16:09
모각코 PS스터디 백준 문제들을 보다보면 가끔가다 재미용 문제(?)가 있죠. 이 문제도 약간 그런 느낌입니다. 부트캠프 커리큘럼이 재귀를 배울 차례라, 알고리즘을 정해주신 대장님께서 넣어주신 것 같아요. 웃으면서 재밌게 풀었습니다. ㅎㅎ 문제와 풀이 문제 링크 : 백준 17478번 - 재귀함수가 뭔가요? 👇펼쳐서 코드와 해설 읽기 설명할 로직이랄게 없죠?...ㅎㅎ 더 정리할 수 있을 것 같은데 재귀 은근 머리아파서... 대강 풀고 끝내자! 하고 대강 풀어버렸습니다. (...) import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); ..
-
모각코 PS / 백준 1475 방 번호PS 2022. 5. 25. 15:57
모각코 PS스터디 이번주는 지난주와 비슷한 난이도의 문제가 선정되었습니다. 아직 2번 문제까지밖에 못봤는데 오늘 남는 시간에 나머지도 얼른 풀어봐야겠어요. 그 전에, 먼저 풀어놓은 문제들부터 포스팅으로 남겨보려고 합니다. 문제와 풀이 문제 링크 : 백준 1475번 - 방 번호 👇펼쳐서 코드와 해설 읽기 로직의 흐름은 이렇습니다. 09까지의 숫자세트를 저장할 배열 변수 set을 만들어놓습니다. 입력받은 숫자열(int)의 길이를 체크해서, 길이만큼 for문을 돌 건데요. 한 바퀴 돌 때마다 앞에서부터 숫자 하나씩 가져옵니다. 가져온 숫자가 숫자세트에 존재하는지 체크합니다. 있으면 숫자세트의 잔여 개수를 하나 줄입니다. 줄일 잔여 수가 없으면 숫자세트를 하나 추가(09까지 하나씩 증가)하고 난 뒤에 잔여개수를..
-
모각코 PS / 카카오 2020 신입 블라인드 채용 1차 문자열 압축PS 2022. 5. 21. 16:47
모각코 PS스터디 왜인지 모르겠는데 PS는 하고 나서 포스팅 하는 걸 자꾸 까먹는다. 이번주 스터디 한 세 문제를 차례로 포스팅해보려고 한다. 문제와 풀이 문제 링크 : 카카오 2020 신입 개발자 블라인드 채용 1차 코딩 테스트 - 문자열 압축 해당 문제는 프로그래머스에서도 풀어볼 수 있다. 👇펼쳐서 코드와 해설 읽기 문자열 카테고리의 문제다. 로직 자체는 매우 직관적으로 떠올릴 수 있다. 머릿속으로 비교하는 그림이 대강 그려졌다. 대충 이렇게. 딱 봐도 뭔가 반복문을 겹겹이 돌아야할 것 같은 기분이 든다(표본 길이가 최대 1000이니까 낭낭히 돌아도 문제 없다). 그래서 코드를 짜기 전에 '어떤 반복문을 / 어떤 범위로 / 얼마만큼씩 키워나가면서' 돌 것인지 정리를 하고 구현을 시작했다..
-
모각코 PS스터디 / 백준 1783 병든 나이트PS 2022. 5. 21. 16:44
모각코 PS스터디 왜인지 모르겠는데 PS는 하고 나서 포스팅 하는 걸 자꾸 까먹는다. 이번주 스터디 한 세 문제를 차례로 포스팅해보려고 한다. 문제와 풀이 문제 링크 : 백준 1783번 - 병든 나이트 👇펼쳐서 코드와 해설 읽기 이 문제도 역시 그리디(greedy) 카테고리의 문제다. 얼핏 보면 탐색 같지만, 표본 수(2,000,000,000)를 보면 탐색으로 했을 때 무조건 타임아웃이 날 거란 걸 생각해볼 수 있다. 충족할 조건은 2가지다. 이동횟수를 최대화할 것. 이동방식을 충족할 것. (밟은 발판 갯수가 5개 이상 시에만) 나이트의 이동경로는 다음 네가지다 2U 1R 1U 2R 1D 2R 2D 1R 네 가지 이동을 완수하는 케이스를 먼저 생각해보기로 했다. 네 가지 이동을 완수하고 나서도 시작점에 ..