전체 글

전체 글

    알고리즘/프로그래머스

    [devmoon] 프로그래머스 - (Java) 소수 만들기

    https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 1. 유형 수학, 조합 2. 시뮬레이션 에라토스테네스의 체 소수판단 조합 배열에서 3개를 선택하면 그 합이 소수인지 판단하면 된다. 소수판단은 효율성을 생각해서 에라토스테네스의 체를 사용한다 3. 코드 class Solution { static boolean matrix[]; static int Nums[]; static int ans=0; ..

    [devmoon]프로그래머스 - (java)합승 택시 요금
    알고리즘/프로그래머스

    [devmoon]프로그래머스 - (java)합승 택시 요금

    https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 1. 유형 플로이드-와샬, 최단거리 탐색 2. 시뮬레이션 노드의 개수 N이 최대 2..

    [devmoon]프로그래머스 - (Java) 섬 연결하기
    알고리즘/프로그래머스

    [devmoon]프로그래머스 - (Java) 섬 연결하기

    https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 1. 유형 그리디 2. 시뮬레이션 이번 문제는 프림, 크루스칼을 사용하여 해결가능하다. 이전에 크루스칼을 사용했으니, 이번엔 프림을 사용한다. testcase에 대한 시뮬레이션 아래도 마찬가지로 0,1번 노드와 연결된 가장 작은 간선을 선택 최종값은 아래와 같이된다. 3. 코드 import java.util.*; class Solution { static PriorityQueue pq; static List list[]; public int solution(i..

    [devmoon] 백준 1197 - (Java)최소 스패닝 트리
    알고리즘/백준

    [devmoon] 백준 1197 - (Java)최소 스패닝 트리

    https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. 유형 프림, 크루스칼, union-find 2. 시뮬레이션 1. 크루스칼 알고리즘 uion-find를 활용한다. 두 노드의 부모가 일치하면 연결됐다는 의미 다르다면 연결이 안 됐다는 의미 3. 코드 1. 크루스칼 import java.io.*; import java.util.*; public class Main { static class Node..

    [devmoon] 백준 1976 - (java)여행 가자
    알고리즘/백준

    [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)외벽 점검
    알고리즘/프로그래머스

    [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진수 게임
    알고리즘/프로그래머스

    [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)이진 변환 반복하기
    알고리즘/프로그래머스

    [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)점프와 순간 이동
    알고리즘/프로그래머스

    [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]프로그래머스 - 쿼드압축 후 개수세기
    카테고리 없음

    [devmoon]프로그래머스 - 쿼드압축 후 개수세기

    https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 1. 유형 구현 2. 시뮬레이션 두가지 접근법이 있다 - 재귀 - 그냥 반복문 빨간색 칸을 순서대로 탐색하며, 길이만큼 사각형 안에 0,1의 갯수를 세준다. 3. 코드 cla..

티스토리툴바