내가 보려고 만든 PS 팁 - 1

[ 팁 1 - 들어오는 인풋이 매우 작은 경우 완전 탐색을 고려해보자. ]

 코드 테스트를 하다보면 인풋이 매우 작은 경우가 있다. 예를 들어 특정 규칙으로 글자를 만드는데 8자리까지만 되는 경우, 이런 경우는 완전탐색으로 풀어도 시간 제한을 벗어나지 않는다. 문제를 풀 때, 낮은 케이스를 올려놓고 모든 경우의 수를 탐색하는지 출력문으로 확인해보고 제출하는 걸 잊지말자. 

 

프로그래머스: 모음사전

프로그래머스: 피로도

 

[ 팁 2 - 들어오는 인풋이 억 단위인 경우엔 이분 탐색을 고려해보자. ]

 앞의 경우와 다르게 인풋이 20억 같이 엄청난 값들이 들어오는 경우도 있다. 이 때는 이분 탐색을 고려해보는 게 좋다. 이런 건 N이상인 알고리즘으로 풀라는 게 아니기 때문이다. 따라서 특정한 기준을 통해 해당 값보다 작은지 큰지만 판별해서 이분탐색을 하면 된다. 이 때 주의할 건 이분탐색을 하고 start값, end값 가지고 테스트 케이스보다 많은 케이스를 만들어보고 확인함으로써 경계 체크를 주의하자.

 

프로그래머스: 입국심사

백준 알고리즘: 랜선 자르기

 

[ 팁 3 - 그래프에서 전체 경로 최소 비용이 나온다면 크루스칼 알고리즘을 생각해보자.  ]

 그래프에서 전체 간선 중 필요한 간선만을 남겨놓고 제거해야 될 때가 있다. 그렇게 해서 최소 비용으로 이동할 수 있게 다리 건설 비용을 최소화해라 같은 문제가 나온다. 이 때는 a-b, b-c, c-a로 순환이 있는 경우가 있을텐데 3개 중 제일 비용이 큰 1개를 제거하라는 문제이다. 이때 크루스칼 알고리즘을 사용하면 쉽게 해결할 수 있다. 

 

프로그래머스: 섬 연결하기

 

[ 팁 4 - 현재 순회하고 있는 리스트 내부의 값을 빼고 다음으로 넘어가야 하면 값을 빼는 걸 모든 순회가 끝나고 하는 걸 고려해보자. ]

 여러 문제를 풀면서 가끔씩 특정한 값들을 순회하며 내부 값을 제거하는 경우가 있다. 이 가끔씩 그냥 아무 생각없이 지우는 경우가 있는데 그러면 리스트 값의 길이 바깥으로 넘어가서 index 오류를 내뱉는다. 그럴 땐 값을 지우는 걸 최대한 뒤로 미뤄서 해보자. 

 

프로그래머스: 체육복

 

[ 팁 5 - 특정한 블럭 모양이 있고 넣을 수 있는지 확인할 땐 블록 내부 원소들을 정렬하자. ]

 특정한 블록이 있고 그 블록에 맞는 빈칸이 있으면 끼워넣는 문제들이 있다. 이런 경우, 해당 블록을 나타내는 리스트가 있을텐데 이를 정렬한 뒤 맨왼쪽위 꼭지점이 0,0이 되게 값을 조정하자. 그래야지 나중에 맞는지 확인할 때 중간에 좌표 신경 쓸 필요 없이 처리가 쉽다. 

 

프로그래머스: 자물쇠와 열쇠

프로그래머스: 퍼즐조각 채우기