본문 바로가기

알고리즘 Algorithm

알고리즘 Algorithm/BOJ 백준 (초급~중급) 2022. 12. 29. 백준 알고리즘 100문제 구분 문제 이름 문제 링크 풀이 알고리즘 기초 고스택 https://www.acmicpc.net/problem/3425 C++, Java https://subbak2.tistory.com/3 탈출 https://www.acmicpc.net/problem/3055 C++ https://subbak2.tistory.com/129 JAVA https://subbak2.tistory.com/4 가르침 https://www.acmicpc.net/problem/1062 C++ https://subbak2.tistory.com/130 JAVA https://subbak2.tistory.com/5 후보 추천하기 https://www.acmicpc.net/problem/1713 C++ https://subbak2.tis..
알고리즘 Algorithm/LeetCode 2022. 7. 2. LeetCode 1. Two Sum (Java) * 문제 URL : https://leetcode.com/problems/two-sum/ * 영상 풀이 : https://youtu.be/jbOgIznkuwk * 풀이 순서 1) N^2으로 완전탐색 2) HashMap에 전부 넣고 탐색 3) HashMap에 넣으면서 탐색 * 배경지식 : HashMap은 형태로 데이터를 저장하는 자료구조이다. Hash 알고리즘을 통해 데이터의 삽입, 검색에 시간복잡도 O(1)을 가지기 때문에 반복해서 데이터를 insert, select 할때 유리한 자료구조이다. * 코드 : https://github.com/subbak2/SubCoding/blob/master/Algorithm/LeetCode_No1_TwoSum.java class Solution { public int[..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 두 번째로 작은 스패닝 트리(1626) Java 링크 : https://www.acmicpc.net/problem/1626 문제 설명 : 더보기 방향성이 없는 그래프 G가 주어진다. 문제는 G의 최소 스패닝 트리보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다. MST와 second MST의 모습 입력 : 더보기 첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,000보다 작거나 같은 자연수 또는 0이고, 답은 231-1을 넘지 않는다. 정점 번호는 1보다 크거나 같고, V보다 작거나 같은 자연수이다. 출력 ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 공장 (7578) Java 링크 : https://www.acmicpc.net/problem/7578 문제 설명 : 더보기 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다 또한, 각 기계에는 식별번호가 붙어있으며, 짝이 맺어진 기계끼리는 같은 식별번호가 붙어있다. 즉, 각 열에 있는 N개의 기계끼리는 서로 다른 식별번호를 가지고 있으며, 반대쪽 열에 있는 같은 식별번호를 가진 기계와 케이블로 이어져 있다. 공장 작업의 효율..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 경찰차 (2618) Java 링크 : https://www.acmicpc.net/problem/2618 문제 설명 : 더보기 어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다. 이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 케이크 자르기2 (10714) Java 링크 : https://www.acmicpc.net/problem/10714 문제 설명 : 더보기 JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 명이 케이크를 나누어 먹기로 했다. 케이크는 둥그런 모양을 하고 있다. 어느 점에서부터 직선으로 칼집을 넣어 케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N 까지 반시계방향으로 번호를 매긴다. 즉, 1 ≦ i ≦ N에 대해, i 번째 조각은 i - 1 번째와 i + 1 번째 조각과 인접해있다. (단, 0번째는 N 번째, N + 1 번째는 1번째로 간주한다). i 번째 조각의 크기는 Ai ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 발전소 (1102) Java 링크 : https://www.acmicpc.net/problem/1102 문제 설명 : 더보기 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다. 적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 : 더보기 첫째 줄에 발전소의 개수 N이 ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 30. [BOJ 백준] 외판원 순회 (2098) Java, C 링크 : https://www.acmicpc.net/problem/2098 문제 설명 : 더보기 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이..

티스토리툴바