알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 단어 변환

문제 : https://programmers.co.kr/learn/courses/30/lessons/43163 서론 분류는 DFS/BFS DFS를 이용한 완전탐색으로 구현 풀이 우선 예제2외 같은 예외를 처리해야한다. words에 target과 같은 문자열이 없으면 0을 리턴한다. wrods에 target과 같은 문자열이 있으면 begin을 target이 될 때까지 DFS를 실행하는 완전탐색으로 최초 문자열이 변할 수 있는 모든 경우의 수를 탐색한다. 현재 문자열(최초에는 begin)을 words의 문자열들과 비교해서 변환 가능하면 DFS를 계속 이어간다. 아래는 현재 문자열이 선택한 words의 문자열로 변환 가능한지 확인하는 문자열 비교함수 두 문자열의 같은 문자(순서도 같은) 개수가 문자열의 길이-..

2019. 11. 1. 11:09
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 가장 먼 노드

문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 서론 그래프 문제. 풀이 그래프를 탐색해서 가장 먼 노드들을 찾는다. 그래프 탐색 알고리즘은 DFS/BFS가 있는데, 최단거리 문제를 제외하고는 항상 DFS로 구현했던지라 이번에도 그렇게 했다. 그리고 문제 발생 3번 노드는 1번노드에서 한칸 떨어져 있지만 1 - 2 - 3순으로 탐색해서 2칸 떨어진것으로 인식할 수 있다. 방문할때 조건을 잘 설정해주면 될것 같기도 하지만 애초에 이런 문제가 없는 BFS로 다시 구현했다. 그래프를 만들고 노드들의 거리를 저장하는 배열을 만든다. BFS로 탐색하면서 방문할 노드의 거리는 이전 노드의 거리에서 +1한다. 그리고 노드의 거리 중 최대값은 변수에 저장하..

2019. 10. 28. 10:04
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 네트워크

문제 : https://programmers.co.kr/learn/courses/30/lessons/43162 서론 문제를 보고 연결된 네트워크 따라 탐색시키면 되겠다 생각하고 코드를 완성한 후 분류를 봤더니 DFS/BFS문제다. 그리고 다시 내 코드를 봤더니 BFS였다. BFS는 생각하지도 않았는데 자연스럽게 BFS로 풀이된게 뿌듯하다. 조금은 체화된것같다. 풀이 DFS/BFS문제 answer를 1 증가시키면서 1번 노드에 방문하면 방문표시를 한다. 그리고 방문한 노드와 연결된 노드가 있고 아직 방문을 안했으면 방문하고 방문표시를 한다. 더이상 연결된 노드가 없을때까지 탐색하면 하나의 네트워크를 만들 수 있다. 그리고 위의 과정 전체를 아직 방문하지 않은 노드가 남아있을 때까지 반복한다. 구현 // c..

2019. 10. 10. 23:15
알고리즘/문제풀이 - 백준

백준 16234 인구 이동

문제 : https://www.acmicpc.net/problem/16234 서론 DFS/BFS 문제이며 DFS를 이용하여 구현 아이디어 국경선을 공유하는 연합을 만들기 위해 DFS를 사용한다. 모든 칸에서 DFS를 실행하고, DFS에서 방문할 칸이 아직 방문하지 않은 칸이고 국경선 열림 조건에 부합하면 다음칸에 방문하면 된다. 그리고 방문할때마다 변수 pop에 칸의 인구를 더해주고, 변수 cnt를 +1 해주고 방문한 칸의 좌표를 벡터에 넣는다. DFS가 끝나면 벡터를 이용하여 방문했던 좌표들의 인구를 pop/cnt로 갱신해준다. 이동(){ for(a의 모든 좌표){ pop=0 cnt=0 vector if (현재 좌표 방문 안했으면) dfs(좌표, pop, cnt, vector) for(idx : vec..

2019. 10. 3. 11:41
알고리즘/문제풀이 - 백준

백준 16236 아기 상어

문제 : https://www.acmicpc.net/problem/16236 서론 BFS문제. 아이디어 현재 위치에서 가장 가까운 물고기를 찾아야 하므로 BFS를 실행한다. 조건에 맞게 물고기를 먹고 BFS를 빠져나온 후, 물고기를 먹은 위치에서 BFS를 다시 실행하기를 반복한다. 가장 가까운 물고기가 여러마리일 경우, 가장 위의 물고기를 먹고 가장 위의 물고기가 여러마리면 가장 왼쪽의 물고기를 먹어야한다. 우선 BFS를 실행했을때 물고기를 먹고 바로 BFS를 빠져나오는게 아닌 동일한 거리의 물고기는 모두 벡터에 넣고 빠져나온다. 이를 위해 1초 후 이동할 것들은 제외한 큐의 사이즈만큼만 반복하고 BFS를 빠져나온다. while(!q.empty()){ qSize = q.size(); while(qSize..

2019. 9. 28. 11:57
알고리즘/문제풀이 - 백준

백준 17142 연구소3

문제 : https://www.acmicpc.net/problem/17142 서론 DFS와 BFS를 둘 다 사용해서 구현하는데 시간이 오래걸렸음에도(약 2시간) 예상할 수 있는 반례를 예제로 주어서 비교적 쉽다는 느낌을 받았다. 아이디어 먼저 비활성 바이러스 중에 활성 바이러스 m개를 선택해서 선택된 m개를 큐에 넣고 BFS를 돌려야한다. 바이러스가 퍼지는건 시간을 체크해야하기 때문에 BFS를 사용해야한다. 문제에 나와있듯이 바이러스가 퍼질때마다(한칸씩 방문할때마다) 1초씩 증가하므로 현재 방문지 = 이전 방문지 +1 을 해주면 마지막 방문지는 최종 시간이 되므로 결과값으로 가져오면 된다. 결과값을 가져올때는 지도 전체를 방문해서 벽에 막혀 바이러스가 퍼질 수 없는 곳이 있는지 체크를 먼저 해야한다. 만..

2019. 9. 5. 21:40