![]()
문제 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 문제 풀이 4가지 경우의 수를 모두 구한다면 아마 시간 초과를 피할 수 없을 것이다. 해당 문제도 투 포인터 알고리즘을 사용해야 한다. 눈사람을 4개 골라야 하는데 투 포인터 알고리즘으로 어떻게 하냐~~ 할 수 있는데 세 용액 문제와 동일하게 탐색 숫자를 줄여주면 된다. 4개를 골라야 한다면 이미 2개를 고르고 나서 나머지 2개에 대해서 투 포인터 알고리즘을 사..
![]()
문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 풀이 투 포인터 알고리즘의 대표적인 예시 문제라고 할 수 있습니다. https://jja2han.tistory.com/284 투 포인터 알고리즘(Two Pointer) 알고리즘 스터디를 하다가 새로운 알고리즘을 발견해서 호다닥 공부해서 정리하는 "아주 주관적인" 글입니다. 🔎투 포인터 알고리즘을 쓰는 이유 완전 탐색을 할 경우 시간초과를 피하기 위해 jja2han...
![]()
문제 https://www.acmicpc.net/problem/27498 27498번: 연애 혁명 신촌고등학교 학생회장 기령이는 최근 학생들의 복잡한 사랑관계로 인해 고민이 많다. 학생들이 공부에 집중하지 못해 전반적인 성적이 하락하고 있는 것이다. 이에 기령이는 학생들의 복잡한 www.acmicpc.net 문제 풀이 저번 포스팅인 1197 최소 스패닝 트리를 풀면 아주 수월하게 풀 수 있습니다. 우선 문제가 굉장히 복잡해 보이지만, 핵심은 포기하도록 만드는 애정도의 합을 최소화하는것이 우리의 목표입니다. 우선 사랑관계는 여기서 정점들끼리의 간선으로 연결되어야한다는 뜻입니다. 문제에서 사랑관계가 이미 이루어진 관계는 반드시 포함되어야 한다고 정의했으므로, 사랑관계가 이루어진 관계는 반드시 간선에 포함시켜..
![]()
문제 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 풀이 골드 3이라는 난이도 치고는 접근방법을 빨리 생각해 낸 문제였던 거 같다. 배낭문제와 비슷하다고 생각하고 접근했었는데, 문제를 풀고 다른사람의 풀이과정을 보니 다들 배낭과 비슷하다고 생각했던 것 같다. 그 정도로 접근하기가 쉬웠던 문제였던것 같다. 추를 사용해서 만들 수 있는 모든 무게를 검사해 주면 된다. 추를 사용해서 만들 수 있는 무게에 대한 방법은 크게 3가지 방법이 있을 것..
![]()
문제 https://www.acmicpc.net/problem/20542 20542번: 받아쓰기 세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는 www.acmicpc.net 문제 풀이 우선 문제가 굉장히 길고 비슷한 말이 많아서 문제에 대한 정확한 파악이 필요하다. 입력은 크게 답변과 정답이다. 이 두 가지를 구분하는 것이 굉장히 중요하다. 우리는 답변을 수정,삭제,변환을 통해서 정답과 같은 문자열을 만들어야 한다. 그리고 날려쓰기라는 정보가 등장한다. i를 날려썼다면 i, j, l v를 나르였으면 v, w로 인식된다. 즉 우리가 ..
![]()
문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 난이도 있는 DFS, BFS 문제의 특징이라고 할 수 있다. DP와 같이 사용하거나, 삼차원 배열을 통한 방문 체크, 우선순위 큐 같은 경우가 있다. 해당 문제는 삼차원 배열을 통해서 벽을 부순 여부를 가지고 방문을 체크하는 것이 중요하다. 일반적인 이차원 배열로 방문처리를 할 경우 똑같은 좌표를 방문했지만, 해당 좌표를 이동하기 위해서 벽을 부순건지, 부..
![]()
문제 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제 풀이 항상 높은 난도의 BFS, DFS를 풀면 알 수 있듯이 최적화에 가장 신경을 써야 한다. 그렇지 않다면 무수히 많은 시간초과를 볼 수 있을 것이다... 문제의 핵심은 빈칸을 선택해서 사각형으로 바꾸고, 가장 길게 연결된 사각형의 크기를 구하는 것이다. 그렇다면 우리는 기존의 배열에서 사각형들을 라벨링 하는 것이 필요하다. 왜 라벨링을 해야하는가에 대해서 작업의 흐름을 판..
![]()
문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 풀이 문제가 조금 길어서 요약해 보면 다음과 같다. 궁수의 위치는 N행 즉 주어진 배열 한 칸 아래에 있다. 궁수는 3명이고, 한 칸의 한 명만 있다. 궁수의 사정거리는 D이하이고, 여러명의 궁수가 하나의 적을 공격할 수 있다. 궁수는 반드시 가장 가까운 적을 공격해야하고, 가장 가까운 적이 여러 명이라면 가장 왼쪽의 적을 공격한다. 중요한 점은 하나의 적이 여러 명의 궁수에게 공격받을 수 있다는..
![]()
문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 설명 문제 초반에는 단순하게 dfs를 진행해서 최대로 갈 수 있는 칸 수를 기록하면서 진행했다. 골드 3치고 문제가 너무 쉽다고 생각했는데, 34% 정도에서 시간초과가 발생했다. 생각해 보면 당연하다. 최대 배열 크기가 500이고, 500x500을 계속해서 무식하게 탐색하면 시간초과가 나는 건데 왜 이 생각을 못했을까. 그렇다면 수정해야 될 것은 탐색을 하는 범위라고 생각했다..
