본문 바로가기

알고리즘

 (117)
[프로그래머스] 2021 dev-matching - 행렬 테두리 회전하기 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 머리가 안돌아가서 혼났다. 인덱스를 잘 생각해서 회전시키는 문제다 class Solution { public static void show(int arr[][]){ System.out.println(); for(int i=0;i
[프로그래머스] 2021 dev-matching 로또의 최고 순위와 최저 순위 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 카운트 배열을 사용했다 public int[] solution(int[] lottos, int[] win_nums) { int[] answer = new int[2]; int []cnt = new int[46]; for(int i=0;i=2){ answer[1] = 7-minAns; }else{ answer[1] = ..
[백준] 2098 외판원 순회 문제링크 : www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 어떤 위치에서 출발해서 모든 여행지를 방문하고 마지막엔 다시 원래 위치로 돌아오는 방법 중 가장 짧은 거리를 구하는 문제이다. 처음에 문제를 잘못 알아서 모두 방문 후에 원래 위치로 돌아올 때는 여행지를 방문하면서 와도 되는 줄 알았다. 그래서 플로이드 워셜로 여행지 간 최소거리를 저장해두고 dfs의 마지막에는 start로 돌아오는 최소 거리를 더해주었었다. 하..
[백준] 1562 계단 수 [JAVA] 문제링크 : www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 첫 자리 숫자의 경우 1~9까지 오게, 아닐 경우에는 1. 현재숫자가 0이면 다음은 1, 9이면 8 2. 현재 숫자가 0이나 9가 아니면 위 아래 숫자로 다음 숫자를 정했다. 이런 경우를 중복 없이 모두 확인한다. 재귀 탐색 중, 현재 상태가 0~9까지 모두 등장한 계단수인지 판단하기 위해 그 상태를 비트마스크로 확인했다. (10개가 등장했거나 안했거나(0 or 1)로 가능하기 때문에 10자리 이진수로 표현 가능 => 2^10 크기 배열 선언) 어떤 숫자가 등장했는지와 더불어 (몇 번째 수인지, 이전에 무슨 수를 골랐는지..
[백준] 13398 연속합 2 [JAVA] 문제링크 : www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static int N,ans; public static int arr[]; public static int dp[][]; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedRea..
[프로그래머스] kakao 2021년 블라인드 (광고삽입) [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 카카오 블라인드 문제를 오랜만에 풀어보았다. 어느 시간에 공익광고를 넣는 것이 많은사람들이 보겠는가 하는 단순한 문제이다. 문자열로 주어지는 시간을 초 단위로 바꾸어서 배열에 저장하고 풀었다. => 100:00:00은 36만초이다. => 배열 크기 36만 광고를 넣을 수 있는 시간이 adv_p..
[백준] 11657 타임머신 [JAVA] 문제링크 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 최단거리 알고리즘은 보통 다익스트라나 플로이드워셜만 풀어왔다. 이 문제는 벨만포드 알고리즘으로 풀린다. 벨만포드 알고리즘은 음수 가중치가 있는 경우의 문제의 경우를 풀 수 있는 것으로 사이클의 존재 또한 알 수 있다. import java.io.*; import java.util.*; public class Main { public sta..
[백준] 2629 양팔저울 [JAVA] 문제링크 : www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 무게는 500g 이하이고 개수는 30개 이하이므로 추를 가지고 셀 수 있는 무개의 최대 g은 15000이다. 확인하려는 무게는 40000g 이하이므로 15000g 초과에 대해서는 N일 것이다. 구슬이 항상 왼쪽에 있다고 가정할 때 추를 올리는 방법은 왼쪽에 올리거나 오른쪽에 올리거나 올리지 않는 것이다. bottom-up 방식으로 풀었으며 어떤 무게 x가 가능할 때 i번째 추를 가지고 무게를 잴..

티스토리툴바