728x90 알고리즘15 [알고리즘] 혼자 못 푼 문제 정리 - 도서관 BOJ 1461 도서관난이도 : (백준 난이도 기준) 골4사용 알고리즘 or 자료 구조 : 그리디 알고리즘, 정렬 처음 생각한 풀이1) 현재 위치에서부터 가장 가까운 곳을 찾아 해당 위치를 방문하며, 가지고 있는 책이 0개가 되면 0으로 가는 방식으로 풀었다.(그랬더니 터무니 없이 큰 숫자들이 나왔다.) 2) 반대로 절댓값이 큰 곳부터 가는 것으로 풀었더니 역시 답이 제대로 나오지 않았다.구글링 이후 풀이1. 먼저 위치가 양수인 책과 음수인 책을 따로 저장해준다. 2. 그 후, 양 쪽에서 절대값이 가장 큰 순으로 책을 M개 씩 묶는다. 3. 가장 큰 값만 방문하면 나머지는 0으로 돌아오는 길이나 가는 길에 방문하게 되므로 이동 거리는 가장 큰 값의 2배가 된다. 4. 마지막으로 양수나 음수 중, 가장 큰.. 2024. 6. 6. [알고리즘] 혼자 못 푼 문제 정리(암호코드) BOJ 2011 암호코드난이도 : (백준 난이도 기준) 골5사용 알고리즘 or 자료 구조 : 다이나믹 프로그래밍처음 생각한 풀이 위와 같이 문자열을 파싱해서 다이나믹 프로그래밍을 어떻게 잘 사용하면 될 것이라고 생각했는데, 도저히 방법이 떠오르지가 않았다...구글링 이후 풀이숫자가 1번부터 27번 사이에 있어야 알파벳으로 해석이 가능하다.(이거는 처음부터 생각했던 거) 이때 첫 숫자부터 보는데, 첫 숫자가 0이라면 잘못된 암호이므로 0을 출력하고 return 하고, 아니라면 1개를 dp 테이블에 추가한다. 두번째 숫자부터 1과 9 사이라면 이전 번의 dp 테이블과 암호 개수가 같으므로 더해주고, 만약 이전 숫자와 합쳤을 때 10과 26 사이에 있다면 2개 전의 dp 테이블의 암호 개수만큼 더 만들 수 .. 2024. 6. 6. [알고리즘] 크래프톤 정글 혼자 못 푼 문제 정리(공유기 설치) BOJ 2110 공유기 설치 난이도 : (백준 난이도 기준) 골4, (크래프톤 정글 기준) 중 사용 알고리즘 or 자료 구조 : 이분탐색, 매개변수 탐색 처음 생각한 풀이 처음에는 입력 받은 집의 위치를 정렬을 한 뒤, 시작 집과 끝 집에 공유기가 반드시 설치된다고 생각하고 이상적으로 생각했을 때 공유기끼리의 거리가 얼마나 되어야할지 생각했다. 입력값으로 생각하면 idealD = (house[N - 1] - house[0]) / (C - 1) 가 되어야한다. 그래서 시작 index를 0으로 두고 거리가 idealD가 되는 집이 있으면 해당 집의 index를 반환하고, 없으면 해당 위치에 더 가까운 집의 index를 반환하는 식으로 이분탐색을 구현하려 했다. 하지만 예제와 게시판에 올라온 반례가 모두 맞았.. 2024. 4. 19. [알고리즘] 크래프톤 정글 혼자 못 푼 문제 정리(탑 보기) 크래프톤 정글에서의 알고리즘 커리큘럼은 3주차까지만이다. 이후 문제들은 모두 C++로 풀었으며, 지금부터 정리할 알고리즘 글은 이후에 따로 알고리즘 스터디 중 혼자서 못 푼 문제들을 정리하는 글이므로 참고하길 바란다. BOJ 22866 탑 보기 난이도 : (백준 난이도 기준) 골3 사용 알고리즘 or 자료 구조 : 스택 처음 생각한 풀이 시간 제한과 입력 값의 크기를 봤을 때 반드시 전체 순회 한, 두 번 만에 끝내야된다고 생각을 했다. 그래서 0번 인덱스 ~ N - 1번 인덱스까지 스택을 1개 이용하고, N - 1번 ~ 0번 인덱스까지 스택을 1개 이용하여 순회 두 번만에 끝낼 수 있을 것이라고 생각하여 계속 고민해봤지만 방법이 떠오르지 않아 구글링을 통해 접근법을 찾아보았다. 구글링 이후 풀이 혹시나.. 2024. 4. 17. [알고리즘] 크래프톤 정글 3주차 / 알고리즘 中 혼자서 못 푼 문제 정리 11(외판원 순회) BOJ 2098 외판원 순회 난이도 : (크래프톤 정글 기준) 상, (백준 난이도 기준) 골1 사용 알고리즘 or 자료 구조 : 다이나믹 프로그래밍, 비트 마스킹, 백트래킹? 처음 생각한 풀이 아무리 생각해봐도 백트래킹을 이용한 방법만 떠오를 뿐, 어떡하면 dp 요소를 결합시켜야 하는지 조차 떠오르지 않아서 구글링을 해보았다. 구글링 이후 풀이 이 문제는 비트 마스킹을 이용하여 메모리 관리와 시간 관리를 모두 하는 문제이다. 물론 dp를 이용하는 것도 시간 관리를 하는 요소 중에 하나이다. 즉 비트 마스킹으로 dp가 차지하는 메모리를 상쇄시키고, 비트 연산과 dp로 시간 관리를 하는 문제이다. 만약 N이 충분히 작다면(비슷한 문제가 실버에 있다) 백트래킹을 통해 풀어도 되겠지만, 이 문제에서의 N의 최대.. 2024. 4. 10. [알고리즘] 크래프톤 정글 3주차 / 알고리즘 中 혼자서 못 푼 문제 정리 10(점프) BOJ 2253 점프 난이도 : (크래프톤 정글 기준) 상, (백준 난이도 기준) 골4 사용 알고리즘 or 자료 구조 : 다이나믹 프로그래밍 처음 생각한 풀이 처음에는 돌의 개수만큼의 길이를 가진 1차원 배열을 선언한 뒤, 건널 수 없는 돌의 인덱스에는 False 값을 할당해 밟을 수 없도록 했다. 그 후, 1번 돌부터 도착해야할 n번 돌까지 해당 돌까지 오는데 걸린 최소 횟수를 저장해서 마지막 돌까지 도착하도록 풀었다. 역시나 풀면서 허점을 느꼈던 만큼, 이 풀이로 80퍼까지밖에 가지 못했다. 반례를 찾아보니 어떤 돌까지 최소 횟수로 오면 끝에 도달하지 못하는 경우가 있고, 최소 횟수가 아닌 경우로 왔을 때 끝에 도달하는 경우가 있었다. 그래서 시간 초과를 각오하고 돌에 올 수 있는 최대 횟수를 정해놓.. 2024. 4. 10. 이전 1 2 3 다음 728x90
