알고리즘

[JAVA/자바 백준 17472] 다리 만들기2

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 bfs , prim 알고리즘을 사용했습니다. 1. bfs를 사용해서 섬들을 구분 지어줬습니다. 섬 2번부터 시작해서 2,3,4,5 2. 다리를 지을 수 있는 상황이면 모두 지어주고 거리에 따라 오름차순으로 정렬되게 edgeList에 넣어줬습니다. 3. prim 알고리즘을 사용하여 최소 스패닝 트리를 만들었습니다. 반례) 1. ㄷ자형 섬에 대하여 처리를 해줬습니다. 2. ..

[JAVA/자바 백준 14502] 연구소

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 dfs, bfs 문제입니다. 저는 우선 bfs로 풀었습니다. 1. make_wall 함수를 만들어서 3개의 벽을 만들어주는 기능(combination)을 구현하구, 2. 조건을 만족하면 bfs 탐색을 했습니다. --막힌 점 조합을 써야하는건 알았지만 2차원 배열에서 구현하는데 조금 시간어 걸렸습니다. import java.io.*; import java.util.*; // bfs문제 // 벽을 만들 수 ..

[JAVA/자바 SWEA 3124] 최소 스패닝 트리

풀이 * Kruskal 알고리즘 - 인접 리스트 사용 import java.io.*; import java.util.*; //Kruskal // 정점과 간선이 크므로 edgelist로 풀어아야함 // 가중치 값이 1,000,000이 누적되면 int 범위 넘으므로, result를 long 타입 public class Solution{ static int[] parents; static int V,E; static Edge[] edgeList; static class Edge implements Comparable{ int start,end,weight; public Edge(int start, int end, int weight) { super(); this.start = start; this.end = ..

[JAVA/자바 백준 1149] RGB거리

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 1. 2차원 배열 Cost에 우선 해당하는 rgb에 비용 값을 모두 넣어줍니당. 2. Cost[i][0](red) 일 경우 Cost[i][1](green) Cost[i][2](blue) 중 최솟값을 더해줍니다. 0(Red) 1(Green) 2(Blue) Cost[0][0] Cost[0][1] Cost[0][2] Cost[1][0] += Min(Cost[0][1],Cost..

[JAVA/자바 10026 백준] 적록색약

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 일반적인 bfs 문제 bfs 함수 부분을 한번만 쓰려고 적록색약 아닐때 version=true, 적록색약 일때 version=false로 나눠주고 적록색약인 경우 R과 G를 같은걸로 보니까 R일경우 G를 봐도 큐에 넣어주고 G일경우 R을 봐도 큐에 넣어주고, check 값을 true로 바꿔줬습니다. import java.io.*; import java.util.*; class xy{ ..

[알고리즘 개념] 순열 조합 부분집합(순조부~)

자바로 알고리즘을 풀면서 순조부에 대해서 깊게 공부해야했습니다... (파이썬은 api가 있지만 자바는 없기 때문에) 순조부를 공부하면서 자신이 없던 재귀도 공부하구,,, 의외로 문제 풀때 개념이 많이 쓰이더군용.. 그런 문제만 풀어서 그른가 아무튼 핵심 개념에 대해서 글을 써보겠습니다. 순열(Permutation) 서로 다른 n개 원소 중 r개를 뽑아서 한 줄로 나열하는 것. nPr 쉽게 예제를 통해 말하면 3명 중에서 회장 1명, 부회장 1명을 뽑는다면 (a,b) (a,c) (b,a) (b,c) (c,a) (c,b) 이런 식으로 뽑을 수 있는데 중요한 포인트는 a,b != b,a 입니다. (조합과 다른 큰 특징) 예시 코드 private static void permutation(int cnt) { /..

[Java SWEA 1247] 최적 경로

풀이 순열을 이용해서 풀었습니다. 문제에서도 전부다 순회하면 풀수있다고해서, 완전탐색 써야겠다구 생각했습니다. 순열을 사용해서 numbers배열에 customer_arr 인덱스 값을 넣었습니다. sum()내에서는 현재의 x,y값을 계속 바꿔가면서 거리계산을 했습니다. package a0819; import java.io.*; import java.util.*; class customer{ int x; int y; public customer(int x, int y) { this.x = x; this.y = y; } } public class Main { static int home_x,home_y,current_x,current_y,company_x,company_y, n; //customer 좌표 위치..

[JAVA/자바 1992 백준] 쿼드트리

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 find 부분이 중요합니다. 다른분들은 파라미터 3개로 쓴 사람도 있는데, 풀다가 헷갈려서 5개로 나눠서 썼습니다. 분할정복 문제이므로, label을 처음 사용해서 해결 가능한 문제인지 판단하고, 할수없으면 break 한뒤 1,2,3,4분면으로 나눠서 재귀적으로 돌립니다. 가능하다면 flag 불린값을 바꿔주고, stat~end까지 출력해줍니다. import java.awt.Lab..

[JAVA SWEA 1210 ] Ladder1

풀이 arr에 값을 모두 넣어주고 find에 도착점인 x,y, arr를 넘겨주었습니다. find내에서 방향 dir을 정해주고, dir이 좌 방향일때와 우방향일땐 상 방향 먼저 탐색하고 자기 자신 방향을 탐색하게끔, 상 방향일땐 자기 자신 방향 먼저 탐색하게끔 했습니다. import java.io.FileInputStream; import java.io.*; import java.lang.*; import java.util.StringTokenizer; public class Solution { // 좌 상 우 static int[] dx ={0,-1,0}; static int[] dy= {-1,0,1}; //출발점 찾기! static void find(int x, int y, int[][] arr) { ..

[Python/파이썬 프로그래머스] 다트게임(카카오)

https://programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 풀이 보고 한 15분정도는 고민한 문제 처음 접근은 문자열로 편하게 먼저 구현하려다가 그냥 리스트형식으로 바꿨습니다... 10점일때를 어떻게 고려할까 생각하다가 문자열로 특수한 경우(s,d,t,*,#) 인 경우를 먼저 걸러준 뒤 tmp 값으로 숫자를 받고 s,d,t인 경우 해당 값의 제곱등... 넣어저고 * 일 경우 인덱스 값 고려하구, # 일 경우 -1 곱... def solution(dartResult): tmp='' lst_idx=-1 lst=[] dartResult=list(dartResult) for i in range(le..