본문 바로가기

Algorithm🐰96

[프로그래머스] 하샤드 수 basic 문제 : programmers.co.kr/learn/courses/30/lessons/12947 코딩테스트 연습 - 하샤드 수 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하 programmers.co.kr 분석 : %와 / 를 이용한 누적 값 계산 문제다. temp 변수를 안 쓰고 x원본 값을 나누고 마지막에 비교하는 작업을 했더니 계속 에러가 났다 다음부턴 실수 안해야지 c++ 코드 : #include #include using namespace std; bool solution(int x) { bool answer = true; int s.. 2021. 2. 24.

[백준] 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.

[백준] 2467 용액 이분탐색 문제 : www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 분석 : 이 방식은 시간 초과가 났다. 산성과 알칼리 용액을 구분해 배열에 담았고 각 배열이 끝날때까지 O(n^2)으로 탐색하는 방법을 사용했는데 가장 비효율적으로 문제를 푼거 같다. 그리고 딱히 map 함수를 사용하지 않아도 되었는데 쓸데 없는 악세사리가 많은 느낌 .. 문제에서 더 효율적인 방법을 찾아 해결하였다. C++ 코드 : // // 2467_solution.cpp // SOMA👩🏻‍💻.. 2021. 2. 5.

이전 1 2 3 4 5 다음

티스토리툴바