SUEATY 발은 개발

Input // 문자인가? extension String { var isAlphabet: Bool { return range(of: "[^a-zA-Z]", options: .regularExpression) == nil } } // 공백으로 input arr 만들기 let input = readLine()!.components(seperatedBy: " ") // 다양한 delimeter 사용 let expression = "100-200*300-500+20" let arr = expression.components(separatedBy: CharacterSet(charactersIn: "*+-")) Loop // stride for i in stride(from: 5, to: 0, by: -1) { p..

The Floyd-Warshall Algorithm 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구하는 알고리즘 Dijkstra/Bellman-Ford 를 반복해서 구할 수도 있음 경유점 : 두 정점 u와 v를 잇는 어떤 경로가 있다고 가정할 때, u와 v 사이에 있는 다른 정점 1. 경유점 k를 제외한 S - {k} 노드 중 서로 다른 노드 U, V 선택 (S = 정점 집합일 때 k, U, V ∈ S) 2. U → k → V의 비용 확인 후 최단거리 갱신 직접 해보기 다음과 같은 그래프가 주어졌다고 해보자. Floyd-Warshall 알고리즘은 Dijkstra와 다르게 모든 그래프의 모든 정점 쌍의 최단 거리를 저장해야하므로 2차원 배열이 필요하다 초기화 할 때에는 if from == to, then ..

(뭐 대충 중요하다는 내용ㅎ) 최단 경로 문제를 풀 때 가장 많이 언급되고 활용되는 삼대장이 있죠? 다익스트라 벨만포드 플로이드 상황에 맞게 위 알고리즘을 적용해서 문제를 해결하면 될텐데 언제, 무엇을 선택할 지 모르겠다면 3가지를 떠올려봅시다. 문제를 그래프화 하는 것에 성공하셨다면 이제 이 3가지 흐름을 생각해 봅시다. 가중치가 있는가? : 가중치가 없다면 BFS로 해결 가능 음수간선이 있는가? : weight에 음수 값이 있다면 벨만포드 단일 시작점을 갖는가? : 단일 시작점이 주어진다면 다익스트라, 모든 정점들의 쌍에 대한 경로 값을 알고 싶다면 플로이드 어떤 알고리즘을 쓰면 되는지 선택하셨다면 각 알고리즘들의 개념을 짚어보도록 하겠습니다. 오늘은 Dijkstra Algorithm에 대해 먼저 살..

정말 개인적으로 쓰려고 만들었지만 혹시 보고 싶어하실 수도 있으니 포스팅 해보도록 하겠습니다. 1. 에라토스테네스의 체 : 소수 찾기 // arr : 'true' if prime num, 'false' if not bool *arr = new bool[n+1]; for(int i = 2; i < n+1; i++){ arr[i] = true; } // 에라토스테네스의 체 for(int i = 2; i * i

이 글에서는 프로그래머스 - 스킬트리 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요? 처음에는 입출력 예시를 잘못봐서 아예 코드를 잘못 짰었습니다. 무조건 스킬을 다 써야 하는 줄 알았는데 순서만 맞으면 되지, 순서가 명시되어 있는 모든 스킬들을 쓰지 않아도 된다는 것을 틀리고 나서 알았습니다. 그래서 다시 짜고 말았다는...ㅎ 이 문제야 말로 사람마다 푸는 방식이 다 다를 것 같은데 저는 아래와 같이 풀었고 해당 그림은 문제에 예시를 사용했습니다. 참고로, 아래 풀이는 스킬이 중복되지 않기 때문에 가능한 풀이 입니다. 풀이 1 그림..

이 글에서는 프로그래머스 -멀쩡한 사각형 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요? 저는 문제를 풀고나서 꼭 구글에 해당 문제를 한 번 검색을 해 봅니다. 다른 사람들의 풀이가 도움이 된다고 해서 검색은 해보지만 다수와 다르게 풀었다면 골치가 조금 아픕니다. 대중적인 풀이(?)가 더 효율성이 좋은건가... 하고 효율성도 따져야 하고... 아직 이 문제에 대해서 효율성 검사를 해보지는 않았지만 이 글 쓰고 해보겠습니다. 이 문제를 풀 때 많이 쓰시는 방법이 gcd (최대공약수)를 사용하시던데 아직 찬찬히 살펴보지 않아 어떤 맥락에..

이 글에서는 프로그래머스 - 124 나라의 숫자 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요? 재귀법 좋아하시는 분 계세요? 재귀법하면 제일 먼저 떠오르는게 피보나치 수열인데 드디어 그 틀을 좀 벗어날 수 있을 것 같습니다. 문제를 풀고 다른 분들 풀이 보니까 진법의 원리를 이용해서 푸신 분들이 많던데 저도 처음 풀었을 때 나온 풀이가 3진법이니 가장 직관적인 것이 아닐까 싶습니다. 그러나 3진법 풀이는 이미 다른 블로그에도 많으니 재귀법으로 설명드리겠습니다. 풀이 1 : 재귀법 제가 이 포스트를 위해 공을 좀 들였습니다. 예시를 ..

이 글에서는 프로그래머스의 Level 1 문제 중 꼭 한 번은 다루고 넘어갔으면 좋겠는 문제들에 대해 살펴보도록 하겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요? 일단 시작하기 전, 프로그래머스 Level 1 문제에는 [2019 카카오 개발자 겨울 인턴십 : 크레인 인형뽑기 게임] [2018 카카오 블라인드 채용 1차 : 비밀지도, 다트게임] [2019 카카오 블라인드 채용 1차 : 실패율] [2018 summer/winter coding : 예산]이 포함되어 있습니다. 이 문제들은 선택적으로 풀어보는 것이 아닌 반드시 풀어보아야 할 문제일테니 따로 ..

이 글에서는 프로그래머스 - 탑 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요? 하 진쟈 한 번만에 성공한거 너무 오랜만이라서 지금 흥분을 주체할 수 없어요. 아니 뭐 꼭 어려운 문제를 풀고 나서 성취를 느껴야 하는 건 아니잖아요? 안그래도 지금 백준에 뭐 안풀리는 문제 있어가지고(풀릴 듯 안풀리는... 분명 내일 풀면 풀릴 거야 망할 토마토...) 자존감 떨어지고 있는데 프로그래머스 와서 힐링 했네요ㅋㅋ 문제는 아래 [그림 1] 으로 깔끔하게 요약이 될 것 같습니다. 각 송신탑은 왼쪽으로 시그널을 보내고 자신 보다 높은 송신탑의 수..

이 글은 BOJ 2606-바이러스 문제에 대해 다루겠습니다. BFS, DFS관련 게시글은 요이따 여기에 있습니다. 공부한 것을 정리하는 형식으로 작성되었으므로 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요? 결론부터 말하자면 문제를 풀 때 DFS를 쓰는 것이 더 적합합니다. 왜냐하면 바이러스에 걸린 1번 컴퓨터와 연결된 모든 컴퓨터를 찾아야 하기 때문입니다. DFS는 모든 노드를 traverse할 때, BFS는 path finding을 할 때 잘 쓰이기 때문입니다. 그런데 저는 BFS로 풀었냐구요? 음... 약간 제가 재귀문 트라우마가 있어서 BFS로 먼저 짰다가 시간 초과나면 DFS로 갈아탈 생각이었습니다. 뭐... 코테 볼 때나 면접 볼 때 그럴 여유는 없겠지만 우리는 ..