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

프로그래머스 레벨3 순위

* 문제유형이 그래프인데 다른방법으로 풀어서 다시 풀어봐야 할 문제 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 풀이 i번 선수를 이긴 선수의 명단인 win과 i번 선수에게 진 선수의 명단인 lose를 만든다. 그리고 results를 확인해서 A가 B에게 이기면 B번 선수의 이긴명단에 A를, A번 선수에게 진 명단에 B를 추가한다. setwin[101]; setlose[101]; for(auto i : results){ win[i[1]].insert(i[0]); lose[i[0]].insert(i[1]); } input : [4, 3] 4는 3에게 이겼으므로 win[3]에 4를 추가한다. 3은 4에게 졌으므로 lose[4]은 3를 추가한다..

2019. 12. 4. 23:00
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 이중우선순위큐

문제 : https://programmers.co.kr/learn/courses/30/lessons/42628 서론 제목에 나와있듯 우선순위 큐를 이용한 문제. 이중우선순위 큐를 이용하려면 최대힙, 최소힙 두개의 우선순위 큐를 만들면 될듯하지만 STL의 우선순위 큐는 인덱스를 이용한 접근이 안된다. 벡터의 위엄이다. 어쨌든 그래서 생각한 방법은 1. 우선순위 큐를 배열로 구현한다. 2. 우선순위 큐를 이용하지 않는다. 3. 다른분의 풀이를 참고한다. 2번을 선택했는데, 우선순위 큐를 만들지 않고 단순히 벡터를 만들고 삽입할떄마다 정렬해주고 최대값 삭제하려면 가장 뒤의 값을, 최소값 삭제하려면 가장 앞의 값을 지우는 형태로 풀었더니 효율성체크가 없어서 통과했다. 그래도 개운치 않아서 우선순위 큐를 이용해서..

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

프로그래머스 레벨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/43238 서론 혼자 풀어내지 못한 문제. 분류가 이분탐색인데 뭘 이분탐색하라는건지 이해를 못했었다. 그리고 이분의 블로그를 참고하여 이해할 수 있었다. https://antananarivo.tistory.com/141 원하는 답이 시간이니 시간을 이분탐색 해야한다고 생각할 수도 있었을것 같은데 왜 못했을까 싶다. 시간은 1부터 흘러가야한다는 굳어진 생각을 했었던건 아닌가 싶다. 풀이 시간을 기준으로 이분탐색하여 적합한 시간을 찾아야 한다. 최소시간은 1, times.min, n/times.length 등 다양하게 만들 수 있는데 여기서는 n*times.min/times.length 으로 구현했다. 최소시..

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

프로그래머스 레벨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