알고리즘

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 날짜 최대 개수는 1000000이고, 매매가는 최대 10000이다. 그러면 최대 1000000*10000 정도의 결과가 나..

https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 문제풀기 전 생각 물건을 쪼개서 넣을 수 있다면 그리디 문제이지만, 사람을 쪼갤 수 없으니 완전탐색이다 최대 가치의 물건을 넣는 배낭문제로 생각할 수 있고 완전탐색 백트래킹 방법으로 생각할 수 있다 배낭문제로 생각하면 배낭의 크기가 체력의 크기(100)이므로, 크지 않은 숫자라서 배낭문제로 풀기 적합하다 세준이의 체력은 최소 1까지만 줄어들 수 있고, 0이나 음수가 되면 안되는거 고려 백트래킹으..

완전 탐색해야하는 문제! 백트래킹을 사용한다 dfs방식으로 해를 찾고, visit 배열을 되돌리는 방법을 사용 시간복잡도 문제로 꼭 가지치기를 해줘야한다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; //[baekjoon] java-1058 public class Main { private static int min = 3001; //(5*3*200) private static int size; private static int[][] arr; private static boolean[][] visit; public stati..

모든 쌍 최단 경로 문제를 푸는 알고리즘 모든 쌍 최단 경로 문제 각 쌍의 점 사이의 최단 경로를 찾는 문제 풀이방법 다익스트라 알고리즘 O(n³) 플로이드 워샬 알고리즘 O(n³) 플로이드 워샬 알고리즘(Floyd-Warshall) 동적계획법 알고리즘 매우 간단하여 다익스트라 알고리즘보다 효율적 음의 간선이 존재해도 모든 최단 경로를 구할 수 있음 (다익스트라는 안됨) 귀납법으로 증명이 가능하다 간단한 원리 어떤 점을 경유하는 거리와 다이렉트 경로 중 작은값을 선택하여 갱신함 D[2,3] 이라는 2부터 3의 거리가 있다면 1을 경유하는 거리 D[2, 1] + D[1,3] 원래거리 D[2,3] D[2,3] = min( D[2,3], D[2,1] + D[1,3] ) 1을 경유하는 거리 비교 후 갱신, 2를..

https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net bfs를 사용한 풀이(내 풀이) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; //[baekjoon] java-1058 public cla..

https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 내 풀이 설명 나올 수 있는 가장 짧은 경우는 짝수길이일 때: 짝수길이 팰린드롬으로 만들어지는 경우 (ex. baab) 홀수길이일 때: 홀수길이 팰린드롬으로 만들어지는 경우 (ex. bbabb) 문자열 길이가 L이라면 L/2 - 1 인덱스부터 짝수길이 팰린드롬/ 홀수길이 팰린드롬을 만들어보고 인덱스를 하나씩 늘려가면서 비교한다 L/2 - 1 인덱스가 가장 짧은 경우이고 인덱스가 하나씩 늘어날수록 팰린드..

브론즈 문제는 너무 쉬워서 바로 실버를 푸는 것도 괜찮을 것 같은 브루트포스 문제! 실버문제들을 풀어보려고 한당 1476 날짜제작 실버5 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer..

브루트포스로 문제를 풀어야만 하는 경우에 다른 방법을 시도하다 시간을 낭비한 적이 많다. 아직 브루트포스 방식에 익숙하지 않기 때문이라고 생각한다. 그래서 해당 풀이법과 관련있는 문제들을 많이 풀어보려고 한다.! 브루트 포스(bruteforcing) brute: 짐승 같은, 난폭한 brute-force: (정제되지 않은) 난폭한 힘, 폭력 이론적으로 가능한 모든 경우의 수를 찾아보는 방법 시간과 자원이 많이 드는 무식한 방법 가장 확실하면서 정확도 100%를 보장함 1837 암호제작 브론즈3 https://www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 생각 듣도 못한 사람 - A그룹 / 보도 못한 사람 - B그룹 듣도 보도 못한 사람 - A U B (합집합) A그룹을 해시에 저장하고 B그룹 사람 이름의 key값이 존재하는지 확인, 존재하면 count ++ 시간복잡도? 정렬된 값으로 저장하는 것보다 해시가 가장 빠르다고 생각함. 실험을 통해 알아보자! 1. 배열 HashMap을 사용하지 않으면 시간초과남 2. HashMap 사용하기 import..

https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net bfs를 쓰면 시간이 너무 오래걸릴 것 같아 수식으로 해결해봤다. 규칙을 찾는 데 시간이 좀 걸렸지만, 수식을 사용하기 때문에 수행시간이 빠르다. 1. 갈 수 없는 곳 판별하기 이렇게 표로 슥슥 그려보면 갈 수 없는 지점이 보인다 행(row)은 시작지점의 2의 배수만큼 떨어져 있어야하고 열(col)은 시작지점과 (2 x..