Algorithm 뽀개기

네이버 코테 전날 알고리즘을 1 도 모르면서 벼락치기 라도 해보겠다고 BFS 문제를 허겁지겁 풀다가 토마토에서 막혀버렸다... 밤은 늦었고 내일 코테는 어차피 글렀고... 어차피 경험 삼으려고 신청한 거고... 하며 답답한 마음으로 집에 가는데 서러워져서 울었다 ㄹㅇ임그니까 BFS 란 그래프나 트리에서 가까운 노드부터 탐색해 나가는 알고리즘이다. BFS 는 같은 레벨 (거리) 에 있는 노드를 먼저 다 본 다음, 그 다음 레벨로 넘어간다. BFS 알고리즘을 작성할 때의 특징큐(Queue) 자료구조 사용최단 거리 문제에 자주 쓰임방문한 노드를 다시 방문하지 않도록 visited 배열을 사용동작 방식시작 노드를 큐에 넣고 방문 표시큐에서 노드를 꺼냄해당 노드와 연결된 (방문하지 않은) 노드들을 큐에 추가하고 ..

코딩테스트 준비를 하기 위해 인턴이 끝나고 오랜만에 머리 쓰는 알고리즘을 푸는데, 진짜 ㄹㅇ 하나도 감이 안 잡혔다. 그래서 프로그래머스 레벨 0 부터 뽀개기를 하다가 너무 많아서 반쯤 하고 포기하고, 레벨 1, 2 를 섞어 풀고 있다. 거침 없이 문제를 풀던 중 나를 가로막은 한 문제가 나를 오랜만에 블로그로 이끌었다!!1. 먼저 공백을 기준으로 s 를 나눈다. (=words)  ex. ['3people', 'unFollowed', 'me']2. words 의 길이 만큼 for 문을 돈다. (3 번 돌겠지 그럼)3. 만약 words[i] 가 있다면, words 의 첫 문자는 대문자로 바꾸고 나머지는 소문자로 바꾼다. 이때 words[i][0] 과 같은 식으로 배열을 사용하였다. 이거 뭐라 그러는지 아는..

아직 언제 재귀를 써야 하고, 언제 dfs 를 써야 하고, 언제 백트래킹을 써야 하는지 잘 모르겠다 ㅜㅜ 이 문제는 백트래킹으로 들어간 문제인데 그걸 아는데도 백트래킹이 무엇인지 제대로 몰라서 아주 헤맸다. 먼저 다시 정리해보고자 한다. 백트래킹이란 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어가는 것이다.즉, 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 다시 해를 찾는 것이다. 여기서 중요한 점은 더 이상 탐색할 필요가 없는 상태를 제외하는 것인데 이를 가지치기 라고 한다.백트래킹은 모든 경우의 수에서 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전 탐색 기법인 ..

먼저 2 차원 배열로 상담 시간과 수익을 저장한다.  현재 작업 중인 i 번째 리스트 인덱스 값에 i 번째 리스트의 값을 더했을 때  보다 작다면, 수익에 해당 값을 재귀 호출한 값과 수익을 더한다. 현재 작업을 수행하지 않고 그냥 다음 작업으로 넘어가는 경우 두 경우 중 더 큰 값을 선택한다. 각 작업은 소요되는 시간이 정해져 있고 주어진 제한된 시간 안에서 최대한 많은 이익을 얻기 위해 어떤 작업을 선택해야 할지 재귀 호출을 통해 고민해 보았다. 1. 주어진 작업을 할지 말지 결정2. 작업이 끝나는 시간을 넘지 않는 범위 내에서 최대 이익을 얻도록 재귀적으로 계산 재귀 -> 각 작업을 선택하거나 선택하지 않는 모든 경우를 탐색n = int(input())list = [list(map(int, inpu..