평생공부하는사람

안녕하세요😀 오늘은 프로그래머스 전력망을 둘로 나누기 문제를 풀어보겠습니다! 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 전력망을 둘로 나누기 문제는 완전탐색을 이용해서 풀었습니다. 최대 노드 갯수가 100개이기 때문에 bfs알고리즘으로 풀 경우 최악의 상황에서 O(n * nlogn) 의 시간이 걸리기 때문에 시간제한이 걸리진 않을듯 합니다! 이제 문제를 풀어보겠습니다! wireGraph와 isVisitedNode를 선언하고 완전탐색이므로 전력망을 둘로 나누기 위해 wire를 자르는데 모든 와이어를 한번씩 ..

안녕하세요. 오늘은 DFS와 BFS알고리즘에 대해서 알아 보겠습니다. DFS와 BFS는 그래프의 완전탐색 알고리즘입니다. 시간복잡도 두 알고리즘의 시간 복잡도에 대해서 먼저 설명드리겠습니다. 인접리스트형식으로 표현된 그래프와 인접행렬법으로 표현된 그래프에서의 시간복잡도는 다릅니다. 우선 인접행렬법(V by V 행렬 : V은 정점의 개수 입니다.)에서는 O(V^2)입니다. 각각의 노드에서 모든 노드로 간선이 있는지 여부를 알아야 하기 때문입니다. 두번째로 인접리스트형식(V: 정점의 개수, E: 간선의 개수)으로 표현된 그래프에서는 O(V+E)입니다. 각각의 노드에서 다른 노드로 간선이 리스트형식으로 존재함을 알기 때문에 V+E로 모두 탐색 가능합니다. 알고리즘 설명 DFS부터 알고리즘 설명 드리겠습니다. ..

안녕하세요. 오늘은 프로그래머스 후보키 문제를 풀어보겠습니다! 후보키 문제는 여러가지 알고리즘을 섞어만든 문제인데요! 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr row&column이 max 8*20이기 때문에 어떤 방법으로해도 전략만 잘 세운다면 시간초과날 일은 없을듯합니다! 처음에는 재귀알고리즘을 이용하여 combination을 하여 후보키 후보조합을 만들어줍니다! 이 후 sort..

안녕하세요. 오늘은 프로그래머스 소수 찾기 문제를 풀어보겠습니다. 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 이 문제는 재귀를 이용한 완전탐색을 통해 소수판별 알고리즘을 적용하여 문제를 해결 하실 수 있습니다! 우선 순서가 상관없으니 순열을 적용해야합니다. 순열은 재귀의 for문에 0부터 시작하면 순열입니다! (순서가 상관있다면 이전 index를 가져와서 index+1부터 탐색하시면 됩니다.) 또한 모두 안뽑아도 되고 모두 뽑아도 되므로 해당 숫자가 들어가있을때 한번 안들어가있을때 한번 재..

안녕하세요. 오늘은 프로그래머스 빛의 경로 사이클 문제를 풀어보겠습니다! 빛의 경로 사이클 문제는 각각의 포인트에 대하여 모든 방향으로 지나갔는지 안 지나갔는지 확인하면서 경로의 길이를 측정하면 되는 문제입니다! 문제를 위와 같이 간소화 할 수 있는 이유는 지나간 길은 다시 돌아와 지나가기 때문에 같은 사이클이기 때문입니다. 그러기 위해서 isVisited와 Map을 만들어줍니다! x = grid[0].count y = grid.count for i in 0.. Int { if isVisited[startY][startX][startDirection] != 0 { return 0 } isVisited[startY][startX][startDirection] = 1 let nextDirection = re..

안녕하세요! 오늘은 프로그래머스 2레벨 거리두기 확인하기 문제를 풀어보겠습니다! 이번 문제는 맨허튼 거리를 이용해서 거리를 확인하는 문제입니다! 소스 코드량(함수로 안만들어서 뻥튀기된 부분이 있어요 ㅠㅠ)에 비해서 생각보다 문제가 쉬우니 다들 풀어보시기 바랍니다! 우선 이 문제는 사람이 앉은 포인트를 잡아서 맨허튼 거리 2안에서 사람이 또 있는지 없는지를 확인하는 문제입니다! 장애물도 있기 때문에 일반적인 거리측정방법말고 DFS나 BFS를 이용해야합니다. 저번에 DFS로 문제를 풀었던게 있어서 BFS로 문제를 풀어보겠습니다! 우선 BFS에 쓸 Queue가 필요한데 Swift에는 기본적으로 지원해주는 Queue가 없으니 대충 만들어 씁시다! Queue도 거리가 2까지이다 보니 Queue도 완벽하게 구현할 ..

안녕하세요! 오늘은 프로그래머스 단체사진 찍기 문제를 풀어보겠습니다. 이 문제는 제 기준에선 참 문제를 이해하기 어렵게 만들었다고 생각했는데요. 왜냐면 일렬로 선다고 해놓고 나란히 선다고 하고 저는 전체 경우의 수가 시그마n=1to8 8P(8-n)*n^(8-n)개인줄 알았습니다... 그래서 레벨2에도 엄청난 수열문제가 나올 수 있구나... 이런 마음이였는데요 다행히 그건아니고 최대 8!개를 탐색하는 문제였습니다! 또, 맞왜틀(맞는데 왜 틀리지?!) 문제입니다! 한 session에 하나의 testcase가 아니라 여러 testcase가 들어있어 전역 변수를 초기화 해주지 않으면 오답이 됩니다! 모두 구현한 뒤 오답이길레 한참 헤맸습니다 ㅠㅠ 잡설은 이쯤하고! 같이 문제 풀어보시죠! 알고리즘은 brute f..

안녕하세요! 오늘은 프로그래머스 레벨1 문제 모의고사를 풀어보았습니다! 완전탐색이긴한데 그냥 for문 돌리면서 쭉 값 비교만하면 되는 거라 for문 문제같네요! 수포자 3명 테이블 만들어서 for문으로 풀어보았습니다! #include #include using namespace std; vector solution(vector answers) { int spjrepeat[3][10] = {{1,2,3,4,5,}, {2,1,2,3,2,4,2,5,}, {3,3,1,1,2,2,4,4,5,5}}; int res[3] = {0,}; vector answer; int size = answers.size(); for(int i = 0; i < size; i++){ if(spjrepeat[0][i % 5] == ans..