live the life you love

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제 조건을 잘 읽고 그대로 구현하면 되는 문제이다. 구현 자체는 쉬운데, 문제를 제대로 안읽어서 놓친 조건과 문제에서 정보를 안준 것이 하나 있어서 좀 오래 걸렸다. 문제 조건을 요약하면 아래와 같다. 아기 상어의 이동 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없음 나머지 칸은 모두 지나갈 수 있다. 물고기 먹기 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 처음에는 산성, 알칼리 용액을 나눠서 계산하다 보니 계속 틀려서 블로그를 참고하여 풀었다. 투 포인터를 활용해서 풀려고 했는데, 풀고나니 이 문제는 절댓값을 활용해서 푸는 것이 더 효율적이라고 생각한다. 기존 접근 방식(오답) 산성 용액과 알칼리 용액을 나눠서 저장 후 정렬한다 알칼리 용액만 있는 경우, 산성 용액만 있는 경우 각 배열의 첫번째, 두번째 원소의 값이 최솟값이므로..

www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net map과 이분탐색을 활용해서 조건에 맞게 푸는 문제이다. 8번의 시도 끝에 풀었다. 문제 해결 문제를 읽어보면 다음과 같은 조건이 있다. 1 Key Value : 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다. 2 Key Value : 해당 Key로 검색된 데이터를 Va..

www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보� www.acmicpc.net 그렇게 어려운 문제는 아니었는데 복잡하게 생각을 해서 그런가 헤매다가 다른 블로그의 글을 보고 푼 문제다. 문제는 단순하다. 각 크레인 마다 1개의 박스를 옮길 수 있고 무게 제한이 있다. 한 번 옮길 때 마다 크레인이 옮길 수 있는 최대 무게의 상자를 옮겨주면 된다. 문제 해결 가장 무거운 박스와 가장 무거운 무게를 들 수 있는 크레인을 비교한다. 박스 값이 크레인 보다 크면 절대로 옮길 수..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 숨바꼭질 3의 경우는 1,2번 문제와 달리 순간이동을 하는데 걸리는 시간이 0초다. 이것을 잘 해결 하는 것이 매우 중요하다. 이 문제는 우선순위 큐(priority queue)를 활용하는 방법과 기본적인 큐를 활용해서 푸는 방법이 있다. 순간이동을 하는데 걸리는 시간이 0초이므로, 0초에 순간이동 하는 것을 큐에 먼저 삽입을 해줘야 한다. 우선순위 큐는 최대힙으로 구성되..

www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 숨바꼭질2는 1과 달리, 최단 시간으로 동생을 찾는 경우의 수까지 출력하는 문제이다. 경우의 수를 따로 체크하는 것을 제외하면 숨바꼭질 1 의 풀이와 똑같다. 문제해결 동생을 찾은 시간의 값을 저장하는 배열(answer)을 만든다. 최대로 걸리는 시간은 수빈이가 0에 있고, 동생이 100000에 위치하고 있을 때 1칸 씩 앞으로 가면 100000초가 걸리는 것이므로 배열..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 숨바꼭질 시리즈를 전부 풀어보려고 한다. 총 6개의 숨바꼭질 문제가 있으며, 내용은 거의 똑같지만 문제가 요구하는 조건이 조금씩 다르다. 대부분 탐색문제이며 BFS, DFS, 다익스트라를 잘 활용해서 풀면 될 듯 하다. 동생의 위치를 찾을 수 있는 가장 빠른 시간을 구하는 것이므로 BFS를 활용해서 풀 수 있다. 기본적인 BFS를 구현하면 되는 간단한 문제였다. 문제 해결 큐에 ..

www.acmicpc.net/problem/16113 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 � www.acmicpc.net 시뮬레이션 문제였다. 구현 방법을 떠올리는데 크게 어렵진 않았지만, 사소한 오류를 고치는 과정이 꽤 걸렸다. 또한, 코드도 깔끔하지 않다. 중복된 코드도 있고 예외처리를 위해 goto를 사용했다.. 좀 더 깔끔하게 짤 방법이 있을 것이다. 문제 해결 방법 디지털 숫자를 위에서 아래로 읽었을 때 나오는 값을 '#'과 '.' 의 형태의 문자열로 따로 저장해둔다. 예를들어 2라는 숫자를 왼쪽 위에서 시..

오늘 나온 카카오 문제의 알고리즘 유형은 대략 아래와 같다 1번 : 문자열 파싱 및 조건에 맞게 처리 2번 : 백트래킹(조합) 3번 : 이분탐색 4번 : 다익스트라 or 플로이드 와샬(둘 다 가능) 5번 : 투 포인터 6번 : BFS+경우의 수 7번 : 트리 DP 7번을 제외하고는 다 아는 알고리즘인데 오랜만에 알고리즘을 푸니 제대로 못풀었다. 꾸준하게 푸는게 중요한 것 같다

www.acmicpc.net/problem/17479 17479번: 정식당 일반메뉴는 noodle 2개로 20,000원, 특별메뉴는 cutlet 2개와 friedrice 1개로 32,000원, 둘이 합쳐 52,000원으로 서비스메뉴 하나를 주문할 수 있다. www.acmicpc.net 해시 자료구조를 사용하고 싶어서 풀어본 문제 해시 맵을 4개 사용해서 각 메뉴, 가격, 주문수량에 맞게 정보를 저장해주면 된다. 구조체를 사용하여 해시 맵에 저장하면 더 간단하게 풀 수 있는데, 연산자 오버라이딩도 해줘야 해서 그냥 여러개의 해시맵을 만들었다. 4번 시도만에 해결했는데 틀린원인은 2개였다 service 오타 자료형 범위 오타는 금방 찾았지만, 자료형 범위를 찾는데 좀 오래걸렸다. 각 메뉴등급별로 최대 5만개..