알고리즘
![[devmoon] 백준 1976 - (java)여행 가자](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcXKkEP%2Fbtq8pil6r80%2FBUk2QB1UYpbkN1ZkynsYG0%2Fimg.png)
[devmoon] 백준 1976 - (java)여행 가자
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 유형 union-find 2. 시뮬레이션 하나하나 다음 노드가 연결됐는지 확인하는 문제가 아니다. 경로가 한 덩어리로 이어져 있는지만 확인하면 된다. 따라서 각 노드의 "최고"부모노드가 전부 같으면, 노드가 전부 연결 돼있다는 의미. 부모노드를 구하기 위해 union-find알고리즘을 활용 3. 코드 import java.io.*; import java.util.*; public class ..
![[devmoon]프로그래머스 - (Java)외벽 점검](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbi2tHT%2Fbtq8fXuQSmG%2FzOMA9tKnHyFleO5HiuZXf1%2Fimg.png)
[devmoon]프로그래머스 - (Java)외벽 점검
https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 1. 유형 구현 2. 시뮬레이션 1. 한점을 선택 2. 가장 먼 곳을 탐색할 수 있는 사람부터 사용 3. 모든 weak를 탐색할 수 있을때까지 위를 반복 위 처럼 시뮬레이션을 돌리면, 가장 먼저 1을 선택 후, 2가지 경우의 수가 나온다. 9 선택하는 경우 -> 5만큼 탐색하면 모든 weak탐색가능 ->2명 필요 10 선택하는 경우 -> 5만큼 탐색해도 9번은 ..
![[devmoon]프로그래머스 - n진수 게임](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdwStq2%2Fbtq7XsXkSDK%2FUyB0LkejSjhet79SYJwSYK%2Fimg.png)
[devmoon]프로그래머스 - n진수 게임
https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 1. 유형 재귀, 구현 2. 시뮬레이션 0부터 수를 1씩 증가 수를 n진법으로 전환 튜브의 순서에 맞는 변환된 n진법수를 선택 위를 튜브가 t개 선택할 때까지, 반복 3. 코드 - 이진법 전환 코드 - 탐색코드 class Solution { public String solution(int n, int t, int m, int p) { String..
![[devmoon] 프로그래머스 - (Java)이진 변환 반복하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdnT8X1%2Fbtq7XsXgcmt%2FDb9kCSs9jyaTnCzchrc1uK%2Fimg.png)
[devmoon] 프로그래머스 - (Java)이진 변환 반복하기
https://programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 1. 유형 재귀 2. 시뮬레이션 그냥 요구 조건대로 구현하면 될듯 3. 코드 import java.util.*; class Solution { public int[] solution(String s) { int[] answer = {}; List list = new ArrayList(); int zeroCount=0; int turnCount=0; while(!"1".equals(s)){ list.clear(); for(char c : s.toCharArray()){ if(c=='1'){ list.add(c); }else zeroCo..
![[devmoon] 프로그래머스 - (java)점프와 순간 이동](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FR2S6x%2Fbtq7Z1KtxL9%2Fcnc0bryeDcRjyKM2fwRHo0%2Fimg.png)
[devmoon] 프로그래머스 - (java)점프와 순간 이동
https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 1. 유형 재귀, 수학 2. 시뮬레이션 2가지 접근법 동적프로그래밍 수학 우선 DP를 이용한 풀이는 불가능. N이 10억으로 시간초과가 발생 따라서, 재귀+수학으로 풀이 아래와 같이 나머지가 1인 경우의 수를 세어주면 된다. 재귀 사용 3. 코드 import java.util.*; public class Solution { public i..
![[devmoon]프로그래머스 - 방문 길이](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbEKCT6%2Fbtq7QPkR9pk%2FrsmkdkIzHGUnTTpnjKwXnk%2Fimg.png)
[devmoon]프로그래머스 - 방문 길이
https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 1. 유형 구현 2. 시뮬레이션 한 점은 방문하는 방향에 따라 여러가지 경우의 수가 나옴. 따라서 3차원 배열을 활용해서 방문체크 'U'일때, 2가지 경우의 길에 대해서 방문체크를 해야한다. 3. 코드 import java.util.*; class Solution { static int D[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; static int N=10; static public int solution(String dirs) { int answer = 0; char arr[] = dir..
프로그래머스 - JadenCase 문자열
https://programmers.co.kr/learn/courses/30/lessons/12951 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr 1. 유형 문자열 2. 시뮬레이션 모두 소문자로 변환 문자열을 탐색하면서, 공백 + 소문자인 경우 대문자로 전환 3. 코드 import java.util.*; import java.util.regex.*; class Solution { public String solution(String s) { Str..
프로그래머스 - 압축
https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 1. 유형 해시맵 2. 시뮬레이션 딕셔너리에 등록되지 않은 가장 긴 문자열 탐색 등록되지 않은 문자열은 딕셔너리에 등록 문자열 끝까지 위를 반복 3. 코드 import java.util.*; class Solution { static List ans = new ArrayList(); static Map map = new HashMap(); static int index =27; sta..
프로그래머스 - 이중우선순위큐
https://programmers.co.kr/learn/courses/30/lessons/42628# 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 1. 유형 우선순위큐 2. 시뮬레이션 우선순위큐에 [인덱스, 값] 형태로 집어 넣는다. 아래 처럼 내림, 오름 차순으로 우선순위큐를 선언 D가 나올때마다, 방문배열에 체크한다 따라서 max, min큐에서 방문 배열이 false인 것이 정답이다. 3. 코드 import java.util.*; class Solution { public int[] solution(String[] operations) { int[] answer = {0, 0}; PriorityQueue min = new PriorityQueue(new Comparator(){..
프로그래머스 - 보행자 천국
https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 1. 유형 DP 2. 시뮬레이션 로직 맵을 완전탐색 한다. 현재의 칸에서 상, 좌를 확인한다 이전 칸이 0 OR 2에 따라 분기한다. 위의 그림의 공식대로 Dp에 저장 위를 n-1,m-1 좌표까지 반복 3. 코드 class Solution { int MOD = 20170805; public int solution(int m, int n, int[][] c..
프로그래머스 - 단어변환
https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 1. 유형 DFS 2. 시뮬레이션 로직 완전탐색으로 1자리만 다른 단어가 있는지 탐색 DFS 3. 코드 class Solution { static int N, INF= Integer.MAX_VALUE; static boolean visited[]; static String[] Words; public int soluti..
프로그래머스 - 셔틀버스
https://programmers.co.kr/learn/courses/30/lessons/17678# 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 1. 유형 구현 2. 시뮬레이션 로직 timetable을 모두 "분"으로 전환 후, 오름차순 정렬 버스에 m명까지 태우기 만약 m명 미만이다. 현재 버스시간이 정답 m명이다. 마지막에 탄 사람의 시간-1이 정답 분 -> 시 3. 코드 import ja..
프로그래머스 - (Java) 가장 긴 팰린드롬
https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 1. 유형 문자열 2. 시뮬레이션 로직 총 길이 설정 시작 위치를 설정 양 끝에서 중앙으로 이동하면서 문자가 같은지를 판단 3. 코드 class Solution{ public int solution(String s) { int answer = 1; success:for(int len=s.length(); le..
프로그래머스 - (Java)여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 1. 유형 DFS 2. 시뮬레이션 로직 Map 형태로 자료구조 사용 DFS사용하여 완전 탐색 3. 코드 풀이1 import java.util.*; class Solution { static int N; static List ret; static public String[] solution(String[][] tickets) { ..
프로그래머스 - (Java)자물쇠와 열쇠
https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 1. 유형 구현 2. 시뮬레이션 위처럼 전체 맵을 만들고 key를 이동하면서 lock에 대입해보면서 판단한다. 로직 key가 평행이동할 전체 맵을 완전탐색한다 key를 90도 돌려준다 key와 lock이 맞는지 확인한다 3. 코드 class Solution { public boolean solution(int[][] key, int[][] lock) { boolean answer = false; int keyl..
프로그래머스 - (Java)입국심사
https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 1. 유형 이분탐색 2. 시뮬레이션 이분탐색과 수학적 지식이 있어야 풀 수 있는 문제다. 우선 시뮬레이션일 돌려보자. 그렇다면 위의 과정에서 28은 어떻게 구해야할까. 이분탐색이다. 로직 먼저 head, tail의 초기값을 설정 head가 tail보다 커질때까지 반복문을 돌린다 조건에 따라 mid값을 변경해준다. 3. 코드 class Solution { publi..
백준 - 1600 말이되고픈 원숭이 (Java)
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 유형 DP, BFS 2. 로직 bfs를 돌리면서 조건에 맞는 경우만 큐에 넣어주기 시뮬레이션을 돌리면 위 같은 상황이 나온다. 현재 좌표에서는 이전에 말처럼 이동했는지 알수 없다. 따라서 dp[말처럼 이동 횟수][행][열]인 3차원 배열에 이동거리를 저장하고, 저장한 것 보다 더 작은 이동회수가 있을겨우만 큐에 삽입하면 된다. 3. 코드 import java.io.*; imp..
프로그래머스 - (Java) 경주로 건설
https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 1. 유형 DP, BFS 2. 로직 테스트 케이스가 약간 빈약한것 같다. 반례가 존재하..
프로그래머스 - (Java) 보석쇼핑
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 1. 유형 해쉬맵, 큐 2. 로직 총 보석의 종류를 파악 해쉬맵에서 {보석이름, 개수}형태로 딕셔너리 생성 투포인터를 사용해서 모든 종류의 보석을 포함하고 있는 범위를 구함 gems가 아래처럼 주어졌다고 할때, ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 위의 그림처럼 시뮬레이션을 하면 start=3, end=4가 된다. 위의 방법처럼..
프로그래머스 - (Java)단체사진 찍기
https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 1. 유형 구현, 순열 2. 로직 순열 구하기 사람들끼리의 거리를 구한다 data배열의 조건대로 내가 구한 순열이 만족한지 판단 각 사람들끼리 떨어진 거리는 String.indexOf를 사용해서 쉽게 구할수 있었다. 3. 코드 class Solution { static char info[] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', '..