알고리즘
kakao_튜플
kakao_튜플
2021.12.06튜플 문제 설명 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2) 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2) 튜플의 원소 개수는 유한합니다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', ..
kakao_캐시
kakao_캐시
2021.09.01Cache Size만큼 돌면서 HashMap에 채워 나간다. Hit라면 +5 하한다. Cache 가 가득 차면 하나를 줄인다. import java.util.*; class Solution { public int solution(int cacheSize, String[] cities) { int answer = 0; LinkedHashMap hm = new LinkedHashMap(); if(cacheSize == 0){ return cities.length*5; } int cnt = 1; for(int i=0; i
백준_새로운게임2
백준_새로운게임2
2021.08.13
프로그래머스_디스크컨트롤러
프로그래머스_디스크컨트롤러
2021.08.13
프로그래머스_실패율
프로그래머스_실패율
2021.08.13
새로운게임_Java
새로운게임_Java
2021.08.04문제 접근 하기 위해 아래 2가지를 만들어주었다. 1. 말의 상태를 관리하는 class를 생성 => 체스의 상태를 관리해줘야 하는 이유는 체스가 움직이면 맨 밑에 있는지 위치는 어디인지 방향은 어디인지를 명확하게 알기 위함이다. 2. 맵, ArrayList 맵 => 맵은 0,1,2 이렇게 표시만 되는 부분이고 ArrayList 맵은 어떤 체스들이 들어 있는지 보여준다. 예를 들면 다음과 같다. ArrayList_Map[0][0] = { 1,2,3 } 의 의미는 (0,0) 좌표에 체스 1,2,3 이 포진해 있다. 이렇게 해석하면 된다. 3. 우선 main으로 쭉 나열해서 푸는 방법 그리고 재귀적으로 푸는 방법 2가지 모두 시도해보았다. 아무래도 main에다 다 때려박아서 하는게 속도는 더 좋았다. 그치만 ..
LeetCode : Partition Label
LeetCode : Partition Label
2021.07.07https://leetcode.com/problems/partition-labels/submissions/ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public List partitionLabels(String s) { //last Index 넣어라 HashMap hm = new HashMap(); String[] splitMsg = s.split(""); for(int i=0; i
KAKAO_[3차]압축
KAKAO_[3차]압축
2021.07.071 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.util.*; class Solution { public int[] solution(String msg) { int[] answer = {}; HashMap hm = new HashMap(); HashMap checkSearch = new HashMap(); String[] alphabet = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",..
Kakao_보석쇼핑
Kakao_보석쇼핑
2021.06.10시작 효율성을 검증하는 문제다. 사실 문제 요구사항은 크게 어렵지 않다. 다만, 보석의 개수가 100,000 이라는 점에서 반복문을 2번만 돌려도 시간초과가 날 수 있으니 유의해야 한다. 배열의 범위가 커지면 O(N)이나 혹은 그 이하로 프로그램이 수행해야 하는 경우가 종종 있다. 이 문제를 접근해서 해결할 수 있는 방법은 투포인트 방법이 있다. 여기서는 원포인트, 투포인트 접근 모두 다뤄보고자 한다. 알고리즘 동작 원리(투포인트) 쉽게 말하면 보석을 조금씩 덜어내고 마침내 사라지면 마지막으로 보석을 본 시점부터 끝까지 돌며 해당 보석을 찾아가는 과정을 나열한 것이다. 조금 복잡해 보이지만, 별거 없다! 눈여겨 봐야할 것은 1. 중복제거해서 쥬얼리 종류 파악 2. HashMap에 각 쥬얼리가 얼만큼 등장..
BOJ_14864_줄서기
BOJ_14864_줄서기
2021.05.30시작 줄서기 문제는 Ad-hoc 으로 문제 분류가 되어있습니다. 이 알고리즘을 찾아보니, 창의력 문제 정도로 찾아볼 수 있었습니다. 규칙? 문제를 읽고 손으로 끄적이다가 대강 넣어보니 이렇게 들어가는 구나 이해를 했습니다. 아래는 그 손으로 끄적인것을 그림으로 도식화 한것입니다. 근데 막상 규칙을 찾아보려 하니 규칙이 눈에 띄진 않았지만 괄호안에서 왼쪽, 오른쪽 사이에는 대소 비교관계가 있고 왼쪽이 오른쪽보다 크기 때문에 묶어 생각해보면 학생1이 가진 숫자는 최소 2개의 숫자보다 크게 됩니다. 그렇기 때문에 +2 라는 표시를 했고 학생5의 경우에는 최소 3개의 숫자보다 작게 됩니다. 마찬가지로 -3라는 표시를 했습니다. 그렇게 보니, 초기 값 N=5라면 Array 각 인덱스에 1,2,3,4,5 가 순서대..
BOJ 5719 거의 최단 경로
BOJ 5719 거의 최단 경로
2021.05.27시작 https://lotuslee.tistory.com/137 본문을 참고하였습니다. 문제를 읽어보면 한가지 좋은 아이디어를 생각해볼 수 있었는데 구현이 쉽지 않았습니다. 아이디어는 비교적 간단합니다. 1. 다익스트라로 최단 경로를 구합니다. 2. 최단 경로들을 모두 제외 합니다. 3. 다익스트라로 다음 최단 경로를 구합니다. 그림으로 보면 다음과 같습니다. 각 순서는 그림에서 왼쪽부터 1, 2, 3으로 확인해 볼 수 있습니다. 소스코드를 우선 살펴보겠습니다. 코드 중에 preNodeCollections, ArrayList 를 선언해 두었습니다. 최소 비용을 가진 경로를 담아두기 위한 목적인데, 거리 값이 갱신 되면 왼쪽에 보이는 1번 경로가 clear 되고 2번 경로가 preNodeCollection..
다익스트라 X BOJ_4485_녹색옷입은애가 젤다지?
다익스트라 X BOJ_4485_녹색옷입은애가 젤다지?
2021.05.26시작 다익스트라 개념에 대해 정리한것을 포스팅 합니다. 다익스트라는 기본적으로 최단 경로로 많이들 알고 있지만, 최단 경로는 BFS 로도 접근할 수 있기 때문에 여기서 최소 비용 개념을 추가해주어야 합니다. 즉, 다이스트라는 최단 거리 + 최소 비용의 문제입니다. 조건 보통의 다익스트라의 문제 경우 아래 조건들을 만족합니다. 1. 방향 그래프 입니다. 2. 0 이상의 가중치 값을 가지고 있습니다 3. 사이클이 존재하지 않아야 합니다. 구현 (코드X) 다익스트라의 경우 BFS 개념에 그리디 알고리즘을 적용합니다. 덧붙이면, 최단 거리를 구하게 되지만 매 순간 가장 좋은 가중치 값을 선택하게 됩니다. 거리, 방문 여부 변수를 두어 다익스트라 알고리즘이 어떻게 동작하는지 살펴보겠습니다. 그림 처음 워크플로우는..