본문 바로가기

Algorithm102

LeetCode - 994. Rotting Oranges Rotting Oranges - 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 문제 In a given grid, each cell can have one of three values: the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange th.. 2020. 6. 1.
LeetCode - 15. 3Sum 3Sum - 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 triplets. Ex.. 2020. 6. 1.
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.
문제해결 전략 - 30. 최단 경로 알고리즘 최단경로 문제 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제 가중치가 있는 그래프에서의 최단 경로를 찾는 알고리즘을 다룬다. 최단 경로를 구성하는 정점들의 목록을 구해주는 것이 아니기 때문에 실제 경로를 계산하기 위해서는 별도의 정보를 저장해야 한다. 다양한 그래프의 종류와 특성에 따라 최적화된 많은 최단 경로 알고리즘이 존재한다 음수 간선의 중요성 음수 간선을 지나가면 전체 경로의 길이가 짧아진다. 음수 사이클이 있을 경우 경로의 길이는 음의 무한대로 발산 할 수 있다. 그래서 최단 경로를 찾을 수 없으며 음수 사이클이 존재한다는 것만 확인할 수 있다. 단일 시작점과 모든 쌍의 알고리즘 단일 시작점 알고리즘 : 너비 우선 탐색과 비슷하게, 하나의 시작점에서 다른 모든 .. 2020. 5. 29.
LeetCode - 3. Longest Substring Without Repeating Characters Longest Substring Without Repeating Characters - 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 string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. .. 2020. 5. 28.
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 - 5. Longest Palindromic Substring Longest Palindromic Substring - 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 string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example.. 2020. 5. 27.
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.
문제해결 전략 - 28. 그래프 깊이 우선 탐색 그래프 탐색 알고리즘 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘 트리보다 구조가 훨씬 복잡하기 떄문에 탐색 과정에서 얻어지는 정보가 중요하다. 탐색과정에서 알 수 있는 정보 어떤 간선이 사용되었는지 어떤 순서로 정점들이 방문되었는지 깊이 우선 탐색(Depth-first search) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 해당 간선을 무조건 따라감 더이상 갈곳이 없는 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 이동 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도한다. 지금까지 거쳐온 정점들을 모두 알고 있어야 하는데 재귀호출을 이용하면 간단히 구현.. 2020. 5. 14.
Programmers - [1차] 프렌즈4블록 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import java.util.*; class Solution { int answer = 0; char[][] block; boolean[][] isThere; boolean getScored = true; public int solution(int m, int n, String[] board) { char[][] game = new char[m][n]; boolean[][] localIsthere = new boolean[m][n]; int index = 0; for (int i = 0; i < board... 2020. 5. 8.
Programmers - 문자열 압축 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import java.util.*; class Solution { int answer = 0; public int solution(String s) { answer = s.length(); for(int splitCount = 1 ; splitCount < s.length() ; splitCount++){ String[] strArray = s.split("(? 2020. 5. 8.
문제해결 전략 - 27. 그래프 표현과 정의 그래프 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현 여러 도시들을 연결하는 도로망 사람들 간의 지인 관계 웹사이트 간의 링크 관계 트리에 있던 부모 자식 관계에 관한 제약이 없기 떄문에 트리보다 훨씬 다양한 구조를 표현할 수 있다. 그래프의 정의 그래프 G(V,E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조 그래프의 종류 방향 그래프(directed graph) : 각 간선이 방향이라는 새로운 속성을 가짐 무향 그래프(undirected graph) 가중치 그래프(weighted graph) : 각 간선에 가중치(weight)라고 불리는 실수 속성을 부여함 다중 그래프(multigraph) : 두 정점 사이.. 2020. 5. 7.
Leetcode - 557. Reverse Words in a String III [Must do Easy Question] How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss 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 Reverse Words in a String III - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge.. 2020. 4. 29.
문제해결 전략 - 15. 계산기하 정리 계산기하 알고리즘 점, 선, 다각형과 원 등 기하학 적 도형을 다루는 알고리즘 학부 선형 대수나 고등학교 수준의 기하학을 코드로 구현할 수 있는 능력 기초적인 수학 이론을 어떻게 간결하고 예외가 적은 형태로 구현하는지에 초점 계산기하 도구들 벡터의 구현 2차원 평면의 서로 다른 두 점의 상대적 위치 벡터는 방향과 거리의 쌍이므로 시작점이 중요하지 않다. 벡터의 시작점은 항상 좌표공간의 원점으로 둔다 벡터를 화살표 끝점의 위치 (x,y)로 표현할 수 있다. const double PI = 2.0 * acos(0.0); struct vector { double x, y; explicit vector(2double x_ = 0 double y_ =0) 등등 여러 operator x 좌표가 작은 벡터일수록, 끝.. 2020. 4. 29.
Leetcode - 448. Find All Numbers Disappeared in an Array [Must do Easy Question] How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss 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 Find All Numbers Disappeared in an Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand you.. 2020. 4. 23.
Leetcode - 226 . Invert Binary Tree [Must do Easy Question] How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss 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 Invert Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get pr.. 2020. 4. 20.

티스토리툴바