본문 바로가기

algorithm

(135)
프로그래머스_네트워크(C++) programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr [문제 풀이] DFS를 이용하여 문제를 풀었습니다. 이 문제는 컴퓨터를 연결하는 간선의 정보가 입력으로 들어왔을 때 서로 직간접적으로 연결된 그래프의 그룹의 개수 찾는 문제입니다. A와 직접 연결된 정점들과 정점들의 연결된 컴퓨터를 탐색하는 방법으로 문제를 해결했습니다. 문제의 로직은 반복문을 돌면서 방문하지 않은 컴퓨터라면 DFS에 인덱스값을 전달하여 연결된 컴퓨터들을..
프로그래머스_타겟 넘버(C++, JAVA) programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr [문제 풀이] DFS를 이용하여 문제를 풀었습니다. 이 문제는 n개의 정수가 입력으로 들어왔을 때 숫자들을 +, -하여 타겟 넘버를 구하는 문제입니다. +, - 연산을 모든 경우에 대해 구해보는 DFS를 이용하여 문제를 해결했습니다. 문제의 로직은 DFS 함수에 (다음 index 번호, 현재 index의 벡터값을 더하고 뺀..
프로그래머스_입국심사(C++) programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr [문제 풀이] 이분탐색을 이용하여 문제를 풀었습니다. 이 문제는 n명의 사람이 입국 심사를 모두 마치는 데 걸리는 최소시간을 구하는 문제입니다. n과 times의 범위가 크기 때문에 완전 탐색으로는 해결이 어려우므로 이분탐색을 이용하여 해결하였습니다. 문제의 로직은 최소시간과 최대시간(가장 오래 걸리는 입국 심사관 * n)의 값의 중간을 찾아 중간시간 안에 몇 명의 심사관이 심..
백준 1260_DFS와 BFS(C++) www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [문제 풀이] DFS와 BFS를 이용하여 문제를 풀었습니다. 이 문제는 그래프를 구성하는 정점과 간선이 주어질 때 그래프 탐색을 DFS와 BFS로 탐색하는 것을 구현하는 문제입니다. 따라서, DFS와 BFS 함수를 구현하여 주었습니다. DFS 코드 설명 입력으로 주어진 간선을 저장해 둔 map 배열을 N 크기 만큼 돌면서 DFS 함수에 매개변수로 주어진 v 와 연결된 정점을..
백준 9342_염색체(C++) www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net [문제 풀이] 구현을 이용하여 문제를 풀었습니다. 이 문제는 아래의 조건을 만족해야 합니다. 문자열은 {A, B, C, D, E, F} 중 0개 또는 1개로 시작해야 한다. 그 다음에는 A가 하나 또는 그 이상 있어야 한다. 그 다음에는 F가 하나 또는 그 이상 있어야 한다. 그 다음에는 C가 하나 또는 그 이상 있어야 한다. 문자열은 {A, B, C, D, E, F} 중 0개 또는 1개로 끝나야 한다. 따..
백준 1927_최소 힙(C++) www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net [문제 풀이] STL의 우선 순위 큐를 이용하여 문제를 풀어보았습니다. 이 문제는 단순히 STL을 구현하는 것이므로 설명은 생략하겠습니다. priority_queue에 대한 개념은 아래에 링크에 정리되어있습니다. 더보기 steady-life.tistory.com/78 (C++ STL) priority_queue priority_queue< 자료형 T, 구현체 Container, 비교 연산자 Co..
백준 11279_최대 힙(C++) www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net [문제 풀이] STL의 우선 순위 큐를 이용하여 문제를 풀어보았습니다. 이 문제는 단순히 STL을 구현하는 것이므로 설명은 생략하겠습니다. priority_queue에 대한 개념은 아래에 링크에 정리되어있습니다. 더보기 www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를..
(C++ STL) priority_queue priority_queue priority_queue 란? 힙 이론을 통해 우선순위 큐를 구현한 것 입니다. 자료형으로는 변수, 클래스 등 다양한 것들을 넣을 수 있습니다. 구현체는 기본적으로 vector를 사용하지만 deque를 사용하는 것도 가능합니다. 비교 연산자는 기본적으로 greater 오름차순, less 내림차순으로 정의하지만 비교연산자를 지정 해줄 수도 있습니다. queue 헤더 안에 존재합니다. priority_queue 함수 priority_queue.empty() 우선 순위 큐가 비었는지 확인하는 함수입니다. 비어있다면 True, 아니면 False를 반환합니다. priority_queue.size() 우선 순위 큐의..