본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 5014번 : 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net bfs로 푼 문제였습니다. 비슷한 문제로는 숨바꼭질 문제가 있습니다. 풀이방법 입력받은 후 bfs를 수행합니다. 올라갈 수 있다면 queue에 다음 층을 방문하고 누른 버튼 수를 함께 queue에 pair형태로 push해줍니다. 내려갈 수 있다면 마찬가지고 push해줍니다. *pop이후에 방문하게 된다면 한 줄만에 방문해서 더 깔끔해 보이지만 시간초과가 납니다. x+u와 x-d가 다음 경로에서 엇갈리면서 중복..
(C++) - 백준(BOJ) 1062번 : 가르침 www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 효율적으로 탐색해야하는 문제였습니다. 풀이방법 그냥 있는대로 탐색한다면 조합을 뽑는데 최대 26C13이 나오므로 1천만의 시간복잡도 가집니다. 따라서 뽑은 후 50 * 15를 하면서 최대 단어의 개수를 구하므로 50 * 15 * 1천만 = 7억 5천정도의 시간복잡도로 시간초과에 걸립니다. 따라서 효율적인 탐색방법을 고안해야합니다. 먼저 모든 단어는 "anta"로 시작되고, "tica"로 끝납니다. 이 말..
(C++) - 백준(BOJ) 17142번 : 연구소 3 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 여러가지 알고리즘을 사용하는 문제였습니다. 풀이방법 1. 입력을 받습니다. vector pair 형태로 2인 부분의 행,열 좌표를 virusPos 변수에 저장해줍니다. 그 외 필요한 변수들을 선언해줍니다. 2. 바이러스를 m개 놓아야합니다. backtracking을 이용해 조합으로 뽑아줍니다. 그 좌표들을 spreadPos변수에 저장합니다. 3. bfs를 수행합니다. 그 후 가장 큰 값이 마지막으로 퍼졌을 때의 시간입니..
(MYSQL) - 프로그래머스(2021 Dev-Matching: 웹 백엔드 개발자) : 헤비 유저가 소유한 장소 programmers.co.kr/learn/courses/30/lessons/77487 코딩테스트 연습 - 헤비 유저가 소유한 장소 PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 programmers.co.kr nested query를 사용하는 문제였습니다. 풀이방법 HOST_ID의 row 개수가 1초과인 열들을 뽑은 후 모든 열에서 HOST_ID와 매칭되는 열을 출력했습니다. Code SELECT ID, NAME, HOST_ID FROM PLACES WHERE HOST_ID IN ( SELECT HOST_ID FROM PLACES G..
(C++) - 백준(BOJ) 1865번 : 웜홀 www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 벨만포드 문제였습니다. 풀이방법 모든 정점을 확인하면서 갱신이 되었다면 flag를 세워주고 갱신이 되지 않았다면 다시 돌아올 수 없는 경우므로 flag를 내려주는 방식으로 벨만포드 알고리즘으로 순회하며 정답을 찾습니다. Code #include #define INF 0x3f3f3f3f using namespace std; using pii = pair; int tc; int n, m, w; vect..
(C++) - 백준(BOJ) 1504번 : 특정한 최단 경로 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 시작정점을 a, 거쳐야할 두 정점을 각각 v1,v2 도착정점을 b라고 가정했을때 가는 최단경로가 있다면 다음과 같이 두 가지 경로가 있습니다. 1) a -> v1 -> v2 -> b 2) a -> v2 -> v1 -> b 1), 2)중 최소인 경로를 출력, 경로가 없다면 -1을 출력해주면 됩니다. 1. 1)의 답은 a -> v1으로 ..
(C++) - 백준(BOJ) 1238번 : 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 i번 친구가 x마을로 가는데 걸리는 최소 시간과 x마을에서 i가 출발해 i마을에 도착하는데 걸리는 최소 시간의 합이 오고 가는데 거리는 총 소요시간이므로 다익스트라로 해당 값을 구해 최댓값을 출력해주면 됩니다. Code #include #define INF 0x3f3f3f3f using namespace std; using pii = pair; i..
(C++) - 백준(BOJ) 2096번 : 내려가기 www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net dp문제였습니다. 풀이방법 메모리 제한이 4mb이므로 400만 byte크기 이하의 변수들을 선언해 사용해야 합니다. 이 문제는 10만개의 배열 이상 사용하지 않아도 되는 문제입니다. 1. 첫 번쨰 행의 세 수를 먼저 입력 받습니다. 그 후 d, d2배열에 각각 저장합니다. 2. 현재 열이 0번째 열이면 이전의 행에서는 0,1번째 열 중 최대값에서 현재 열의 값을 더한값이 현재 열이 가질 수 있는 최댓값입니다. 현재 열이 1번..

티스토리툴바