2JINISHAPPY 2JINISHAPPY

Comparable과 Comparator는 모두 Java의 인터페이스이다 단어도 비슷하고, 인터페이스 내 메소드 내 구현해야 할 메소드 명도 비슷해서 항상 용법이 헷갈리지만 엄연히 역할들이 분류되어 있었다. Interface Comparable Comparable은 java.lang package에 존재하는 public interface이며 이 인터페이스를 구현하는 클래스의 객체는 순서를 정의할 수 있는 규칙을 부여할 수 있다. Collections.sort(Arrays.sort)를 할 때 인자로 Comparator를 넘겨 주지 않아도 되며 sorted map이나 sorted set에서도 그 order가 적용된다. public class Point implements Comparable { int x; ..

Bellman-Ford(벨만 포드) 알고리즘은 Dynamic Programming 기반으로 Edge-Weighted Graph에서 최단거리를 계산하는 알고리즘이다. 특정 Vertex(source)에서 다른 모든 vertex로의 shortest path를 구하며(single-source shortest path), 매 step 마다 해당 shortest path의 distance를 update하는(dynamic) 알고리즘이다. 이 때, 다른 알고리즘과 구분되는 점은 Edge의 Weight가 negative여도 올바르게 동작한다는 점이다. 벨만 포드 알고리즘은 다음의 recurrence relation 아래 작동한다. dist(u) = vertex s에서 u까지의 실제 shortest path의 길이 dis..

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 내가 기존에 못 하던 유형인 DP, 이진탐색을 연습할 필요성을 느껴서 간간히 풀어보려고 한다 대표적인 문제인 나무자르기 사실 옛날에는 봐도 감이 안 와서 몇번을 풀려고 트라이했지만 실패했었는데 스터디에 이진탐색 빡고수분의 지도를 몇 번 받아 이제 감이 슬슬 오고있따 이진탐색 문제는 left, right 변수를 설정하는 것이 가장 핵심인 것 같다. 처음부터 이진탐색 솔루션이..

www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 주어진 알파벳 string의 해석 경우의 수를 구하는 DP문제 수를 한 자리, 두 자리 씩 끊을 때 나올 수 없는 숫자의 범위가 있기 때문에 그 경우를 고려해주어야 한다. -2만큼 이전에 있는 인덱스를 참조하기 때문에 base case를 위해 앞에 dummy string을 추가해주었다. #include #include #define MOD 1000000 using namespace std; string str; int dp[50..

www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 스터디 문제 풀이용으로 급하게 서치한 문제인데 굉장히 유익한 것 같아서 포스팅 로봇의 시작 좌표 S가 주어지고, 열쇠의 좌표 K(여러 개)가 주어졌을 떄 모든 열쇠를 얻을 수 있는 최단거리 이동 경로를 구해야 한다. 이 때, 이동 경로에는 가중치가 없고(BFS를 이용한 최단거리 계산) 열쇠가 복사가 가능하기 때문(S에서만 K를 도달할 수 있는게 아닌, K에서 다른 K로도 이동 가능..

programmers.co.kr/learn/courses/30/lessons/17686# 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr 이때까지 외워서 사용했던 정렬 comparator에 대해 생각하게 해주는 문제 카카오 2018년 기출은 풀면서 배워가는게 많은 것 같다 파일명 정렬에서는 파일 이름 string을 HEAD, NUMBER, TAIL 세 파트로 나눈 뒤 각각의 order에 따라 정렬을 해주어야 한다. 문자열 토큰화가 크게 복잡하지 않았기 때문에 C++로 풀이했다. 처음 설계했던 풀이 ..

파이썬으로 프로그래밍을 하면 프로그래머스 류의 코딩테스트에서 종종 시간 관련 문제를 만날 수 있다. 시간을 처리하는 메소드를 직접 구현하기 보다는 Python의 Datetime 모듈을 활용하는 것이 더 효율적일 때가 많아서 정리해보려고 한다. 1. datetime 모듈의 datetime 클래스 포함하기 import datetime #ex) datetime.datetime.today() # >> datetime.datetime(2021, 3, 23, 22, 50, 49, 881617) 현재 날짜와 시간을 구할 때는 today 메소드를 사용한다. UTC 기준으로 구하는 방법도 있지만 설명은 생략한다. 2. 특정 날짜와 시간으로 객체 만들기 datetime.datetime(year, month, day, ho..

그래프 G 상에서 vertex u에서 v로의 가장 짧은 path의 길이를 찾는 문제를 최단경로 문제라고 한다. 최단 경로 문제는 주로 1️⃣ edge에 weight가 존재하는지 2️⃣ edge weight 범위가 0이상인지/정수인지 3️⃣ 특정 vertex u에서 도달 가능한 path만 구하는지/모든 vertex set에 대해 구하는지 에 따라 사용할 알고리즘을 정하게 된다. 그 중 Dijkstra Algorithm은 edge에 weight가 존재하면서, 범위가 0 이상 이고 특정 vertex u에서 도달 가능한 vertex들의path를 구할 때 사용하는 알고리즘이다. 위 그림과 같은 형태에서 vertex f -> d로의 path는 여러 형태가 존재할 수 있지만, shotest path는 f-b-a-c-..