꼼개의 개발자취

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 자료구조를 잘 활용하여 풀어야하는 시뮬레이션인다. N의 크기가 100이기 때문에 값이 0인 자리에서 출발하여 모든 경우의 수를 살펴봐도 O(N^2)이다. 아마 평균적으로는 장애물들이 있기 때문에 훨씬 더 빠를 것이다. 알고리즘 1. 0이 있는곳 즉 아무 장애물이 없는 구역을 queue에 넣는다. 2. 하나씩 poll 하며 4방향으로 조건에 맞게 탐색을 진행한다. 3. 웜홀 같은 경..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 기본적인 DFS문제지만 공사 할 수 있는 것을 잘 유의하며 접근해야한다. 알고리즘 1. DFS로 가장 높은 봉우리부터 4방향 탐색을 시작한다. 2. 만약 다음 갈 수 있는 봉우리 - 현재 높이 가 공사할 수 있는 높이보다 작아야 공사가 가능하다. 3. 2번의 경우 공사 한 것을 체크 한뒤 DFS를 진행..

서론 Floyd Warshall 알고리즘은 최단 경로를 구하는 방법중 하나이다. 동적계획법으로 접근하는데 시간 복잡도는 O(N^3)이다. 최단경로 구하는 알고리즘인 dijkstra와 비교하자면 간선 수가 많으면 Floyd 가 빠를 수 있다. 시작 정점이 정해져 있으면 dijkstra가 당연히 빠르다. 음의 가중치가 존재한다면 dijkstra는 사용할 수 없지면 Floyd는 사용가능하다. 구현 코드 for i in vertex // 경유 for j in vertex //시작점 if i == j continue for k in vertex //도착점 if i == j or j==k continue arr[j][k] = min(arr[j][i] + arr[i][k] , arr[j][k]) 문제에 적용 문제 :..

문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 www.acmicpc.net 문제설명 단순 로직, 메모이제이션, 완전탐색 등 푸는 방법은 여러가지이다. 단순 로직은 빠르지만 문제가 달라지면 또 다른 로직..

문제 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 알고리즘 1. 한방향 그래프를 인접 리스트로 연결하고 도착점에 count를 증가시킨다. 2. count가 0이면 가장 앞자리거나 정보가 없는 정점이기에 큐에 넣는다. ->정보에 나오지 않은 학생은 어디에 있어도 순서가 만족한다. 3. 큐가 빌 때 까지 poll 하면서 나온 정점이랑 이어진 간선을 제거한다. 주의사항 1..

서론 DFS는 가장 많이 쓰이는 알고리즘이다. 아마 대부분의 문제들은 DFS와 BFS 알고리즘으로 해결되기 때문에 꼭 알아야 한다. DFS는 Stack 또는 재귀로 구현할 수 있는데 재귀로 구현하는 것이 직관적이고 가독성도 좋다. DFS를 구현하기 전에 문제에서 원하는 조건을 꼭 알아야 한다. 중복이 되는지, 순서대로 하는 건지 등등.. 조건에 따라서 방문했던 곳을 제 할 수 돼있고, 포함시킬 수 도있다. 그러므로 꼭 문제의 조건을 확인해야 한다. 만약 DFS가 구현하기 어렵다면 기본적인 틀을 외우고 문제를 풀어가며 이해한다. 구현 코드 1. 중복 가능 순열(1~2중에 3개 선택 중복가능) public class PermutationNPIN { static int n; //순열의 자리수 static in..

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN&categoryId=AV18KWf6ItECFAZN&categoryType=CODE4 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 1. 반복문을 이용하여 substr을 구하고 우선순위 큐에 넣는다. 2. 큐에서 주어진 index를 빼며 답을 구한다. 주의사항 1. 우선순위 큐에 substr을 담았기 때문에 중복제거는 반복문 1개로 가능하다. 2. 우선순위 큐를 이용하여 정렬할 때 문제에 주어진 조건을 잘 읽어봐야 한다. -> ..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 1. 이중 포문을 돌면서 8방향 지뢰의 개수를 찾는다. 2. 지뢰개수가 0인 좌표를 큐에 넣고 조건을 만족 하는 범위까지 퍼진다. 3. 안 퍼진 곳(0)과 퍼진곳의 시작 좌표(-1)을 count해준다. 주의사항 1. 구현 하는 방식은 다양하다. 알고리즘을 생각할 때 문제를 잘 읽어보고 문제대로 구..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG&categoryId=AWqU0zh6rssDFARG&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Treeset, list 등을 이용하여 푸는 방식은 많지만 우선 순위 큐가 가장 적합하다 생각했다. 알고리즘 1. 입력을 받으면서 우선 순위 큐에 넣는다. 이름은 객체로 받았다. -> ComparTo 함수를 만들어도 된다. 2. 객체 비교를 하는데 먼저 길이를 비교하였고, 길이가 같으면 반복문을 통해 사전 순으..

서론 우선순위 큐는 알고리즘 풀 때 자주 쓰이는 자료구조 중 하나이다. 우선순위 큐의 장점은 offer를 하면 큐 내에서 Sort를 해준다. Sort의 기준은 defalut가 값 하나에 대한 오름차순이다. 그러나 대부분 문제들이 우선순위 큐에 객체로 들어가기 때문에 CompareTo를 Overriding 하여 Sort의 기준을 잡아준다. 구현 코드 ///////////////////////객체 생성 후 CompareTo 재정의/////////////////////// class road implements Comparable{ int y; int x; int value; public road(int y, int x, int value) { super(); this.y = y; this.x = x; thi..