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

프로그래머스 레벨3 여행경로

문제 : https://programmers.co.kr/learn/courses/30/lessons/43164 서론 DFS+완전탐색+백트래킹을 이용해서 구현 풀이 이동가능한 모든 경로를 DFS+완전탐색으로 구현하는데, 현재 항공권의 도착지가 다음 항공권의 출발지와 같을 수 있도록 백트래킹을 추가 여행의 출발은 무조건 ICN이다. tickets중 출발지가 ICN을 찾아서 DFS를 시작한다. for (int i = 0; i < ticketNum; i++) { if (tickets[i][0].compare("ICN") == 0) { dfs(...); } } 현재 항공권의 도착지와 다음 항공권의 출발지가 같으며 아직 사용하지 않은 항공권일때 DFS를 이어간다. 항공권의 사용여부를 파악하는 이유는 예제2번의 ['..

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

프로그래머스 레벨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
알고리즘/문제풀이 - 백준

백준 12100 2048 (Easy)

문제 : https://www.acmicpc.net/problem/12100 서론 어려움이 많았던 문제. 구현에 오류가 많았는데 테스트케이스는 하나 뿐이라 반례와 그 원인찾기가 무척 힘들었다. 발생했던 문제들은 1. 전역변수로 만들어진 지도를 여러 재귀에서 같이 사용했던 문제 2. 최대값 갱신을 블록이 이동할때마다 하는것이 아닌 5번째만 갱신했던 문제 3. 한번 합쳐진 숫자는 다시 합쳐지면 안되는것을 구현하면서 발생한 실수 풀이 여러 함수로 구성되어있다. 1. right(), left(), up(), down() 블록들을 이동시키는 함수다. void up() { memset(visited, 0, sizeof(visited)); int dir = 0; // 위 for (int i = 1; i < n; i+..

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

백준 14500 테트로미노

문제 : https://www.acmicpc.net/problem/14500 서론 정사각형 4개가 가질 수 있는 모든 경우의 수를 찾기 위해 DFS를 이용했는데 보라색 사각형 모양이 DFS로는 안나온다. 이걸 구현한 후에야 알았다. 접근법이 틀렸다고 생각해서 이것저것 생각해봤는데 저 모양의 사각형들을 일일이 만들어야 하는것만 떠올랐다. 그리고 다른분의 풀이를 봤더니 보라색 사각형만 만들고 나머지는 DFS로 구현했다. 왜 이걸 생각하지 못했을까 풀이 보라색을 제외한 나머지는 DFS로 구현한다. DFS는 전형적인 DFS이며 깊이가 4가되면 탐색한 칸들의 합을 최대값과 비교하고 리턴한다. 탐색한 칸들의 합은 DFS의 인수에 더해주는 방식을 이용한다. void dfs(int y, int x, int sum) {..

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

백준 14502 연구소

문제 : https://www.acmicpc.net/problem/14502 서론 완전탐색 + DFS/BFS 삼성문제들은 완전탐색, DFS/BFS, 시뮬레이션 안에서만 출제되는거 같다. 풀이 지도를 입력받으면서 바이러스는 따로 벡터에 좌표를 저장한다. 가벽을 3개 세우는 모든 경우의 수를 찾기 위해 완전탐색을 이용한다. 가벽을 3개 세웠으면 바이러스를 퍼뜨리기 위해 DFS를 이용한다. 그 후 바이러스가 퍼지지 않은곳들을 세어본다. void bf(int idx, int y, int x){ if(map[y][x] > 0) return; // 바이러스거나 벽이면 리턴 map[y][x] = 3; // 가벽은 3으로 마크 if(idx == 2){ // 가벽을 3개 세웠다면 for(i : virus) dfs(i);..

2019. 10. 18. 11:29