본문 바로가기

Algorithm

[백준 1695] 팰린드롬 만들기 - Java 코드
2022. 5. 6. https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 문제 이해 앞뒤가 똑같은 번호를 팰린드롬이라 한다. 입력 수가 주어지면, 해당 수열에 몇번의 숫자를 끼워 넣어야 팰린드롬으로 만들수 있는지를 구한다. 이 문제는 이차원 배열 DP를 만들어서 최솟값 메모이제이션을 통해 답을 구한다. 풀이 DP 배열은 n x n 크기로 선언후 -1로 채운다. 그리고 입력받은 arr값에 양 끝을 비교해가면서 팰린..
[백준 2632] 피자판매 - Java 코드
2022. 5. 6. https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 문제 이해 나는 이 문제를 어떻게 이분탐색으로 풀어야 할지 모르겠다. 분명 이분탐색을 더 공부하고 싶어서 골랐지만... 경우의 수 문제는 그냥 해당 경우의 수를 구하는 방법밖에 생각이 나지 않았다. 풀이 경우의 수를 구해주는 풀이법 피자마다 각각 조합의 값이 몇개가 나오는지 count해주는 DP 배열을 만들었다. 피자의 조합의 경우의 수를 Count할 때, 몇가지 예외사항이 있..
[백준] 14. 동적계획법1 - Java코드😨
2022. 4. 21. https://www.acmicpc.net/step/16 동적 계획법 1 단계 i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다. www.acmicpc.net 동적계획법은 메모이제이션이 핵심! 단순하게 연산이 반복되는 문제나, 여러 재귀호출이 있는 경우, 또는 이전연산으로 이후의 결과를 만들수있는 경우에 DP 개념을 도입해 값을 캐싱하도록 구현하므로 보다 빠르게 문제를 해결하는 방법이다. 목차 ✅ 1 1003 피보나치 함수 31.311% ✅ 2 9184 신나는 함수 실행 41.947% ✅ 3 1904 01타일 32.360% ✅ 4 9461 파도반 수열 41.897% ✅ 5 1149 RGB거리 50.640% ✅ 6 1932 정수 삼각형 58.635% ✅..
[백준 1780] 종이의 개수 - Java 코드 (분할정복)
2022. 4. 18. https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 이해 분할정복은 매트릭스가 주어지며, 잘라야하는 숫자의 k승 이하로 주어진다. 해당 문제는 3의 k승 이하로 주어졌으며, 3으로 분할정복할때 나누어 떨어지는 input임을 알 수 있다. 풀이 입력은 BufferedReader로 결과는 HashMap에 -1, 0 , 1을 각각 저장해주는 형태로 구현하였다. 물론 3칸짜리 배열을 이용해도 괜찮다. import java.io.Buffer..
[백준] 13. 백트래킹 - Java 코드
2022. 4. 15. https://www.acmicpc.net/step/34 백트래킹 단계 삼성 SW 역량 테스트 기출 문제 2 www.acmicpc.net 문제 목차 ✅ 1 15649 N과 M (1) ✅ 2 15650 N과 M (2) ✅ 3 15651 N과 M (3) ✅ 4 15652 N과 M (4) ✅ 5 9663 N-Queen ✅ 6 2580 스도쿠 ✅ 7 14888 연산자 끼워넣기 ✅ 8 14889 스타트와 링크 대체적으로 백트레깅 문제에서는 순열과 조합을 이용한 문제가 많이 출제된다. 난이도가 올라갈수록 bfs의 개념으로 구현하는 문제가 나온다. 해당 단계에서는 5번 N-Queen, 6번 스도쿠 문제가 난이도가 있어고 재밌었기 때문에 따로 풀이 글을 작성할 예정이다. ✅ 1 15649 N과 M (1) import ..
[백준 1922] 네트워크 연결 - Java코드 (크루스칼)
2022. 4. 9. https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 문제 이해 문제 이해는 어렵지 않다. N개의 노드에 대한 M개의 간선정보(from , to , cost) 가 입력되는데 , 모든 노드를 연결되는 최소비용을 구해주면 된다. 방법 이해 ★ 최소비용, 최단거리 그래프 (노드) 연결 문제를 MST , Minimum Spanning Tree (최소신장트리) 라고 말한다. Greedy (탐욕법) 문제유형 중에 대표적인 유형의 문제이다. 이런 MST 유형의 문제를 푸는 정형화된 알고리즘이 존재하는데, 바로 그 유명한 "크루스칼(Kruskal)..
[고득점 Kit] 문제 풀이를 마치며...
2022. 3. 30. 첫번째 바퀴 - 21년 6월 동기와 첫 스터디 회사동기들과 무작정 시작했던 알고리즘 공부. 일주일에 한 챕터씩 매주 머리싸매고 고통중에 답 안보겠다고 말하면서 일주일간 고민하다가 몰래 정답 찾아가며 알고리즘 문제를 접하고 풀었었다. 그렇게 10개 쳅터를 3달간 풀면서 우리는 알게모르게 많은것들을 학습할 수 있었고, 다양한 부분에 확장해가면서 무지했던 자바문법과 개념들을 학습해나가는 시발점이 되었다. 이 첫 스터디를 시작으로 자바 8을 쓰는 자바 개발자로 재직중이면서도 Stream, Lambda, Optional, Collections, Generic 등에 굉장히 무지했던 내 자신을 부끄러히 여기고, 자바 문법을 다시 점검하고 공부하면서, 무지해서 더 많은 공부의 필요성을 느끼며, 동력을 얻을 수 있었다...
[Heap] 이중 우선순위 큐 - Java코드
2022. 3. 25. https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제 이해 우선순위큐를 최소값 정렬과 최댓값 정렬로 2개를 만들면 쉽게 풀 수 있다. 풀이 import java.util.Collections; import java.util.PriorityQueue; import java.util.StringTokenizer; class Solution { public static int[] solution(String[] operations) { int[] answer = new int[2]; //최소 힙, 최대 힙 PriorityQueue pq = new PriorityQueue(); Priority..
[Heap] 디스크 컨트롤러 - Java코드 ★★★
2022. 3. 25. https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제 이해 반가운 개념이 나타났다. (OS시간에 배웠던 SJF 방식) 입력으로 작업의 요청시간과 수행시간이 들어온다. 가장 짧은 Job부터 스케줄링하면 각각의 Job이 요청시간으로부터 대기시간과 수행종료 시점까지의 시간의 총 평균시간이 가장 짧은 스케줄링 기법이다. 해당 기법을 Java로 짜보는건 처음이지만, Heap을 이용해 정렬된 요청시간과 대기시간을 ..
[Heap] 더 맵게 - Java 코드
2022. 3. 24. https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제 이해 정렬의 개념이 필요하다. Heap (PriortyQueue) 자료구조에 들어가므로 오름차순 정렬되는 특성을 이용하여 매개변수로 받는 스코빌지수가 정렬되면, 첫번째 원소(peek)가 K를 만족하는지 체크하면서 poll() 를 통해 가장 맵지 않은 두 원소를 차례로 빼서 새로운 조합을 다시 힙에 넣어주며 풀면 된다. 풀이 import java..
[스택/큐] 주식가격 - Java 코드 ★★★
2022. 3. 3. https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 문제 이해 각 원소의 유지되는 시간은 한 인덱스당 1초이다. 마지막 원소의 유지시간은 무조건 0이다. 배열을 사용한 풀이 완전탐색을 이용하면 보다 직관적이고 수월하다. class Solution { public int[] solution(int[] prices) { // 완전탐색은 n2 순회 int[] res = new ..
[스택/큐] 다리를 지나는 트럭 - Java코드 ★★★
2022. 3. 3. https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 문제 이해 다리에 트럭이 선입 선출되는 문제이므로 FILO이 아닌 FIFO에 큐를 이용한다. 큐에 들어간 무게합은 wegith보다 작은지 검사하면서 다리라는 Queue를 활용하여 무게의 합을 관리하면서 초를 재야한다. 설계 문제 체감상 Lv2가 아닌 Lv3정도는 되는것 같다. 다리의 길이만큼을 가지는 Queue를 설계하고 싶었지만, 큐..
[스택/큐] 프린터 - Java코드
2022. 2. 22. https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 문제 이해 문제를 보면, 해당 location에 있는 문서가 몇번째로 출력되는지를 구하는문제인데, 차례대로 우선순위를 확인하여 , 우선순위가 아니면, 작업을 맨뒤로 보내버린다. 즉. 선입 선출 구조의 큐를 이용해야 한다. Peek 작업이 Queue가 가지는 max값(최고 우선순위값)이 아니라면 맨뒤에 넣어주는 작업을 하면서, 해를 구하면 되겠다. 풀이 입력으로 들어..
[스택/큐] 기능개발 - Java코드
2022. 2. 22. https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 문제 이해 문제를 상세히 읽어보면 각각의 일률을 구할 수 있고, 들어온 순서대로 종속적인 업무이기 때문에, 앞에서 배포가 되지않으면 뒤에 업무가 완성되어도 배포할 수 없다. 이 문제는 선입 선출로 순서배포가 일어나는 구조이기때문에, 스택이아닌 큐 자료구조를 이용한다. 일률을 큐에 저장하고 peek값에 일률보다 작거나 같은것들을 count해주면서 함께 배포..
[백준] 12. 정렬 - Java 코드
2022. 2. 22. https://www.acmicpc.net/step/9 정렬 단계 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다. www.acmicpc.net 백준문제는 생각보다 메모리와 시간제한이 빡빡한 편이다. 입력은 Scanner보다는 BufferdReader를 출력은 단순 for문 출력보다 StringBuilder로 받아 출력하는걸 기본으로 작성해야 한다. 정렬은 Arrays.sort O(n)~O(n2)보다 Collections.Sort O(nlogn)가 빠른 속도를 보장하지만, Collections의 List, Set, Map를 사용하기 위해서는 Input의 범위와 ..
[백준] 11. Brute Force - Java 코드
2022. 2. 17. https://www.acmicpc.net/step 단계별로 풀어보기 단계별은 @jh05013님이 관리하고 계십니다. 단계제목설명정보총 문제내가 맞은 문제1입출력과 사칙연산입력, 출력과 사칙연산을 연습해 봅시다. Hello World!132if문if문을 사용해 봅시다.73for문for문을 www.acmicpc.net BruteForce (무차별 공격) 암호학에서 비밀번호를 찾는 방법론. 조합 가능한 모든 경우를 하나씩 다 대입해 보는 방식으로 암호를 해독하는 방법. 브루트 포스 공격(brute force attack) , 키 전수조사(exhaustive key search), 무차별 대입 공격, 완전 탐색 등으로도 부른다. 알고리즘의 대다수의 문제가 브루트 포스와 같이 경우를 완전 탐색하며 해를 구하는 ..
[백준 1431] 시리얼 번호 (정렬) - Java코드
2022. 2. 17. https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 문제 이해 문자열을 입력받는값들을 배열에 저장하고 Comparator를 활용해서 잘 정렬해주어 출력하면 된다. 정렬에 3가지 기준은 아래와 같이 작성하였다. 길이를 비교는 length로 비교 문자열에서 숫자만 추출하여 합을 구하는 부분은 Regular Expression을 통한 치환후 for으로 합을 구하는 함수생성 마지막 사전순은 String.compareTo 메소드를 말한다. 풀이 imp..
[KAKAO 2021] 합승 택시 요금 - Java 코드 (Dijkstra) ★★★★
2022. 1. 19. 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 문제 이해 출발지점이 정해져있고, a,b를 포함하는 최단경로를 구하는 문제이기때문에..
[백준 1753] 최단경로 -Java코드 (Dijkstra)★★★
2022. 1. 19. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 설계 이 문제는 그래프의 최소경로값을 구하는 문제이다. 최소경로 문제는 BFS, Floyd Warshall(플로이드 와샬), 다익스트라(Dijkstra) 알고리즘 등으로 풀 수 있다. 가중치 개념이 없는 단순 최소경로문제 -> BFS 가중치 개념이 있는 한 노드기준의 최소경로값 -> Dijkstra (다익스트라) 가중치 개념이 있는 모든 노드기준의 최소경..
[백준 2606] 바이러스 - Java 코드
2022. 1. 17. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 접근 네트워크에 대한 입력값들을 이차원 배열에 담고, 방문여부를 체크할 Bool 배열을 선언하여 dfs를 구현해주었다. 풀이 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ..

티스토리툴바