본문 바로가기

코딩테스트/c++

 (20)
[백준] 14890번 경사로 해당 문제는 크게 요구하는 알고리즘은 없는 것 같다. 문제를 풀 때 재귀를 사용했지만 그렇게 복잡하지 않았고 구현의 비중이 큰 문제다. 요즘 어려운 문제를 풀 때 조건 하나하나씩 생각하려고 한다. 이렇게 문제를 접근하다 보니 구현하는 데 있어서 큰 도움이 된다. 이 문제는 총 3가지 경우로 나뉜다. 1. 다음 칸이 현재 칸의 높이와 같을 경우 2. 다음 칸이 현재 칸의 높이보다 높을 경우 3. 다음 칸이 현재 칸의 높이보다 낮을 경우 여기서 이제 쪼개서 생각한다. 1번의 경우는 그대로 진행하면 되고 2번은 높이의 차가 1보다 큰 경우는 false. 만약 차이가 1이라면 앞에서부터 현재 칸까지 L개의 현재 칸과 높이가 같은 칸이 필요하다. 만약 L개 미만일 경우 false. 3번의 경우도 2번과 비슷하다...
[백준] 1068번 트리 문제를 풀 때 예제에 자식이 2개가 최대인 예제 밖에 없어서 이진 트리인 줄 알고 문제를 풀었다가 질문게시판에 있는 반례에서 3개가 나오는 예시를 보고 다시 풀었다. node라는 구조체를 선언하고 node 내에 parent라는 부모 노드를 가리키는 node형 변수와 node형 벡터를 만들어 자식 노드들을 가리키게 했다. 처음으로 구조체 내에 벡터를 선언했는데 이번에 하면서 알게 된 사실이 있다. 구조체 내에 벡터를 사용할 때는 new를 사용하여 동적 할당을 해줘야한다. 그렇지 않으면 나중에 벡터에 push_back을 할 수 없다. 루트 노드가 무조건 첫 번째로 나온다는 보장이 없다. 따라서 입력한 숫자가 -1인 경우 루트 노드이므로 해당 노드의 num을 i로 설정하고 parent는 NULL로 설정한다. ..
[백준] 2146번 다리 만들기 해당 문제는 BFS를 활용한 구현 문제라고 볼 수 있다. 처음에 문제를 봤을 때는 많이 막막했지만 하나씩 생각하다보니 해결할 수 있었다. 가장 먼저 든 생각은 BFS를 활용한 거리 계산이다. 하지만 거리를 계산하기 위해서는 각각 섬들을 다르게 표시해야 한다. 표시를 했으면 이제 가장자리들로부터 시작하여 다른 섬까지의 거리를 계산한다. 정리하면 1. 섬들을 구분한다. 2. 해당 위치가 각 섬들의 가장자리인 경우에 BFS를 시작하여 다른 섬까지의 거리를 구한다. 3. 최솟값을 갱신해준다. lcount는 섬의 갯수로 각 섬들을 구분할 때 쓰인다. 지도를 (0, 0)에서 (N-1, N-1)까지 확인하며 육지인 경우 BFS를 시작하여 해당 섬에 lcount값을 더해준다. 그렇게 되면 만약 섬이 3개인 경우 섬은 ..
[백준] 1520번 내리막 길 DFS와 DP를 사용하여 내리막길로 길을 가다가 만약 방문한 적이 있는 칸이 있다면 끝까지 가지 않고 해당 칸의 DP 값을 더한다. DP는 해당 칸에서 목적지까지 갈 수 있는 경우의 수다. -1로 초기화한 이유는 0인 경우는 목적지까지 갈 수 있는 경우의 수가 없는 것이고 -1인 경우는 아직 방문을 안한 경우다. (x, y)가 목적지면 1을 리턴하고 방문한 적이 있으면 해당 DP값을 리턴한다. 아직 방문을 하지 않았으면 상, 하, 좌, 우를 보며 지점의 높이가 더 낮으면 해당 지점으로 가서 DP값을 계산하여 이렇게 상, 하, 좌, 우의 갈 수 있는 DP값을 더해준다. 전체 코드 #include using namespace std; int dx[] = { -1,0,1,0 }; int dy[] = { 0,-..
[백준] 3584번 가장 가까운 공통 조상 기본적인 트리 문제로 해당 노드의 부모 값만 잘 설정해준다면 어려움없이 풀 수 있다. 구조체 배열을 사용하여 풀었지만 풀고 나니 그냥 int형 배열을 사용하여 해당 index의 값을 부모로 설정해도 풀 수 있을 것 같다. 구조체 node에 부모를 가르키는 parent와 해당 node의 숫자 num을 저장했다. 크기가 10005인 node형 벡터를 선언하고 N-1개의 node 값을 입력 받으며 벡터에 값을 넣어준다. 공통 조상을 구할 두 개의 노드를 입력 받고 해당 노드의 부모들을 큐에 저장한다. 두 노드의 큐의 크기가 다를 경우 같게 해준 뒤 하나씩 빼면서 값이 같은지 비교를 한다. 크기를 같게 해주는 이유는 예시로 { 1, 2, 3 } 과 { 10, 9, 2, 3 } 인 경우 크기가 더 큰 오른쪽의 1..
[백준] 10026번 적록색약 전형적인 BFS 문제로 두 번째 경우에서 빨간색과 초록색을 동일한 색깔로 보는 조건만 처리해주면 된다. 각 칸에 색깔을 넣어준 뒤 변수들을 선언한다. 2중 for문을 돌며 방문하지 않은 곳이면 q에 넣고 BFS를 시작한다. curColor에는 시작한 구역의 색깔을 저장한 후 그 색깔에 맞는 count를 더해준다. 현재 위치의 상,하,좌,우를 확인하며 curColor와 같은 색깔일 경우 큐에 삽입 후 방문 표시를 한다. 2중 for문이 끝나면 각 색깔의 count를 더하여 출력한다. rgCount는 빨간색과 초록색의 구역의 개수를 합친 것이다. visited의 모든 값들을 false로 초기화한다. BFS 시작하는건 앞에서 했던 코드와 동일하고 상,하,좌,우 확인하면서 큐에 삽입할 때 현재 빨간색과 초록색을..
[백준] 2206번 벽 부수고 이동하기 3차원 벡터를 사용하여 해당 위치에 벽을 부수고 왔는지, 벽을 부수지 않고 왔는지 여부를 확인해야 한다. 그 후 BFS를 사용하여 목적지까지 갈 수 있는지 확인한다. board는 맵을 뜻하고 dis는 해당 위치까지의 거리를 뜻한다. 위에서 말했듯이 벽의 파괴 여부를 체크하기 위해 3차원 벡터로 선언했고 세번째 index가 0일 경우 부수지 않고 온 경우, 1인 경우 벽을 부수고 온 경우를 뜻한다. 그래서 큐의 자료형도 tuple을 사용하여 해당 위치에 벽의 파괴 여부를 표시했다. 만약 q에 { 1, 2, 1 }이 있으면 (1, 2)에 벽을 부수고 도달했다는 뜻이다. 이제 BFS를 적용할텐데 현재 위치가 1) 벽을 부수고 온 경우 1-1) 다음 위치가 벽이 아닌 경우 - 다음 위치가 벽을 부수고 방문한 적..
[백준] 9205번 맥주 마시면서 걸어가기 각 정점마다 갈 수 있는 정점을 연결하여 그래프를 이용하여 문제를 풀었다. 연결을 한 그래프를 가지고 dfs를 적용하여 페스티벌 좌표에 도착하면 1을 리턴하여 happy를 출력하고 0을 리턴하면 sad를 출력하도록 구현했다. visited는 해당 정점을 방문 여부를 판별하고 adj 2차원 벡터는 어느 정점끼리 연결되어 있는지 저장한 벡터다. adj[2]에 { 0, 1 }이 있으면 2번 정점은 0번 정점, 1번 정점과 연결되어 해당 정점으로 갈 수 있다는 뜻이다. 테스트케이스를 시작할 때 각 배열들을 초기화한 후 n+2개의 정점들을 입력한다. 입력 후 각 정점들간의 거리를 계산하여 맨해튼 거리가 1000보다 작거나 같을 경우 i번째에서 j번째로 갈 수 있다는 뜻이므로 adj 배열에 추가한다. 0번째 정점을..

티스토리툴바