본문 바로가기

728x90

알고리즘49

[Swift] 프로그래머스 위클리 챌린지 7주차 입실 퇴실 Problem 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr Solution 1. 반드시 만나는 경우를 구하기 leave에 있는 숫자를 차례대로 순회합니다. leave안에 있는 숫자를 n이라고 가정할 때 enter안의 숫자 0부터 n이 있는 인덱스까지의 숫자들은 모두 반드시 만나는 경우입니다. ex) enter [1,4,2,3] leave [2,1,4,3] leave의 가장 첫 번째 숫자는 2입니다. enter에서 2가 있는 index는 2입니다. 고로 enter의 0부터 2까지의 숫자 1,4,2는 1과 4 .. 2021. 9. 16.

[Swift] 프로그래머스 다단계 칫솔 판매 Problem 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr Solution 1. 판매자의 부모와 이익을 초기화해준다. var parentDic:[String:String] = [:] var profitDic:[String:Int] = [:] for i in 0.. 2021. 9. 12.

[Swift] 프로그래머스 위클리 챌린지 5주차 모음 사전 Problem 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr Solution 1. 모음 순서와 인덱스별 카운트 어레이를 만든다. 인덱스별 카운트는 가장 끝 즉,4번째 인덱스일 경우 다음 모음으로 이동하는데 1개의 단어가 필요합니다. ex) AAAAA -> AAAAE -> AAAAI .... 1개씩 3번째 인덱스의 경우 다음 모음으로 이동하는데 6개가 필요합니다. ex) AAAA -> AAAE -> AAAI ... 6개씩 2번째 인덱스의 경우 다음 모음으로 이동하는.. 2021. 8. 30.

[Algorithm] 백트래킹(Backtracking)이란? (feat. 예제포함) 안녕하세요 Foma 💻 입니다! 오늘은 프로그래머스 N-Queen 문제를 풀면서 해당 문제가 백트래킹 문제라는 것을 알게 되었는데요. 그래서 백트래킹이 무엇이고 어떻게 구현해서 사용해야 하는지에 대해 정리해보려고 합니다. 바로 시작할게요~ 백트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만,.. 2021. 8. 28.

[Algorithm] 조합(Combination)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "조합" 에 대해서 알아보도록 하겠습니다. 바로 시작할게요~ 조합이란? n개의 원소에서 r 개의 원소를 순서에 상관없이 뽑는 경우의 수 - 나무 위키 - 순열과 다르게 순서는 중요하지 않아요. 쉽게 설명하면 물건을 사고 총 가격을 구하는 것과 비슷해요. 과일로 예를 들면 사과,포도,수박이 있다면 사과,포도,수박 포도,사과,수박 수박,사과,포도 ... 등 어떤 방식으로 사도 총 가격을 똑같겠죠? 즉, 이루어진 과일이 똑같다면 하나의 조합으로 생각하는 것입니다. 코드 구현 먼저 경우의 수를 담을 배열을 만들어줍니다. var cases:[[Int]] = [] combination의 파라미터를 설정해주는데 인덱스들을 담고있는 ind.. 2021. 6. 27.

[Algorithm] 순열(Permutation)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "순열"에 대해서 알아보도록 하겠습니다. 바로 시작할게요! 순열이란? 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 이른다. - 나무 위키 - 쉽게 설명하면 줄 세우기와 똑같아요. A,B,C라는 학생을 줄 세우는 방법은 ABC,ACB,BAC,BCA,CAB,CBA 등이 있겠죠? 이 중에서 2명의 학생으로 줄 세우는 방법은 AB,AC,BA,BC,CA,CB 등이 있을거에요. 코드 구현 경우의 수들을 담을 이중 배열을 만들어줍니다. var cases:[[Int]] = [] 몇 개를 뽑을지 정해줍니다. let pickCount = 3 본격적으로 순열 함수를 만들어줍니다. 파라미터로는 전체 인덱스가 담긴.. 2021. 6. 27.

[Swift] 프로그래머스 가장 긴 팰린드롬 Problem 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr Solution 해당 문제는 완전탐색 문제입니다. 모든 경우를 탐색해야 정답을 알 수 있는 문제입니다. 하지만 효율적으로 탐색하기 위해 주어진 문자를 긴 문자열에서 짧은 문자열로 잘라서 비교하는게 핵심입니다. 1. 초기값 설정 인덱스를 찾기 쉽게 문자열을 매핑한 값과 가장 긴 값의 초기값을 설정해줍니다. //문자열 인덱스를 찾기 쉽게 매핑해줌 let str:[String] = s.map{Stri.. 2021. 6. 22.

[Swift] 2019 KAKAO BLIND RECRUITMENT 길 찾기 게임 Problem 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr Solution 해당 문제는 "이진트리 " 문제입니다. 이진 트리는 각각의 노드가 최대 두 개의 자식 노드을 가지고 있고 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 1. 초기에 필요한 변수들을 세팅해줍니다. //부모와 자식을 담을 이중배열 var parentsChildren:[[Int]] = Array(repeating: [], count: nodeinfo.count + 1) //각 노드의 범위들을 담을 배열 var ranges = Array(r.. 2021. 6. 11.

[Swift] 프로그래머스 숫자 게임 Problem 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr Solution 1. a와 b를 오름차순으로 정렬시킵니다. (sortB,sortA라고 칭하겠습니다.) 2. sortB를 순회하면서 sortA의 가장 첫번째값(가장 작은값)이 더 작다면 sortA의 첫번째 값을 삭제해줍니다. 3. 전체 갯수에서 sortA의 갯수를 빼줍니다. Souce Code func solution(_ a:[Int], _ b:[Int]) -> Int { var sortA = a.sorted() b.sorted().f.. 2021. 6. 11.

[Algorithm] 깊이 우선 탐색(DFS,Depth-First-Search)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 엄청 빈번하게 출제되고 알아두면 정말 유용한 DFS에 대해서 알아보도록 하겠습니다. 바로 시작할게요! DFS란? "깊이 우선 탐색은 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다." - 위키 백과 - 이게 뭔말이야....;;; 쉽게 예제를 통해서 설명드리겠습니다. 아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다. 어떤 사람은 "난 먼저 어떤 나라들이 있는지 부터 확인하고 그 나라 안에 있는.. 2021. 6. 5.

[Swift] 프로그래머스 행렬 테두리 회전하기 Problem 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr Solution 1. 직사각형의 숫자들을 행과 열에 맞게 넣어준다. 한 행을 행의 크기만큼 만들어서 열의 수만큼 넣어준다. 2. 테두리의 위쪽 행과 아래쪽 행을 회전한 숫자에 맞게 바꿔준다. (테두리를 1,1,6,6 으로 가정했을때) 먼저 위쪽 행은 숫자들을 오른쪽으로 전부 밀고 가장 첫번째 숫자를 바로 아래 행의 가장 왼쪽의 숫자로 대체한다. 아랫쪽 행은 반대로 숫자들을 왼쪽으로 전부 밀고 가장 마지막 숫자를 바로 위 행의 가장.. 2021. 5. 24.

[Algorithm] 다익스트라(Dijkstra) 알고리즘이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 그래프 문제에서 아주 빈번하게 사용되는 다익스트라라는 알고리즘에 대해서 알아보겠습니다. 바로 시작할게요! 다익스트라란? 🤔 나무 위키에는 다음과 같이 정의되어있습니다. "음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다." 쉽게 말하면 한 정점에서 다른 정점으로 이동할 때 가장 빠른 길을 찾아주는 알고리즘이에요. 그래프 설명 다음과 같은 그래프가 있다고 가정하겠습니다. 시작 정점은 1로 목표 정점을 4로 두었을 때 가장 가까운 거리는 몇일까요? 1 - 5 - 4 로 가는 경우가 3 + 1 = 4로 가장 가까운 길이겠죠? 이렇게 간단히 보이는 경로는 눈으로 쉽게 찾을 수 있지만 복잡한 경로일수록 찾기가 어려워질 것입니다. 이.. 2021. 5. 22.

이전 1 2 3 4 5 다음

728x90

티스토리툴바