본문 바로가기

알고리즘11

Swift 코딩 테스트 준비 - Java to Swift 😱 이번에 하계 인턴을 위한 코테를 칠 예정이다. 오늘 안내 메일을 받았는데 세상에나 Swift 언어만 지원한다고 한다. iOS직군이라 그런것 같으나 언어 제한을 둘 줄은 몰랐다. 평소에 Swift로 슬슬 풀어볼까 생각이 들었었는데 이 참에 Swift로 풀어야 겠다. 🤦‍♂️ 문자열 - 가운데 수 찾기 func solution(_ s:String) -> String { if(s.count%2==0){ let index1 = s.index(s.startIndex, offsetBy: s.count/2-1) let index2 = s.index(s.startIndex, offsetBy: s.count/2) return "\(s[index1])\(s[index2])" }else{ let index1 = s.inde.. 2020. 7. 1.
01. 배열과 문자열 Hash table 효율적인 탐색을 위한 자료구조 key-value 방식 구현방법 키의 해시 코드를 계산한다. (키의 개수는 무한한데 int 의 개수는 유한하기 때문에 서로다른 두 개의 키가 같은 해시코드를 가리킬 수 있다.) hash(key) % array_length 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다. (서로다른 두개의 해시 코드가 같은 인덱스를 가리킬 수 있다.) 배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비하여 반드시 연결 리스트를 이용한다. (충돌 : 서로다른 두 개의 키가 같은 해시 코드를 가리킬때, 서로다른 두 개의 해시 코드가 같은 인덱스를 가리킬때) 값을 찾을 때 주어진 키로부터 해시 코드를 계산하.. 2020. 6. 9.
Programmers - 폰켓몬 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. � programmers.co.kr 문제 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬.. 2020. 5. 29.
Programmers - 스킬트리 코딩테스트 연습 - 스킬트리 programmers.co.kr 문제 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return.. 2020. 5. 29.
Programmers - 땅따먹기 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 문제 문제 설명 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | .. 2020. 5. 29.
LeetCode - 53. Maximum Subarray Maximum Subarray - 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 integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] .. 2020. 5. 28.
LeetCode - 146. LRU Cache LRU Cache - 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 문제 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the .. 2020. 5. 26.
Leetcode - 2. Add Two Sum Add Two Numbers - 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 two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked.. 2020. 5. 25.
문제해결 전략 - 29. 그래프 너비 우선 탐색 그래프 너비 우선 탐색 너비 우선 탐색은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 구현 방법 각 정점을 방문할 때 마다 모든 인접 정점들을 검사한다. 이중 처음 보는 정범을 발견하면 이 정점을 방문 예정이라고 기록한 뒤 별도의 위치에 저장한다. 인접한 정점을 모두 검사하고 나면 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문한다. 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다. 특징 깊이 우선 탐색과 달리 너비 우선 탐색에서는 발견과 방문이 같지 않다. 모든 정점은 아래와 같은 세 상태를 순서대로 거친다. 아직 발견되지 않은 상태 발견되었지만 아직 방문되지 않은 상태(정점들의 목록이 큐에 저장되어 있음) 방문된 상태 시간 복잡도 깊이 우선 탐색과 같다. 모든 정점을 한 번.. 2020. 5. 22.
Programmers - 프린터 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린�� programmers.co.kr 우선순위 큐 [예제] [JAVA] 우선순위(PriorityQueue) 큐 1. 개요 일반적으로 Queue라는 자료구조는 '선입선출'(First-In, First-Out)의 대기열 규칙(queuing discipline)을 가지고 있다. 말그대로 먼저들어온 놈이 먼저 나간다는 것이다. 하지만 JAVA에서 제공하는 '... asuraiv.blogspot.com 코드 import java.util.*; class Solution { public int solution.. 2020. 5. 15.
문제해결 전략 - 27. 그래프 표현과 정의 그래프 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현 여러 도시들을 연결하는 도로망 사람들 간의 지인 관계 웹사이트 간의 링크 관계 트리에 있던 부모 자식 관계에 관한 제약이 없기 떄문에 트리보다 훨씬 다양한 구조를 표현할 수 있다. 그래프의 정의 그래프 G(V,E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조 그래프의 종류 방향 그래프(directed graph) : 각 간선이 방향이라는 새로운 속성을 가짐 무향 그래프(undirected graph) 가중치 그래프(weighted graph) : 각 간선에 가중치(weight)라고 불리는 실수 속성을 부여함 다중 그래프(multigraph) : 두 정점 사이.. 2020. 5. 7.

티스토리툴바