본문 바로가기

Algorithm102

Swift - BFS iteration on Binary Tree [1,3,2,5,3,null,9] func bfs(_ root: TreeNode?) -> Int { if root == nil { return 0 } var maxWidth = 0 var queue : [TreeNode] = [] queue.append(root!) while(!queue.isEmpty){ var count = queue.count maxWidth = max(maxWidth,count) while(count > 0){ var tmp = queue.removeFirst() print(tmp.val) if(tmp.left != nil){ queue.append(tmp.left!) } if(tmp.right != nil){ queue.append(tmp.right!) } count -= 1 }.. 2020. 7. 9.
💯 Daily LeetCode Challenge Day_08 - 3Sum Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate tri.. 2020. 7. 9.
💯 Daily LeetCode Challenge Day_07 - Island Perimeter Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by w.. 2020. 7. 7.
💯 Daily LeetCode Challenge Day_06 - Plus One Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array co.. 2020. 7. 7.
💯 Daily LeetCode Challenge Day_05 - Hamming Distance Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 문제 The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming di.. 2020. 7. 6.
💯 Daily LeetCode Challenge Day_04 - Ugly Number II Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence.. 2020. 7. 6.
Swift 배열 처리 String 과 Int 를 넘나드는 데이터 타입 변경 배열 반대로 순회 배열을 String으로 리턴 코드 import Foundation var arr1 : [Int] = [3,2,3,1,2,8,6,4,3,5,2,3,2,1] var arr2 : [Int] = [9,7,5,4,3,4,2,1,3,5,0,5,4,3] var answer : [Int] = [] var carry = 0 for i in (0.. 2020. 7. 4.
💯 Daily LeetCode Challenge Day_03 - Prison Cells After N Days Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 문제 There are 8 prison cells in a row, and each cell is either occupied or vacant. Each day, whether the cell is occupied or vacant changes according to the following rules.. 2020. 7. 3.
💯 Daily LeetCode Challenge Day_02 - Binary Tree Level Order Traversal II Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). level 에 맞게 2개씩 짝짓는다. DFS 로 풀다가 트리의 depth 별로 접근하니 BFS 인가 싶어서 Queue를 쓰는.. 2020. 7. 3.
💯 Daily LeetCode Challenge Day_01 - Arranging Coins Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins. Given n, find the total number of full staircase rows that can be formed. n is a non-negative i.. 2020. 7. 1.
Programmers - 카펫 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 �� programmers.co.kr 문제 문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return.. 2020. 6. 30.
Programmers - 숫자 야구 ⚾️ 코딩테스트 연습 - 숫자 야구 [[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]] 2 programmers.co.kr 문제 문제 설명 숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다. 게임해보기 각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다. * 숫자는 맞지만, 위치가 틀렸을 때는 볼 * 숫자와 위치가 모두 맞을 때는 스트라이크 * 숫자와 위치가 모두 틀렸을 때는 아웃 예를 들어, 아래의 경우가 있으면 A : 123 B : 1스트라이크 1볼. A : 356 B : 1스트라이크 0볼. A : 327 B : 2스트라이크 0.. 2020. 6. 30.
Programmers - 소수찾기(완전탐색) 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 � programmers.co.kr 문제 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0,.. 2020. 6. 30.
Programmers - ⚖️가장 큰 수 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 �� programmers.co.kr 문제 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰.. 2020. 6. 27.
Programmers - 라면공장🍜 코딩테스트 연습 - 라면공장 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니�� programmers.co.kr 문제 문제 설명 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 .. 2020. 6. 26.
Programmers - 위장 🔫 코딩테스트 연습 - 위장 programmers.co.kr 문제 문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하.. 2020. 6. 25.
Programmers - 다리를 지나는 트럭🚛 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 문제 문제 설명 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4,.. 2020. 6. 25.
Programmers - 기능개발 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 �� programmers.co.kr 문제 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배.. 2020. 6. 24.
📕 잠깐 내가 이해한게 맞는지 정리 Dynamic Programming Greedy Back Tracking Branch and bound Greedy는 반례가 있어서 적용 안되는 경우가 있다. - 0-1 knapsack problem Greedy가 적용되지 않는 경우 Dynamic Programming 을 쓴다. Dynamic Programming 이 적용되지 않을 때 BackTracking을 쓴다. - Dynamic Programming 은 2^n의 부분집합을 검사하니까 오래걸리는데 이걸 Backtracking이 Tree 형태의 pruned state space tree 로 promising 하는 경우만 check 한다. Backtracking 에서 발전된게 Branch and bound 이다. 그리디는 local 한 최적해를 구하고 .. 2020. 6. 19.
😈 Greedy & Prims Algorithm (feat MST) 탐욕 알고리즘이란 답을 하나씩 고르는데 미리 정한 기준에 따라 매번 가장 좋아 보이는 답을 선택한다. *동적 프로그래밍과 마찬가지로 최적화 문제를 푸는데 사용된다. 동적 계획법과 다른점 동적 계획법 1. 재귀 관계식을 세워서 2. 입력 사례를 더 작은 입력사례로 분할 탐욕법 1. locally 최적의 경우 선택 2. 적절성 검사 3. 해답 점검 *전체적으로 최적인 해를 구하지만 항상 최적인 해를 얻는다는 보장이 없다. --> 최적인 해답을 얻는지 확인하는 절차가 반드시 필요하다. 거스름 돈 문제 : 동전의 개수가 최소가 되도록 거스름돈을 주는 문제 빈손으로 시작한다. 액면가가 가장 높은 동전을 집어 손에 올린다. (선택과정) 손에 있는 거스름 돈의 총액이 거슬러 주는 액수를 초과하는지 확인한다. (적절성.. 2020. 6. 18.
01. 배열과 문자열 Hash table 효율적인 탐색을 위한 자료구조 key-value 방식 구현방법 키의 해시 코드를 계산한다. (키의 개수는 무한한데 int 의 개수는 유한하기 때문에 서로다른 두 개의 키가 같은 해시코드를 가리킬 수 있다.) hash(key) % array_length 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다. (서로다른 두개의 해시 코드가 같은 인덱스를 가리킬 수 있다.) 배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비하여 반드시 연결 리스트를 이용한다. (충돌 : 서로다른 두 개의 키가 같은 해시 코드를 가리킬때, 서로다른 두 개의 해시 코드가 같은 인덱스를 가리킬때) 값을 찾을 때 주어진 키로부터 해시 코드를 계산하.. 2020. 6. 9.

티스토리툴바