알고리즘/백준61 [백준][백트래킹] 6603 로또 로또 문제는 백트래킹을 이용해서 해결합니다. 2019. 10. 7. [백준][그리디] 11399 ATM ATM문제는 그리디 알고리즘을 이용해서 해결할 수 있습니다. 2019. 9. 23. [백준][DP] 11727 2Xn 타일링 2 2xn 타일링 2문제는 다이나믹 프로그래밍으로 처리할 수 있습니다. 1칸일 때 타일을 깔 수 있는 방법은 타일을 세로로 까는 방법 1개 입니다. 2칸일 때 타일을 까는 방법은 2X2 타일 하나를 붙이는 것과, 타일 두개를 세로로 까는 방법 2개 입니다. N번째 칸이 추가 될 때 타일 한개를 까는방법은 N-1번의 칸에 타일 한개를 추가하는 방법과 N-2번의 칸에 2개 짜리 타일을 추가하는 방법이 있습니다. N = [N-1] + [N-2] + [N-2] 2019. 7. 23. [백준][삼성SW검정] 14890 경사로 경사로 문제는 시뮬레이션 문제입니다. 문제가 제시하는 조건을 잘 읽고 풀어보면 됩니다. 가로, 세로는 하나의 로직으로 처리하기 위해서 배열 두개로 입력받아서 처리합니다. 1. 배열의 한행을 기준으로 합니다. 2. 순차적으로 읽어가다가 높이차가 1이면 경사로를 계산합니다. 3. 낮은 경우에는 경사로 길이(L) 만큼 앞으로 체크 4. 높은 경우에는 경사로 길이(L) 만큼 뒤로 체크 2019. 4. 8. [백준] 1260 DFS와 BFS DFS와 BFS문제는 정점사이의 간선을 탐색하는 기본적인 문제입니다. 간선사이의 연결 상태를 표현하는 link배열과 방문여부를 표현하는 visited 배열을 이용하여 해결합니다. 2019. 4. 2. [백준][삼성SW검정] 14500 테트로미노 테트로미노 문제는 가장 간단하게는 현재 시작점을 기준으로 각 모양별로 회전하여 이동가능한 위치의 배열을 만들어서 모두 더하면 됩니다. (다음 소스의 exceptions 를 확인) ㅗ 모양 외에는 DFS로 현재 시점부터 상하좌우로 4칸씩 이동하면 각 도형이 회전한 모양으로 생성됩니다 이를 이용해서 DFS로 이동하여 4칸 이동했을때의 최대값을 구하면 됩니다 2019. 3. 25. [백준] 7576 토마토 토마토 문제는 BFS를 이용하여 해결할 수 있습니다. 1. 익은 토마토(1)는 큐에 추가, 익지 않은 토마토(0)의 개수를 세어줌 2. BFS로 익은 토마토 상하 좌우의 토마토를 큐에 추가3. 처리일(day)을 추가하고, 다시 반복 4. 모든 토마토가 익었으면 결과를 출력하고, 아니면 -1 출력 2019. 3. 21. [백준] 11505 구간 곱 구하기 구간 곱 구하기 문제는 세그먼트 트리를 이용합니다. 세그먼트 트리를 이용하여 각 구간의 곱을 미리 계산하여 두고, 각 구간의 곱을 출력합니다. 2019. 3. 20. [백준][삼성SW검정] 13458 시험감독 시험 감독 문제는 다음과 같이 해결합니다. 1. 시험장 인원에서 총감독관의 인원을 빼고 sum + 12. 나머지 인원이 있으면 부 감독관이 필요한 개수를 sum + () - 나머지 인원 / 부감독관 - 나머지 인원 % 부감독관 - 이 두개를 계산하여 처리 2019. 2. 14. [백준][삼성SW검정] 12100 2048(Easy) 2048(Easy) 문제는 DFS를 이용하여 해결하였습니다. 1. 먼저 배열을 이동합니다. 2. 배열을 이동방향으로 순회하면서 병합합니다. - 이전 인덱스의 값과 비교해서 동일하면 현재 인덱스에 새로운값을 넣고, 이전 인덱스에 0을 입력합니다. 3. 배열을 이동 방향으로 다시 이동합니다. - 병합에서 발생한 0을 처리하기 위해서 입니다. 2019. 2. 12. [백준][삼성SW검정] 16234 인구이동 인구이동 문제는 BFS를 이용하여 해결합니다. 현재 위치에서 연합이 가능한 국가를 확인해서 국가의 합을 구해서 인구수를 재배치 하고,이를 계속 반복하여 인구 이동이 없을때까지 진행합니다. 2019. 2. 8. [백준][삼성SW검정] 14501 퇴사 퇴사 문제는 BFS로 현재 일자부터 순차적으로일을 할때와 하지 않을때로 나눠서 이동해가면서,얻을 수 있는 최대값을 이용하여 이동여부를 결정하면 마지막날의 최대값을 구할 수 있습니다. 2019. 2. 7. [백준][삼성SW검정] 15684 사다리조작 사다리조작 문제는 완전 탐색을 이용하여 처리합니다. 조합을 이용하여 3개 이하의 사다리를 선택 가능한 모든 경우를 생성하고, 이때 최소 횟수로 선택이 가능한 경우를 출력합니다. 2019. 2. 7. [백준] 15686 치킨 배달 치킨배달 문제는 먼저 조합을 이용해서 치킨집을 선택하고,도시의 치킨거리의 합을 구하면 되는 문제입니다. 치킨거리는 집을 기준으로 가장 가까운 치킨 거리의 합입니다. 2019. 2. 6. [백준][슬라이딩윈도우] 11003 최솟값 찾기 최솟값 찾기 문제는 슬라이딩 윈도우 알고리즘을 이용합니다. 슬라이딩 윈도우 알고리즘은 덱(Deque)을 이용합니다. 덱은 큐와 스택을 합친 동작읍 합니다. 먼저 입력한 데이터를 출력할 수도 있고, 뒤에서도 출력할 수 있습니다. 2019. 2. 3. [백준][DP] 9184 신나는 함수 실행 신나는 함수 실행은 다이나믹 프로그래밍을 이용하여 구성할 수 있습니다. 계산을 위한 점화식은 이미 문제에 나와 있습니다. 이 계산식을 그대로 구현하고, 계산결과를 배열에 넣어두고 동일한 계산은 이전 계산 결과를 사용하면 됩니다. 2019. 2. 2. [백준] 2151 거울 설치 거울 설치문제는 BFS를 이용해서 다음 경로를 탐색하고 메모이제이션을 이용해서 최소한의 횟수로 이동할 수 있는 지점을 제한합니다. 이동방향은 거울을 설치하는 경우 두가지와 거울을 설치하지 않는 경우 한기지로 선택합니다. 예를 들어 오른쪽으로 이동하는 경우 거울을 설치하면 위, 아래로 이동하고,거울을 설치 하지 않는경우 오른쪽으로 계속 이동하게 됩니다. 모든 경우를 계산하여 도착지점 문의 메모이제이션의 값이 최소 이동 횟수가 됩니다. 2019. 1. 29. [백준][삼성SW검정] 14502 연구소 연구소 문제는 3개의 벽을 세우는 조합과 벽을 세운뒤 바이러스의 개수를 세어서바이러스 영역이 제일 작을 때의 안전영역의 크기를 구했습니다. - 임시벽은 3으로 표시하였습니다. - 안전역역 = 공백구간 - 바이러스 개수 - 3(임시벽의 개수) 2019. 1. 11. [백준] 4673 셀프 넘버 셀프넘버는 숫자를 한자리씩 분리하여 더하여 주면 계산할 수 있습니다. 123을 1, 2, 3 으로 분리하는 방법은 10으로 나누어 몫은 다음계산으로 나머지는 더하여 주면 됩니다. 다음 처럼 구하면 됩니다. 123/10 = 12 123%10 = 312/10 = 1 12%10 = 21/10 = 0 1%10 = 1 2019. 1. 9. [백준][BFS] 1600 말이되고픈 원숭이 말이 되고픈 원숭이는 3차원 배열을 이용해서 해결합니다. 최소 이동횟수를 체크하는 배열을 만들고, x, y 위치로 이동할 때 최소이동 횟수로 도착하면 큐에 추가합니다. 여기에 말로 이동하는 것도 체크해야 하기 때문에 3차원 배열로[말이동횟수][x 좌표][y 좌표] 배열로 최소 이동 횟수를 체크해서 도착위치에 도달하는 최소 횟수를 체크합니다. 2019. 1. 9. [백준][그리디] 1931 회의실 배정 이 문제는 그리디 알고리즘을 이용하여 해결할 수 있다. 종료 시간을 기준으로 정렬하여 이전 종료시간이후로 가장빨리 시작하는 회의의 개수를 확인하면 된다. https://www.acmicpc.net/problem/1931 2018. 9. 18. [백준][그리디] 1049 기타줄 기타줄 문제는 그리디 알고리즘으로 해결한다. 적어도 끊어진 기타줄 만큼 구매할 수 있는 최소한의 돈을 출력하면 된다. 1. 패키지로 구매할 수 있는 최소값, 개당으로 구매할 수 있는 최소값을 구하고,2. 패키지로 구매하는 것보다, 개당구매로 6개를 구매하는 것이 더 싼지 확인하고,3. 끊어진 기타줄 만큼 패키지 구매 + min(개당 구매, 패키지구매) 적어도 끊어진 기타줄 만큼 구매이기 때문에 더 구매해도 되는 것을 생각해서 마지막에 패키지 구매가 최소값인지 확인하면 된다. https://www.acmicpc.net/problem/1049 2018. 9. 12. [백준][투포인터] 2003 수들의 합2 수들의 합2 문제는 투포인터 알고리즘을 이용하여 해결할 수 있다. s(start), e(end) 인덱스를 이용하여, start 로 배열을 증가하면서 sum을 증가시켜 M값과 동일하면 count를 증가하고 end를 증가하면서 sum 을 빼서 동일한 값이 있는지 확인한다. 배열 = {1 2 3 4 2 5 3 1 1 2}일때 start, end는 처음에 0번 인덱스 입니다. start를 증가하면서 1 + 2 + 3을 순서대로 해주면 sum은 6이 되어 M을 넘어서게 됩니다. 이때 end를 증가하면서 sum을 빼주면start가 2번 인덱스이고, end가 0번 인덱스인 시점에 합은 5가 됩니다. 이때 count를 1더해주면 됩니다. 이를 끝까지 반복해주면 됩니다. 2018. 6. 21. [백준][다이나믹] 2193 이친수 현재자리에 1은 앞자리에 0으로 끝난 이친수이고, 현재 자리에 0은 앞자리에 0, 1로 끝난 이친수 모두가 가능하다. 따라서 현재자리의 1은 앞자리 0의 개수이고, 현재라리의 0은 앞자리 0 + 앞자리 1의 개수와 동일하다. https://www.acmicpc.net/problem/2193 2018. 6. 19. [백준][스택] 10828 스택 스택 문제는 배열과 현재의 위치를 나타내는 커서를 이용하여 구현할 수 있다. 배열에서 현재의 아이템 인덱스를 알리는 current 인덱스를 가지고 케이스문에서 처리하면 됩니다. 2018. 6. 19. [백준] 2606 바이러스(유니온 파인드) 2606 바이러스 문제는 "유니온 파인드" 를 이용하여 해결할 수 있다. https://www.acmicpc.net/problem/2606 2018. 4. 20. [백준][그래프] 1922 네트워크 연결(프림 알고리즘) 네트워크 연결 문제는 프림 알고리즘으로 해결할 수 있다. https://www.acmicpc.net/problem/1922 2018. 4. 20. [백준][그래프] 위상정렬 1516 게임개발 인입간선 정보를 이용하여 위상정렬로 해결한다. https://www.acmicpc.net/problem/1516 2018. 1. 25. [백준][DP] 10942 팰린드롬? 펠린드롬 문제는 DP 로 풀이할 수 있다. 해결방법은 다음과 같다. https://www.acmicpc.net/problem/10942 2018. 1. 25. [백준][그래프][DAG] 1766 문제집 이 문제는 DAG 문제의 응용이다. 들어오는 간선의 개수가 0일 때 큐에 추가하여 다음 문제를 해결해 가면 된다. 쉬운 문제를 먼저 풀어야 하기 때문에 우선순위 큐(PriorityQueue)를 이용하여 처리하는 것이 더 좋다. https://www.acmicpc.net/problem/1766/ 2018. 1. 25. 이전 1 2 3 다음