문제 풀이

[baekjoon 2589] 보물섬 (BFS, 브루트포스) (C++)

www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제의 조건은 "보물은 서로 간에 최단 거리로 이동하는 데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다."이다. 즉, 보물의 위치가 정해져 있지 않고, 탐색할 수 있는 육지 중에서 최단 거리 중 가장 긴 시간이 걸리는 곳을 찾으면 된다. 처음에 문제를 보고, 위치가 없는데 어떻게 탐색을..

[baekjoon 20040] 사이클 게임 (유니온 파인드, union-find) (C++)

www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 유니온 파인드를 통해 사이클 판별을 하는 문제이다. 두 개의 정수가 주어지고, 그 둘은 연결되는데 선분들이 연결되다가 사이클이 발생할 때를 출력한다. 사이클이 생성되지 않을 경우 0을 출력. #include using namespace std; int parent[500001], n, m, from, to, answer; int getParent(int x) { if (parent[x] == x) retu..

[프로그래머스 LV4] 3 x n 타일링 (DP) [C++]

programmers.co.kr/learn/courses/30/lessons/12902#qna 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 백준의 이 문제와 똑같다. 밑의 설명을 참고하면 좋을 것 같다. bbeomgeun.tistory.com/30 [baekjoon 2133] 타일 채우기- DP(동적 프로그래밍) (C++) www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 일반적인 타일 문제라 생각했지만 추가적인 아이디어가 필요한 문.. bbeomgeun.tistory.com 차이점은 백준 문제는 30까지 구하지만 프로그래머스는 n이 5000까지..

[프로그래머스] 여행경로 (문자열, BFS) [C++]

programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 주어진 경로대로 탐색을 하면 되는데, 노드가 문자열이기도 하고 숫자로 매핑을 어떻게 해야 할지 몰라서 너무 복잡하게 풀었다. #include #include #include #include #include #include using namespace std; int check[10001][10001]; map m; vector v[10001]..

[프로그래머스] 등굣길 (DP, DFS) [C++]

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 웅덩이를 피해서 목적지까지의 경로의 수를 세야 한다. 다른 분들은 DP를 이용해서 쉽게 풀었지만, 나는 DP+DFS로 풀었다. #include #include #define MOD 1000000007 using namespace std; int dp[101][101], arr[101][101], N, M, xmove[2] = {1, 0}, ymove[2] = {0,..

[프로그래머스 SQL] 입양 시각 구하기(2) group by, recursive

programmers.co.kr/learn/courses/30/lessons/59413 코딩테스트 연습 - 입양 시각 구하기(2) ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 programmers.co.kr 평범하게 count 후 group by를 하면 데이터가 7~19시까지밖에 출력이 되지 않는다. 하지만 문제에서는 데이터가 없어도 0~23시까지의 데이터를 출력하라는 요청이다. 따라서 WITH RECURSIVE 구문을 통해 0~23까지의 HOUR을 가진 테이블을 만든 후 그 테..