본문 바로가기

Algorithm🐰/백준61

[백준] 1753 최단 경로 dijkstra 문제 : www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 분석 : 대표적인 다익스트라 알고리즘 문제이다. 다익스트라의 방향 그래프를 구현하기 위해서 배열 또는 우선순위 큐 자료구조를 사용한다. 배열로 사용 할 시 시작 노드와 끝나는 노드의 가중치를 넣기 위해 int v[in][to] = w 와 같이 사용해야 하는데 문제의 배열의 범위가 20000이라 시간 초과가 나 사용이 불가능 했다. 이는 모든 노드들에 대해 for문을 돌면서 또.. 2021. 3. 10.

[백준] 12865 평범한 배낭 knapsack 알고리즘 문제 : www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 분석 : 이 문제는 knapsack 알고리즘의 대표적인 문제이다. 🍙 knapsack 알고리즘 무게와 가치가 따로 있고 최대 가치를 구하는 문제 greedy론 최대 가치를 보장 할 수 없기 때문에 DP로 접근해야 한다. D[i][j] - j 만큼의 무게를 가진 i번째까지 물건들의 가치 V[i] - i 번째 물건의 가치 W[i] - i번째.. 2021. 3. 9.

[백준] 11000 강의실 배정 priority-queue, greedy 문제 : www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 분석 : 이 문제는 언뜻 보면 19598번 최소 회의실 개수 문제와 비슷해 보인다. 하지만 N의 범위가 200,000d으로 O(N^2)으로 풀면 시간 초과가 발생한다 😢 그래서 자동으로 강의 끝나는 시간이 짧은 친구 순으로 검색할 수 있게끔 우선순위 큐를 이용하였다. (처음 써본다 .. 하하) 우선 순위큐는 자료형 T, Container, 사용자 정의 비교 연산(struct, class - operator 연산자) 이 3가지를 정의해 줘야 하고 pq.. 2021. 3. 7.

[백준] 10974 모든 순열 백트래킹 문제 : www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 분석 : 사실 전혀 이해가 되지 않아서 블로그들을 참고하여 풀었다. dfs가 백트래킹이랑 관련이 깊다 했는데 이 문제가 바로 백트래킹 알고리즘 사용하는 고전적인 문제라고 한다. c++ 에선 next_permutation이라는 순열 찾는 함수가 에 있다고 한다. 이걸 이용하면 쉽게 풀 수 있을 것 같다. 하지만 백트랙킹 연습을 위해 백트랙킹 방식으로 완전 탐색 문제를 풀어보았다. dfs와 마찬가지로 visit (방문했는지 안했는지 검사하는 배열)이 필요로 된다. v vector에 넣어주는데 방.. 2021. 2. 27.

[백준] 2617 구슬 찾기 DFS 문제 : www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 분석 : 이 문제는 배열을 두개로 나눠서 쓸 생각을 못해서 배열을 어떻게 담아야 하는지 타입에 관해 고민이 많았다. 심지어 내가 잘 못쓰는 재귀함수까지 사용해서 감 잡기가 어려웠다 😅 문제에서 원하는 것은 무게가 중간이 될 수 없는 구슬의 수를 찾으라고 한다. 중간이 될 수 없으려면 각각 담은 light, heavy vector에 인접한 노드들이 많이 담겨 비교가 많이 되어야 한다. .. 2021. 2. 26.

[백준] 2003 수들의 합2 투 포인터 문제 : www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 분석 : 투 포인터란 1차원 배열에 대해 포인터를 양 끝단에 두고 값을 찾는 방식을 말한다. 조건(m)에 해당 되는 값을 찾으면 cnt를 증가 m 보다 작은 값이면 end 인덱스 위치의 값을 sum에 저장하고 end 하나 증가 m 보다 큰 값이면 start 인덱스의 값을 빼고 start를 하나 증가시킴 c++ 코드 : // // 2003_sum2.cpp // S.. 2021. 2. 26.

[백준] 2667 단지 번호 붙이기 BFS 문제 : www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 분석 : 이 문제는 BFS로 풀었다.(DFS로 풀어도 노상관) 전형적인 BFS 문제이지만 끊어진 방문 위치가 있기 때문에 종만북에서 보았던 것처럼 BFS_ALL을 해주어야 한다. c++ 코드 : // // 2667_complex.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/02/14. // #include #include #include #include #i.. 2021. 2. 19.

[백준] 18870 좌표 압축 문제 : www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 분석 : 좌표 압축은 수직선 상 넓은 범위에 비해 적은 점을 찍는 것이 비효율적이라는 점에서 고안한 기술이다. ( 위 블로그를 참고하였다.) 점의 좌표를 인덱싱하여 정렬된 순서로 번호를 매기는 방식이다. unique : ex > unique(index.begin(), index.end()) index 라는 벡터의 처음부터 끝까지 중복되지 않게 원소를 재.. 2021. 2. 19.

[백준] 2660 회장 뽑기 Floyd Warshall 문제 : www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 분석 : 이 문제 역시 플로이드 와샬을 이용해 풀었다. 문제 이해가 잘 안되었는데 회장 후보의 점수, 회장 후보의 수 회장 후보 인덱스 를 출력하는 문제였다. 이 모임은 친구, 친구의 친구, 친구의 친구의 친구 .. 관계에 대해서 1, 2, 3점을 가진다. 회장은 점수가 가장 적은 즉 가능한 모든 사람들에 대해서 친구인 사람이 회장 후보로 적합하다고 얘기한다. 그렇지만 한 사람이 친구, 친구의 친구 관.. 2021. 2. 18.

[백준] 11403 경로 찾기 Floyd Warshall 문제 : www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 : 이 문제는 플로이드 와샬 방식으로 접근해보았다. 백준 논의 보니까 DFS, BFS 로도 풀 수 있는 것 같아 보였다. 플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 정점에서 모든 정점으로의 최단 경로를 찾는데 사용되는 알고리즘이다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬은 거쳐가는 정점을 기준으로 접근해야 한다는 점이 포인트였다. 플로이드 와샬은 다이나믹 프로그래밍에 의거한다고 한다. 가장 이해되는 .. 2021. 2. 18.

[백준] 2178 미로 탐색 bfs 문제 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 분석 : 이 문제는 경로 탐색 문제이다. DFS, BFS 둘 중 아무거나 풀어도 상관 없어 보인다. 나는 BFS 연습을 위해 BFS 방식으로 풀었다. cin 은 공백 기준으로 input을 받는 것 같아서 scanf의 도움을 받았다. cin 으로 풀 수있는 방법 알면 알려주시면 감사하겠습니다. 🥺 2차원 행렬에 값이 1 (지나갈 수있는 칸) 인경우 true로 담았고 아니면 false로 값을 초기화 하였다. 이 문제는 input 값이 0.. 2021. 2. 17.

[백준] 1931 회의실 배정 문제 : www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 분석 : 이 문제는 대표적인 greedy algorithm으로 푸는 문제이다. 회의실, 가방 배낭 등 고전적인 문제 유형인거 같다. 벡터에 인풋값을 모두 담은 뒤 핵심은 회의가 끝나는 시간 second 를 기준으로 정렬을 하는 것이었다. 그리고 for문을 돌면서 검사하는데 이전 회의의 끝나는 시간 < 다음 회의 시간 이면은 회의가 시작 될 수 있는 것이므로 cnt 값을 증가시켜 회의의 갯수를 셌다. c++ 코드 : // // 1931_room.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong.. 2021. 2. 17.

[백준] 19598 최소 회의실 개수 문제 : www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 분석 : 이 문제는 주어진 인풋에 대해 필요로 되는 최소 회의실 개수를 구하는 문제다. greedy를 이용해 풀었고 회의실이 3개, 회의실 이용 시간은 0 40 15 30 5 10 으로 주어질 때 1. 회의 시작 시간을 기준으로 정렬을 한다. 0 40 5 10 15 30 함수 안에서 처음에 0, 40을 vv vector에 담은 뒤 v 함수 다 돌 때까지 vv 크기만큼 if문을 돌게된다. else 문.. 2021. 2. 17.

[백준] 10818 최소, 최대 문제 : www.acmicpc.net/search#q=10818&c=Problems 검색 www.acmicpc.net 분석 : 이 문제는 못푼 문제에 있길래 클릭 해보니 비교적 간단한 문제라서 풀었다. 1년전 문제라니 세월이 빠르구나 * 반례로 1 10 케이스와 2 10 10 케이스가 있으니 잘 생각해보길 바란다. 처음에는 for문 하나에 input 값 넣고 바로 비교 하려 했는데 위 두 케이스 때문에 분리해서 담아줬다. C++ 코드 : // // 10818_min_max.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/02/12. // #include #include #include using namespace std; int main(){ int n, max.. 2021. 2. 16.

[백준] 2110 공유기 설치 문제 : www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 분석 : 이 문제는 내 기준선에서 조금 신박했던 (?) 이분(이진) 탐색 문제였다. 문제를 이해하는데에도 헷갈렸다. 처음에 정렬을 한 뒤 start 와 end 변수를 간격의 최소, 최대 거리로 설정해 둔뒤 이 위치를 mid 값 변경을 통해 index 위치를 변경 시킨 뒤 start 가 end 인덱스보다 커지게 되면 종료한다. 비교 기준은 mid 값으로.. 2021. 2. 16.

[백준] 2252 줄세우기 문제 : www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 분석 : 이 문제는 종만북 DFS BFS 부분의 대표적인 예제 중 위상 정렬에 관한 문제였다. 위상 정렬이란 의존성이 있는 작업이 주어질 때 이를 어떤 순서로 수행해야 하는지 계산한다. 이때 의존 관계를 DAG(사이클 없는 그래프) 로 표현한다. 사이클이 없다는 뜻은 즉 한 방향에서 한 방향으로 흘러가는 꼴의 그래프를 말한다. 그렇기 때문에 기존 DFS BFS 는 트리 .. 2021. 2. 14.

[백준] 10828 stack 문제 : www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 분석 : 을 사용하여 비교적 쉽게 풀 수 있었던 문제였다. 다만 처음으로 segmentation fault 컴파일 에러가 떴는데 top 부분에 empty 조건을 검사하지 않아서 난 문제였다. 정의된 문제를 앞으론 더 잘 읽어야겠다. 그리고 처음으로 cin 이 공백 기준으로 분리해 읽는다는 점을 알게 되었다. 이를 위해 getline 함수를 사용해야 했고 cin 과 getline을 겸용.. 2021. 2. 6.

[백준] 1915 가장 큰 정사각형 DP 문제 : www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 분석 : 대표적인 DP 문제로 1씩 더하는게 곧 정사각형의 한 변이 된다는 게 신기했다. DP가 전에 한번 공부했을 때 잘 이해가 안됐는데 이번에 조금 알거 같다는 생각이 들었다. 우선 arr이라는 원래 2차원 배열을 만들고 memo라는 배열에 값을 계산해 누적한다. arr[i-1][j-1], arr[i-1][j], arr[i][j-1] 모두가 1일때만이 arr[i][j]과 함께 정사각형을 만들 수 있으므로 그런 경우만 검사 한 뒤 1을 더해 한변을 memo 배열에 누적해.. 2021. 2. 5.

[백준] 1987 알파벳 DFS 문제 : www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 분석 : 위 문제는 전형적인 DFS 문제이다. 처음에는 오른쪽과 아래쪽으로 나아가는 것만 고려했고 수행한 알파벳은 set 함수에 저장해 놓아야지 생각하여 접근했었다. 하지만 안좋은 알고리즘이었다 하하 만약 진행 중 동일한 알파벳을 만난다면 진행한 것을 진행하지 않은 것처럼 하여 다른 방향으로 탐색하는 것이 포인트였다. 재귀함수 사용하는게 추상적이라 잘 이해가지 않아 다른 문제들도 많이 풀어봐야겠.. 2021. 2. 5.

[백준] 2470 두용액 이분탐색 문제 : www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 분석 : algorithm의 sort 함수는 기본 sort 함수와 달리 마지막 인자에 사용자 정의 함수를 추가해 정렬할 수 있다. 위 함수를 이용해 1) 배열을 절대값 기준으로 정렬 2) 절대값 비교를 통해 원래 값 변수에 저장 후 누적 3) 마지막으로 산성과 알칼리 값 구분해 swap 하여 출력 하는 방식을 사용하였다. c++ 코드 : // // 2470_soluti.. 2021. 2. 5.

이전 1 2 3 4 다음

티스토리툴바