막내의 막무가내 프로그래밍 & 일상

https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백준 백트래킹 문제 시리즈로 유명한 N과 M 시리즈의 11번째 문제를 풀어봤습니다. 같은 수를 여러번 고를 수 있는 순열조합이므로 중복 선택을 체크할 boolean[] isVisited 는 사용하지않았습니다. 풀이는 다음과 같습니다. [Java] import java.util.Arrays; import java.util.Scanner; public class Main { private stat..

프로그래머스 LV2 문제를 풀어봤습니다. ㅎㅎ (휴일아침에 알골이라니...할게많다. 이모티콘 기능은 언제생겼찌) 문자열을 조작하는 단순 구현문제였습니다. 요즘 특정 알고리즘 말고 이런 문자열 조작과 시키는대로 단순 구현하는 문제들도 많이 나오는 추세라 중요하다고 생각합니다. 풀이는 주석으로 대신합니다. [Java] class Solution { public int[] solution(String x) { int[] answer = new int[2]; int removeCnt = 0; // 제거된 0의 모든 개수 int convertCnt = 0; //변환 횟수 while (!x.equals("1") && !x.equals("")) { //빈문자열이거나 1이 될때까지 반복 // 1. x의 모든 0을 제거..

https://programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 오랜만에 프로그래머스 알고리즘 LV2 간단한 문제를 풀어봤습니다. ㅎㅎ 처음에 재귀로 풀었으나 시간초과가 나서 DP식으로 풀었습니다. 학창시절 프로그래밍언어개론 과목 첫 과제중 하나가 이거..

www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 백준에서 그리디 유형의 전자레인지 문제를 풀어봤습니다. ㅎㅎ 3가지의 시간초 버튼을 가진 전자레인지로 정해진 시간초(T)를 최소한의 버튼 누르는 횟수로 정확하게 요리할 수 있는지 구하는 문제였습니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanne..

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 백준 DP 유형의 문제를 풀어봤습니다. DP 유형은 이번년도에는 처음 푼 것 같네요.. 역시 생각하는거나 규칙성을 찾는게 어려운 것 같습니다. ㅠ_ㅠ 1,2,3 으로 해당 숫자를 만들 수 있는 경우의 수를 찾는 문제 입니다. 1,2,3 의 덧셈으로 이루어진 경우의 수 이므로 1 일때 경우의 수 (1) - 1가지 2 일때 경우의 수 (1+1, 2) - 2가지 3 일때 경우의 수 (1+1+1, 1+2, 3) - 4가지 4 일때 경우의 수 (1+1의 총케이스, 2+2의 총케이스, 3+3의 총케이스) - 7가지 로 ..

www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 백준 백트래킹 유형의 2529번 부등호 문제를 풀어봤습니다. 부등호가 주어지면 해당 부등호를 만족하는 숫자들 중 최댓값과 최솟값을 출력하면 되는 문제였습니다. DFS 백트래킹을 사용하여 완전탐색 해주면 해결이 됩니다. 풀이는 주석으로 적어놨고 다음과 같습니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.Li..

www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 백준 정렬 단계별풀기 마지막 문제인 좌표 압축문제를 풀어봤습니다. ㅎㅎ 분명 정렬 마지막문제를 풀었던 것 같은데 새로 생긴건지 잘 모르겠네요 흠.. 숫자들이 있으면 그것을 정렬했을때의 자신의 좌표값으로 압축하면 되는 문제였습니다. 같은 숫자인 경우는 가장 앞에 있는 좌표값으로 통일시킵니다. 풀이는 다음과 같습니다. [Java] import java.util.Ar..

programmers.co.kr/learn/courses/30/lessons/49191?language=kotlin 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 프로그래머스 LV 3 문제 순위를 풀어보았습니다. ㅎㅎ 권투 선수간 누가 누굴 이겼는지 알 수 있는 배열이 주어지는데 이걸 토대로 몇명의 권투 선수 순위를 확정지을 수 있는지 구하는 문제였습니다. 이전에 백준에서 풀었던 저울이라는 문제와 비슷했고 똑같이 N:N의 관계를 파악하기 위해 플로이드 워셜 알고리즘을 사용해서 풀었습니다. youngest-programming.tistory.com/535?category=1013047 [알고리즘] 백준 10159 저..

www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 백준 다익스트라 유형의 10282번 해킹 문제를 풀어봤습니다. ㅎㅎ 다익스트라의 기본 유형 문제였습니다. 풀이는 다음과 같습니다. [Java] import java.util.*; public class Main { private static int T; //테스트 케이스 수 private static int N; //컴퓨터 개수 private static int D; //의존성 개수 private static in..

www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 백준 백트래킹 유형에서 외판원 순회2 라는 문제를 풀어봤습니다. ㅎㅎ N개의 도시를 특정 시작 도시에서 출발하여 다시 첫 도시로 순회하는 최단 경로를 구하는 문제입니다. 방문한 도시는 다시 못가고요. 백트래킹을 사용하면 되고 매개변수로 깊이, 시작도시, 이전방문도시, 총 경로비용, 방문 여부를 사용해주면 됩니다. 풀이는 다음과 같습니다. [Java] import ja..

programmers.co.kr/learn/courses/30/lessons/1844?language=java 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 오랜만에 프로그래머스 문제를 풀어봤습니다. ㅎㅎ 단순한 BFS 문제입니다. 그러므로 풀이생략 !! [Java] import java.util.LinkedList; import java.util.Queue; class Solution { private static boolean[][] isVisite..

www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 최소신장트리 유형 문제를 풀어봤습니다. ㅎㅎ 오타하나떄문에 시간을 많이 날렸습니다. ㅠㅠ ;; 문제를 간단히 설명하면, 발전소에서 전기가 나오고 도시들이 모두 전기를 저렴하게 연결하는 비용을 구하면 됩니다. 크루스칼 알고리즘을 사용하여 풀면됩니다. 기본적인 최소신장트리 문제와 다른게 있다면, 모든 도시들을 그냥 싼 비용으로 연결하는게 아니라 여러개의 발전소가 있고 발전..

www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 백준 다익스트라 유형에서 한 문제를 골라 풀어봤는데 BFS에 가까운 문제였습니다. ㅎㅎ 문제에 대해 간략히 설명하면, 검은색방은 지나갈 수 없고 흰색방은 지나갈 수 있는데, (0,0)에서 (N,N) 까지 가는데 최소한의 검은색-> 흰색 방으로 변경해야 하는 개수를 구하는 문제였습니다. 해당 지점까지 오는데 색을 바꾼 값을 담는 배열인 distances - distances는 가장 큰 값(INF)로 초기화를 해줍니다. ..

www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 백준 다익스트라 유형의 특정 거리의 도시 찾기 문제를 풀어봤습니다. ㅎㅎ 특정 경로에서의 최단경로 즉 1:N의 최단 경로를 구하면 되는 문제이므로 다익스트라 알고리즘을 사용하면 됩니다. (정점 개수가 V, 간선 개수가 E일 때 시간복잡도는 O(ElogV)입니다.) 풀이는 다음과 같습니다. [Java] import java.util.Arra..

www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 백준 플로이드 워셜 알고리즘 유형인 운동 문제를 풀어봤습니다. ㅎㅎ 마을과 연결된(단방향) 도로가 있는데 모든 마을을 최소거리(비용)로 도는 비용을 출력해야합니다. (사이클이 존재하지않는다면 -1 출력) 플로이드 유형을 골라푼만큼 플로이드를 사용해서 모든 정점 사이의 최단경로를 구해서 풀이했습니다. 또한 이전문제들과 다르게 자기 자신에 대한 경로를 0이 아닌 INF로 세팅하여 ..