알고리즘
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 개념에 그리디 알고리즘을 적용합니다. 덧붙이면, 최단 거리를 구하게 되지만 매 순간 가장 좋은 가중치 값을 선택하게 됩니다. 거리, 방문 여부 변수를 두어 다익스트라 알고리즘이 어떻게 동작하는지 살펴보겠습니다. 그림 처음 워크플로우는..
프로그래머스 튜플(Java)
프로그래머스 튜플(Java)
2021.05.24소개 이 문제는 2019 카카오 개발자 겨울 인턴십으로 출제되었던 문제이다. 해당 문제에 대한 아이디어는 다음과 같다. 로직 1) 연속된 숫자를 추출하여야 한다. 2) 1의 목적을 위해서 자료구조 HashMap을 사용하였다. 3) HashMap의 경우 같은 Key라면 (default :1) +1 씩 더해주었다. 4) 결과적으로 Value (HashMap의 Key에 따른 Value) 로 내림차순하여 순서대로 Key값을 출력해 주었다. 구체화 해보면 다음과 같다. 이를 그림으로 도식화 하면 다음과 같다. 소스코드 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..
BOJ_1781_컵라면
BOJ_1781_컵라면
2021.05.23시작하면서 해당 문제는 pq 외에도 그리디한 방법으로 해결해 볼 수 있는데, 포스팅에서는 pq로 푸는 방법에 대해 고민해봤습니다. 여러 알고리즘 로직을 세워서 문제를 접근했는데, 9%에서 "틀렸습니다." 가 나와서 참으로 힘들게 했던 문제입니다. 문제 접근 시 데드라인과 컵라면 수를 잘 고려해봐야 하는데 데드라인은 우선순위를 높게, 같다면 컵라면 수는 더 큰것을 정해서 큐에 담아주어야 합니다. 처음 생각한 점 우선순위 큐를 지정했을 때 정렬 순서를 1. 데드라인은 우선순위를 높게 2. 컵라면 수는 더 큰것을 지정 3. 우선순위 큐에 Max-heap 구성 (데드라인 기준으로 push 할 경우 더 높은 숫자의 데드라인이 pop되는 것을 고려) ex) pq에 {1,7} 이 있다고 고려 하면, 새롭게 {2,6}..
프로그래머스 행렬 테두리 회전하기
프로그래머스 행렬 테두리 회전하기
2021.05.21프로그래머스에서 삼성 역량 테스트에 기본 문제가 될 수 있는 좋은 문제를 찾아 풀어보았습니다. 콘솔화면에 맵에 저장되어 있는 값을 출력하며 방향에 따라 맵에 값이 갱신되는지 체크하며 문제를 해결하였습니다. 처음에는 for 문을 돌면서 확인해보려 했는데, DFS로 반복 탐색을 수행하면 코드 가독성을 높일 수 있을것이라 생각하여 DFS로 접근하였습니다. DFS로 접근 ⏤ 방향 정하기 DFS에 접근할 때 dir 1,2,3,4 로 구성하여 문제를 접근하였습니다. Main에서 DFS에 넘겨주는 params dir가 1, 2일 때 경우 처음 DFS를 진행할 때 시작 지점인 sx, sy에서 시작하는 것이 아닌 sx, sy+1 로 시작지점을 선택하였습니다. 이전 값은 세번째 인자로 전달하여 좌표는 다음 좌표를 바라보고..
프로그래머스 짝지어 제거하기
프로그래머스 짝지어 제거하기
2021.05.20이 문제를 처음 시도할 때는 for 문으로 순회하며 같은 알파벳이 있는 경우 (현재 인덱스, 다음 인덱스) 를 넘어가고 다음 알파벳을 체크 하였다. 로직을 수행할 때는 다음 순서를 따른다. 1) 현재 알파벳과 다음 알파벳을 비교 2) 새로 만든 문자열을 가지고 1번을 수행 TC는 통과했지만, 결국 시간 초과 가 났다. 그러면 어떻게 푸는것이 효과적일까? 정답은 Stack 은근 간단하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*; class Solution { public int solution(String s) { int answer = -1; char[] chas = s.toCharArray(); Sta..
완주하지못한선수 / k번째 수
완주하지못한선수 / k번째 수
2021.05.08Javascript로 두 문제를 풀어보았습니다. 관련해서 Javascript 문법이나 특이점을 정리해보고자 합니다. 1) 완주하지못한선수 HashMap을 사용해서 해결할 수 있는 문제였는데 Javascript에서 HashMap을 정의할 때 아래와 같이 사용합니다. HashMap에 데이터를 삽입한 후 for loop으로 데이터를 조회할 때에는 아래와 같이 사용합니다. 이 문제에서는 특별한 로직이 필요없습니다. 여러 풀이법이 있겠지만 HashMap을 이용하면 쉽게 접근할 수 있습니다. Code 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 function solution(participant, completion) { var ans..
알고리즘 :: 신규 아이디 추천 (javascript)
알고리즘 :: 신규 아이디 추천 (javascript)
2021.05.07javascript에 익숙해지기 위해 관련 언어를 서칭하며 문제를 해결해 보았습니다. 관련 문제는 2021 KAKAO BLIND RECRUITMENT 신규아이디추천 입니다. 정규식을 알아야 풀 수 있는 문제라고 접근했는데 서치해보니 문자열의 각 문자를 참조할 수 있는 방법에 대해 공부할 수 있었습니다. MDN Web Docs에서 관련 내용을 참고해보면 ThecharCodeAt()method returns an integer between0and65535representing the UTF-16 code unit at the given index. 로 소개되어있습니다. 즉, Unicode로 반환되기 때문에 우리가 은히 알고있는 아스키 코드표를 참고해서 비교해봄으로써 문제에서 요구한 사항을 지켜낼 수 있습니..
BOJ 1619, 최소비용구하기
BOJ 1619, 최소비용구하기
2020.11.08문제유형 다익스트라 문제풀이 다익스트라 기본 문제, 원리를 이해하고 풀면 좋습니다. 이차원 a 배열을 생성, a값을 모두 inf(1000000000) 로 초기화 x,y,z 값을 입력으로 받는다. 그리고 a[x][y] 가 z보다 큰경우 값을 업데이트 한다. (작은값을 찾아야 하므로) start, end를 입력으로 받는다. d를 배열로 생성한다. n+1 만큼 /마찬가지로 방문여부를 확인할 수 있는 c를 n+1만큼 선언 및 초기화 n만큼 d에 inf 를 업데이트, n만큼 c를 false 로 업데이트 d[start] = 0 으로 초기화 시작지점, d의 역할은 비용 이라고 보면됀다. 반복문을 n-1 만큼 순회한다. 노드의 최솟지점을 찾아야 하므로 min과 x를 선언합니다. (min은 최댓값으로 x는 -1), x는..
숨바꼭질4
숨바꼭질4
2020.11.07문제유형 BFS, 단순구현 문제풀이 모듈 2가지 1. BFS -. x+1, x-1, x*2 방문체크 -. 방문하지 않았다면 큐에 대입 -. 역추적을 위해 from[now] = next 형태로 저장, 재귀함수를 통해 마지막에 추적하기 위함 e.g) 1->2->3->4 면 from[4] = 3, from[3] = 2, from[2] =1 이런식 2. 역추적 -. 재귀함수로 역추적 코드 package backjun; import java.io.*; import java.util.*; public class BOJ_13913_숨바꼭질4 { static void print(int n, int m, int[] from) { if(n!=m) { print(n, from[m], from); } System.out.pr..