PS
BOJ 1913 - 달팽이
www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 이차원 배열을 활용하여 구현하는 문제이다. 프로그래머스 월간 챌린지에서도 이런 비슷한게 나와서 연습겸 풀어보았다 - c++ #include #define MAX 1000 using namespace std; int N, pos; long adj[MAX][MAX]; void print_adj() { for (int i = 0; i
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 다익스트라를 이용해서 푸는 문제로 특정한 조건의 노드를 반드시 거쳐야만 하는 그런 문제 였다. 오랜시간동안 고민하다 도저히 모르겠어서 다른 사람들의 코드들을 보니 다익스트라를 여러번 돌리는 것이 핵심이었다. (PS 잘하는 사람들은 볼때 마다 놀랍다 이런 생각들은 도대체 어떻게 하는 것인지) 기본 다익스트라는 "하나의 시작점에서 다른 노드들에 대한 최단 경로를 찾자"..
BOJ 11585 - 속타는 저녁 메뉴
www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net KMP 를 써서 풀어야 하는 문제이다 원형 룰렛을 구현하는 대신, 문자열을 두배로 늘리고 이에 패턴 문자열을 맞춰서 KMP 를 써야 한다. - c++ #include #include #include #include using namespace std; int N; string parent, pattern; char ch; int cnt; vector make_pi() { int pattern_size = p..
BOJ 7569 - 토마토
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 7569 번 문제는, 아래의 7576 번 토마토 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 와 다..
BOJ 2630 - 색종이 만들기
www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할정복법(Divide and Conquer) 을 사용해 푸는 문제 (참조 : kimch3617.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5%EB%B2%95-Divide-and-Conquer) - c++ #include #define MAX 128 using name..
BOJ 11724 - 연결 요소의 갯수
www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net DFS 를 이용해서 풀어야 하는 문제이다 연결 요소(Connected Component) 에 대한 위키백과의 정의를 보면 이렇게 서술하고 있다. "In graph theory, a component, sometimes called a connected component, of an undirected graph is a subgraph in wh..
BOJ 1931 - 회의실 배정
https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net Greedy 를 이용해 푸는 문제이다. 회의의 시작시간을 기준으로 정렬을 하고, 회의의 끝 시간을 기준으로 정렬을 한다 -> 이렇게 정렬을 두번 하는 이유는 (4,5) , (3,5) , (1,5) 같이 끝나는 시간만 동일한 케이스가 있을 경우 현재 상황에서 가장 최선의 선택을 하는 Greedy 의 원칙과 부합하지 않을 수 있기 때문이다 가장 먼저 시작하는 1초 부터 잡아야 Greedy 의 원칙과 맞기 때문에 (1,5) , (3,5) , (4,5) 로 정렬되어야 한다. 또한 회의가 끝나는 시간 보다 크거나 같은 경우..
BOJ 11399 - ATM
https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net Greedy 알고리즘을 이용해서 푸는 문제이다. 이 문제를 풀면서 내가 겪었던 가장 큰 문제는 DP 와 Greedy 의 개념을 명확하게 이해하지 못하고 있다는 점이었다. DP 는 가능한 모든 경우의 수를 다 따지되 메모이제이션 기법을 써서 연산의 횟수를 줄이는 것이고, Greedy 는 그냥 지금 현재 상황에서 가장 최적의 선택지만 고르면 되는것이다. 이에 대한 명확한 이해도가 없다보니 이 문제를 풀 때 모든 경우의 수를 어떻게..