# ps
백준 16965 - 구간과 쿼리
문제 https://www.acmicpc.net/problem/16965 리뷰 BFS를 통하여 풀이할 수 있는 문제였다. 먼저 각 구간을 나타내기 위해 시작점(s)과 끝점(e)을 필드로 가지는 클래스 Pair를 산정하였다. 이 구간들은 List에 저장하였으며 구간의
백준 13265 - 색칠하기
문제 https://www.acmicpc.net/problem/13265 리뷰 DFS나 BFS로 풀이할 수 있는 문제였다. 필자는 DFS로 풀이하였다. 문제의 조건에 따라 DFS를 통해 현재 탐색 중인 정점과 다른 색으로 다음에 탐색할 정점들을 색칠하는데, 만약 연
백준 1277 - 발전소 설치
문제 https://www.acmicpc.net/problem/1277 리뷰 다익스트라를 통해 쉽게 풀이할 수 있는 문제였다. 먼저 $W$개의 이미 연결된 간선은 $0$의 비용을 가지는 것으로 설정하여 그래프에 반영한다. 그리고 발전소들의 좌표 정보를 받은 후 각
[C++][백준 14716] 현수막
글자의 개수=연결 요소의 개수BFS, DFS를 사용하여 연결 요소를 확인해 주는 방법으로 접근하면 된다.어차피 개수만 세어주면 된다는 점에서 이미 개수를 세어준 글자는 필요 없다.즉 글자를 지우면서 세어줘도 된다는 것이다.2중 반복문을 돌면서 글자가 없으면 넘어가고 글
[C++][백준 1026] 보물
B에 있는 수는 재배열하면 안 된다고 적혀있기에 건들면 안 될 것 같은 느낌이 든다.하지만 더하기의 경우 순서가 상관없기에 두 배열 모두 정렬해도 된다.문제의 제약이 풀이의 제약이 될 수 없다는 것을 알 수 있다.오름차 순, 내림차 순으로 정렬하여 곱하면 가장 작은 S
[C++][백준 5639] 이진 검색 트리
이진 검색 트리에서 왼쪽 노드는 작고 오른쪽 노드는 크다는 점을 활용하면 된다.전위 순회의 결과이기에 다음 입력이 현재 값보다 낮은 값이면 왼쪽 서브 노드라는 것을 알 수 있다.오른쪽 서브 노드의 값은 지금 노드의 값보다 큰 값인데 가장 처음 만난 큰 값이 오른쪽 서브
[알고리즘 문제 해결 전략] 06.5 문제: 게임판 덮기 (문제 ID: BOARDCOVER)
1 문제 알고리즘 문제 해결 전략의 두번째 문제... 첫 문제 포스트를 정리하고 다시 풀기까지 많은 시간이 걸렸음... 문제를 푸는데 생각보다 엄청 헤맸다... 결국 이 블로그 글을 보고 깨달음을 얻음. 아래에 자세히 소개할 예정! 2 문제 해결 알고리즘 > 1.
[C++][백준 30793] gahui and sousenkyo 3
예비 결과와 최종 결과가 나온다.예비 결과를 최종 결과로 나누었을 때 나오는 값을 기준으로 출력해 주면 된다.조건문을 활용해서 값을 분류해 주면 된다.
[C++][백준 30792] gahui and sousenkyo 2
지금 가지고 있는 투표수로 몇 등을 할 수 있는지 확인하는 문제이다.내가 몇 등인지는 나보다 높은 사람의 수로 결정되므로 나보다 투표수를 많이 받은 사람의 수를 세어주면 된다.
[C++][백준 30791] gahui and sousenkyo 1
16등부터 20등을 준다. 16등하고 경쟁할 수 있는 상대를 찾아내면 된다.문제에서 요구하는 바로는 16등하고 1000보다 높은 차이를 내는 경우는 경쟁자라 볼 수 없다.해당하는 인원을 제외하고 세어주면 된다.
백준(Baekjoon) 15971번 : 두 로봇 - python 풀이
[그래프 탐색, 다익스트라] 임의의 두 정점 위의 로봇이 서로 연결될 수 있도록 각 로봇이 이동하는 최단 거리를 구하는 방법을 알려드립니다!
백준 20304 비밀번호 제작
문제에서 안전 거리를 두 비밀번호를 이진법으로 나타냈을 때 서로 다른 자리 수로 정의.비밀번호는 0 ~ n까지 사용할 수 있음.비밀번호가 한자리 플립된 다른 비밀번호와 연결된 그래프에 대해 두 비밀번호 사이 최단 경로는 두 비밀번호의 안전 거리.로그인 시도에 사용된 비
[C++][백준 17387] 선분 교차 2
CCW를 활용하면 된다.CCW를 활용하면 방향을 확인할 수 있다.한 선분을 기준으로 삼고 다른 선분의 점을 이용해서 방향을 구했을 때 교차해있다면 양수와 음수가 나와야 한다.왜냐하면 시계방향에 한 개, 반시계 방향에 한 개 존재하기 때문이다.이런 식으로 떨어진 경우에는
[C++][백준 11758] CCW
기하학 문제이다.CCW를 활용하여 방향을 확인해 주는 것이다.CCW는 외적을 이용해서 평면 위의 3점의 방향 관계를 구하는 공식이다.방향에 따라 외적 했을 때 벡터의 Z 값 부호가 달라진다는 점을 활용하는 것이다.
백준 23286 - 허들 넘기
문제 https://www.acmicpc.net/problem/23286 리뷰 플로이드-워셜 알고리즘을 이용하여 풀이할 수 있는 문제였다. 주어진 문제의 조건중 가장 높은 허들 높이의 최솟값이라는 조건을 잘 이해하지 못해 상당히 애를 먹었다. 결론적으로 그냥 말그대로
[C++][백준 10974] 모든 순열
1부터 N까지의 범위의 반복문을 N 만큼 돌면 모든 순열을 구할 수 있다.반복문을 N 만큼 돌고 싶다면 재귀 함수를 활용해 주면 된다.이미 사용한 수는 체크해 주면서 사용하지 않은 수를 골라서 다음 재귀 함수로 넘어가면 된다.반복문이 1부터 시작하기에 자동으로 사전순을
Linux Command - ps
documentation실행되고 있는 process들 중 특정 process들에 대한 정보를 보여주는 command다.command 실행 '순간'에 있던 process들에 대한 정보를 보여준다.parameter을 부여하지 않으면 command를 실행한 시점에서, com
[C++][백준 1475] 방 번호
업로드중..막대를 세운다고 생각해 보자.가장 튀어나온 막대의 값이 세트의 값인 것이다.하지만 예외로 6, 9는 합쳐서 사용할 수 있다.합친 뒤 반으로 나누면 다른 값과 동일하게 사용할 수 있는 것이다.10의 크기를 가지는 배열을 선언해 준 뒤 0~9까지의 값을 세어준다
[C++][백준 17837] 새로운 게임 2
생략말이 쌓일 수 있다는 점을 고려해 줘야 하는 문제이다.여러 방법을 생각해 봤는데 중간 지점을 잘라서 옮겨야 하는 경우가 존재하기에 vector를 사용하면 좋을 것 같았다.좌표마다 vector를 두어서 쌓아두는 방식으로 접근해 봤다.구현 문제에 특성상 적혀있는 대로