개인사

리뷰시간마다 번지는 물을 피해 S에서 D로 이동하는 문제, 첫번째는 방문배열을 조건에 넣어 주지 않았고, 두번째는 'X'가 있는지 몰랐다... 쉬워보이는 문제더라도 문제를 잘 읽어야겠다. https://www.acmicpc.net/problem/3055 문제 풀이r과 c값을 가져오고 string으로 이루어진 맵을 입력 받아준다.문자열의 각 문자를 참고하여 S일 경우와 D일 경우 위치 좌표를 저장해 둔다.만약 *일 경우 물이 번짐을 체크해야 하므로 별도로 준비해둔 큐에 저장해 준다.bfs를 시작하고, 시작 위치를 미리 준비해두었던 큐에 추가해 준 뒤 탐색을 시작한다.만약 물이 맵에 존재한다면 이미 큐에 저장되어 있을 것이다, 큐에서 pop한 char이 *라면 다음 이동방향이 .일 경우 *로 변경해 준다.만..

리뷰DFS를 통한 완전탐색과, PQ를 통한 값 비교, 시뮬레이션 까지 필요한 까다로운 문제   SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 풀이각 테스트 케이스 마다 init과 input, solution으로 나누어 진행하였다.init에서는 각 테스트 케이스마다 초기값을 세팅해 준다.input에서는 맵 정보와 사람, 계단 정보를 받아와 초기화 해준다.solution에서는 DFS를 실행하고, DFS 내부적으로 재귀를 거치며 기저조건에 달성하면 시뮬레이션을 돌려준다.모든 재귀가 종료되고 나면 ans에 저장 되어 있는 값을 각 테스트 케이스마다 출력해주면 된다. 참고 사항1. init()맵 정보를 모두 0으로 ..

리뷰자꾸 50개의 테스트 케이스에서 43개만 맞아서 고민을 했었는데, 합쳐지는 경우가 2개의 미생물 뿐만 아닌, 3개의 미생물인 케이스가 있었다. SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 풀이각 테스트 케이스에 대해서 init, input, solution 함수로 나누어 풀이를 하고 테스트 케이스에 대한 답을 도출하였다.1. init()정답을 도출할 ans 변수를 0으로 초기화 해준다, 맵을 나타낼 2차 배열 lst를 모두 0으로 초기화 해준다. 2. input()n, m, k 값을 입력 받고, 미생물에 대한 정보를 1번 인덱스 부터 k번 인덱스로 받아와 bugs 배열에 저장해 준다.또한 맵의 받아온 ..

리뷰2D 시뮬레이션을 통해 사용자의 이동에 따른 충전량의 최대 합계를 구하는 문제  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com BC위치(x, y)와 충전 범위 c, 성능 p로 이루어진 구조체로 정의해 준다.BC의 충전 범위는 겹치는 경우가 있고, 겹쳐지지 않는 경우가 있다.BC의 개수는 1 ~ 8개 존재할 수 있으며, 같은 위치에 2개 이상의 BC가 설치된 경우는 없다.사용자사용자는 총 2명이고, 사용자 A는 0, 0 좌표 사용자 B는 9, 9좌표에서 시작한다. 맵은 10 * 10 고정총 이동 시간 m은 20이상 100 이하의 정수이다, 사용자 A와 B가 동시에 같은 위치로 이동할 수 있다. 시뮬레이션시간에 ..

리뷰배열내 요소를 조합하여 특정 숫자를 만족하는 조합의 개수를 찾기https://www.acmicpc.net/problem/3273  문제 풀이n을 입력 받고 배열 arr에 n개의 수를 입력 받아준다. 이후 목표 숫자 target을 입력 받고 arr 배열을 정렬해 준다.개수를 샐 변수 cnt를 0으로, 왼쪽에서 탐색할 left 변수를 0으로, 오른쪽에서 탐색할 right 변수를 n - 1로 초기화 한다.left가 right보다 적을 때 while 루프를 실행한다.arr[left]와 arr[right]를 더했을 때 target보다 크다면 right를 1 줄여준다.arr[left]와 arr[right]를 더했을 때 target보다 작다면 left를 1 늘려준다.만약 target을 찾았다면 cnt를 1 증가시..

리뷰예상 도착지가 주어 졌을때 출발 노드에서 도착 노드까지의 경로 중 일부 경로가 포함 되어있는지를 확인 해야하는 문제 문제 풀이테스트 케이스를 통해 구분된다, 각 테스트 케이스를 반복문을 통해 열어준다.노드 수 n, 간선의 수 m, 예상 도착지의 수 t, 시작 노드 s, 포함 간선을 나타내기 위한 g, h를 받아온다.간선을 양방향으로 받아 주고, 예상 도착지 t개를 입력 받고 오름차순으로 정렬해 준다.다시 t개의 예상 도착지를 순회하며 출발지 부터 예상 도착지 까지의 최단 거리를 구해준다.g와 h를 포함하여 도착지 까지 가는 거리를 찾고, 둘을 비교하여 같다면 도착 노드를 출력해 준다. 참고 사항g와 h를 포함하여 도착지 까지 가는 거리를 찾는 방법은 s -> g -> h -> 도착노드 이거나 s ->..

개요정렬된 데이터에서 탐색 범위를 반씩 줄여가면서 빠르게 특정값을 찾는 알고리즘데이터가 주어졌을때 우선 정렬이 된 상태로 만들어 주어야 한다. algorithm을 include하고 sort를 진행한다.이진 탐색 Flow탐색 범위에서 시작 지점 index를 left, 종료 지점 index를 right로 지정한다.(left + right) / 2를 통해 left와 right의 중간 index, mid 값을 구해준다.찾으려는 수와 배열 내에서 mid 인덱스를 가진 수를 비교해 준다.만약 찾으려는 수가 mid 인덱스를 가진 수보다 작을 경우 mid보다 왼쪽, 클 경우 오른쪽에 있는 것이다.만약 왼쪽에 있을 경우 left는 그대로 두고 right를 mid로 교체해 준다.오른쪽에 있을 경우 right는 그대로 두고..

리뷰촌수를 구하는 완전 탐색 문제, DFS, BFS, 다익스트라 뭘 써도 괜찮을 듯 하다.  문제 풀이n, sn, dn, m값을 차례로 입력 받고, 방문 처리 배열을 101 크기, 0으로 초기화 해준다.정수형 2차 벡터 lst에 노드 정보를 받아와 인접 리스트를 생성해 준다, 단 방향이던 양 방향이던 상관 없을듯?이후 bfs를 돌려주고 시작 노드에서 종료 노드까지의 거리를 구해주는데, 이때 방문 배열에 이전 값 + 1을 해주는 식으로 촌수를 구해주었다.큐가 빌때까지 while을 돌다가 목표 노드에 도달했을 경우 현재 노드의 방문 배열 값을 리턴해준다.만약 while이 종료될 때 까지 만나지 못하고 bfs가 종료된다면 -1을 리턴해 준다.리턴값을 출력해주면 된다. 참고 사항없음  정답 코드#include#..

개요특징특정 노드에서 연결 되어 있는 모든 노드까지의 최단 거리를 구할 수 있다.가중치는 양수여야만 하며 음수일 경우 해당 간선을 계속 방문하게 되어 루프에 빠지게 된다.양방향 및 단방향 그래프 및 2차 배열 형태에서도 에 모두 사용 가능하다.동작 요약모든 노드 까지의 거리를 2e9 혹은 INT_MAX와 같은 값을 사용하여 최대치로 설정한다.시작점 노드 자기 자신 까지의 거리를 0으로 설정하고, 우선순위 큐에 자신을 추가한다.첫 탐색 시 자신과 연결된 인접 리스트를 참고하여 해당 노드까지의 거리가 현재 거리보다 짧다면 갱신해 주고 해당 노드를 우선순위 큐에 넣어준다.이후 우선순위 큐에 있는 노드와 연결된 인접 리스트를 참고하여 거리 정보가 최소가 되도록 갱신해 주는 작업을 반복한다.우선순위 큐에 더 이상..

리뷰모든 노드를 연결하는 최소비용을 구하는 문제, 노드가 섬이라는 점에서 2차원 시뮬레이션 구현 문제이다.https://www.acmicpc.net/problem/17472 문제 풀이n과 m값을 입력 받고 2차원 맵을 입력 받는다.각각의 섬을 노드화 시켜준다. n * m맵을 순회하며 1을 만날 경우 바다가 아닌 지형은 모두 index로 맞추어 준다, 나는 2부터 index를 매겨줬고, 이때 노드의 개수 또한 세어주고, 해당 노드의 시작 좌표를 구조체 형태로 큐에 추가해 준다.큐에 추가된 노드를 기준으로 bfs를 실행해 각 섬까지의 모든 간선을 구해 edges 벡터에 추가해 준다.edges 벡터를 간선 기준으로 정렬 해주고, 유니온 파인드를 통해 최소 간선 비용을 구해준다.만약 모든 노드가 연결되지 못한다..