일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 구현
- 삼성 기출
- 소수
- 맛집
- 브루트포스
- 완전탐색
- dfs
- BOJ
- hackerrank
- koitp
- 해커랭크
- 삼성 SDS 대학생 알고리즘 특강
- 백준
- 시뮬레이션
- 스택
- 그리디
- BFS
- PS
- SWEA
- 백트래킹
- 알고리즘
- dynamic programming
- Algorithm
- C++
- 잠실
- 다이나믹 프로그래밍
- sw expert academy
- 동적 계획법
- 에라토스테네스의 체
- DP
- Today
- Total
목록Study/PS(Algorithm) (93)
펭로그
문제 링크 : https://boj.kr/1012 BOJ 11724 연결요소의 개수랑 매우 유사한 문제로 생각된다.인접한 배추들이 존재한다면 하나로 이어진 배추들에는 지렁이가 한마리씩만 필요하다.결국 연결요소 문제랑 동일하게 연결요소의 갯수를 세면 되는 문제다.visited를 따로 만들지 않고 dfs로 탐색이 가능한 위치면 true로 두었고 방문 불가능한 위치이거나 방문했다면 false로 두었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950// BOJ 1012 유기농 배추#include using namespace std; vector cbg;const int dx[4] = {1, -1..
문제 링크 : https://boj.kr/10451 그림과 같이 순열 사이클을 찾는 방법은 간단하다.그냥 dfs로 돌리면 된다. dfs를 몇번 시작했는지만 체크하면 된다.다음에 방문할 노드를 저장하는 것은 인접 리스트를 만드는 방법과 동일하고 방문했다면 0으로 설정하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243// BOJ 10451 순열 사이클#include using namespace std; vector permu; void dfs(int idx){ int next = permu[idx]; if(next != 0) { permu[idx] = 0; // 방문 표시 dfs(next); }} int main..
문제 링크 : https://boj.kr/11724 문제의 컨셉은 간단하다. 주어진 그래프에서 하나로 이어져 있는 연결 요소의 개수를 찾는 문제로 위 그림에서 하나로 이어져있는 연결 요소 수는 2개가 된다. 입력의 경우는 미리 인접 리스트를 만들어 간선을 입력 받는다. 그 이후 1부터 N까지 DFS를 돌려서 DFS가 끝나는 시점에 카운트를 하나 증가시켜 주면서 다음 시작 요소로 DFS를 돌리는 식으로 반복하면 답을 구할 수 있다. 스택으로 구현한 방법이 함수를 사용하여 재귀로 돌리는 것보다 시간이 덜 걸릴 줄 알았는데 함수로 재귀 돌리는 것이 의미 없는 수치이긴 하지만 더 빨랐다. (위 - 스택, 아래 - 재귀) 스택으로 구현한 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..
문제 링크 : https://boj.kr/2178 지난번에 풀었던 BOJ 7576 토마토 문제보다 훨씬 쉬운 BFS 문제인듯 하다.토마토 문제에서 잡았던 대부분의 기본 개념을 그대로 가지고 풀었다.토마토 보다 이 문제를 더 먼저 풀었으면 좋았을걸.. 먼저 이 문제는 입력 자료형이 공백으로 구분지어져있지 않기 때문에 1. std::istringstream 를 split 하여 입력받기2. char형 그대로 입력 받는 방법3. 스트링 클래스의 getline(std::cin, input); 사용4. scanf("%1d", &input); 처럼 형식지정자로 1자리만 받도록 하기등등 다양한 방법을 활용하여 입력 받아야 한다. 이 외에도 getch나 gets 등등 아주 많다.scanf를 사용하는게 제일 편하긴 하지만..
문제 링크 : https://boj.kr/11399 A B C D 의 순서로 필요한 시간이 있다고 가정해보자1 - A2 - A + B3 - A + B + C4 - A + B + C + D TOTAL - 4*A + 3*B + 2*C + 1*D 로 식이 나오게 된다. 가장 큰 수를 적게 곱하고 작은 수를 많이 곱하는게 이득이 된다. 결국 모든 숫자를 오름차순으로 정렬해줘서 작은 숫자 부터 N - i 번씩 곱해나가는 방식으로 풀면 쉽게 풀린다. 1234567891011121314151617181920212223242526// BOJ 11399 ATM#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);..
문제링크 : https://boj.kr/2309 무식하게 그냥 연산하면 풀리는 브루트 포스 알고리즘 문제이다.우선 모든 값을 sum에 더하고 2개의 원소를 뽑아서 뺀 후 100이 나오면 종료한다.생각할 수 있는 경우의 수가 적어서 단순하게 풀었다. 12345678910111213141516171819202122232425262728293031323334353637383940// BOJ 2309 일곱 난쟁이#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", stdin); vector dwarf; int input, ..
문제 링크 : https://boj.kr/7576 이 문제보다 기본 개념의 문제는 BOJ 2178 미로 탐색을 참고 컨셉을 잡는 데에 상당히 어려울 수 있지만 알고보면 기본적인 BFS 문제인 것 같다.map을 int형 컨테이너로 하나 만들어 입력 정보를 받고 이 정보를 visited로 사용하면 된다.현재 탐색하는 위치 정보는 별도의 구조체를 만들어 여기에 x, y 좌표와 BFS 탐색의 몇번째 단계에 해당하는지 level 변수를 추가하였다.입력 받을 때 익은 토마토를 발견하면 그 즉시 바로 큐에 담는다.큐에 담긴 순서대로 BFS를 수행하면 문제가 쉽게 풀리게 된다.BFS를 다 수행한 이후엔 다시 한번 전수조사를 해서 안익은 토마토를 체크했다. 12345678910111213141516171819202122..
문제링크 : https://boj.kr/10026 현재 위치를 기준으로 상, 하, 좌, 우의 4방향을 DFS로 탐색해서 같은 영역인지 여부를 확인한다.같은 영역이 아닐 경우 빠져나오며 단 한번이라도 같은 영역이 나오면 true를 반환한다.시간 복잡도에는 크게 영향이 없을 것 같으나 편의를 위해서 한번 탐색한 'R'은 'G'로 바꿔주도록 했다.dfs 탐색 도중 중간에서 반환하는 false의 경우는 최초 dfs 실행 후 담을 chk 변수가 아닌 이상 딱히 의미는 없다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263// BOJ 10026 적록색약#..
문제링크 : https://boj.kr/11653 어떤 숫자의 소인수들은 소수들의 곱으로 표현할 수 있다.그러기 위해선 입력 숫자의 범위만큼 소수 리스트를 구해서 해당 소수들이 입력 숫자로 나누어 떨어지는지를 계산하고 이를 무한히 반복하여 더이상 나누어 떨어지지 않을 때까지 나누면 된다. 다만, 소수 리스트를 다 구할 필요는 없고 입력 숫자의 제곱근 범위까지만 구하면 된다.제곱근보다 큰 범위의 숫자를 2개 이상 서로 곱하면 입력 숫자를 초과하기 때문에 더 이상 구할 필요가 없다.소수 리스트에 속하지 않은 남은 숫자는 무조건 소수이다. (해당 숫자가 소수 리스트의 곱으로 표현되는 순간 소수가 아니다.) 소수 판별은 에라토스테네스의 체를 이용하여 구하면 더 빠르게 구할 수 있다. 123456789101112..
// BOJ 1753 최단경로#include #include #include #include using namespace std; struct edge {vector to;vector len;}; int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);freopen("input.txt", "r", stdin); vector edg(20001);priority_queue qq; int D[20001] = { -1, };int num, e, start;cin >> num >> e >> start;D[start] = 0;qq.push(pair(0, start)); int u, v, w;for (int i = 0; i < e; i++)..