Jonyo Programming

[BOJ 2143(G3)리뷰] 투 포인터를 응용해야 하는 문제이다. 문제에서 배열이 두개가 주어지고, 두개의 배열을 이용하여 만들 수 있는 합 중 T를 만족하는 경우의 수를 찾아야 한다. 완전탐색하는 방법으로는 시간초과를 맞게 되므로 투포인터 알고리즘을 이용해야 한다. 투 포인터 알고리즘을 이용하기 위하여 A와 B배열에 대해 각각의 구간합을 저장하는 사전작업을 했다. 즉, 1,3,2,1 배열이라면 1 4 6 7 3 5 6 2 3 1 라는 별도의 배열을 만든다. 그리고 이렇게 만들어진 두개의 배열을 각각 오름차순으로 정렬 한 후에 하나의 배열은 시작부터, 하나의 배열을 끝부터 시작한다. 이미 이 배열에 구간의 합에 대한 경우의 수가 들어 있으니 이 두개의 배열의 합이 T를 만족하는 개수를 찾으면 된다. 다..

[BOJ 1039(G3)리뷰] 굉장히 어려웠던 문제다. 처음엔 이걸 어떻게 BFS로 풀라는 건지 한참 고민을 했다. 계속 고민을 하다보니 그냥 모든 경우에 대하여 BFS를 돌리면 되는 간단한 문제인가? 라는 생각이 들어 바로 코딩을 했지만 계속 메모리초과&시간초과가 났다. 시간초과가 났던 이유는 너무나 당연했다. 두개의 값을 바꾸는 과정에서 중복되는 값이 큐에 푸쉬되는 현상이 반드시 일어 날 수있고, K가 클수록 시간복잡도 측면에서 매우 큰 손해를 보게 된다. 따라서 중복된 값을 큐에 넣지않도록 별도의 처리를 해줘야 한다. 다만 이때 각각의 연산마다 중복처리를 하는것을 독립적으로 계산해야 한다. 즉, 16375 에서 61375가 되고 다시 16375가 될 수 있는것이다. 각각의 연산횟수마다 독립적으로 처..

[BOJ 1713(S1)리뷰] 시뮬레이션 문제다. 문제를 이해한 후에 적당한 자료구조를 이용하여 구현하면 된다. 나는 벡터를 이용하여 추천수와,학생 번호를 저장하고 사진틀에 올라간 학생들의 인덱스를 따로 기록해 놓았다. 학생번호 입력이 들어올 때 마다 해당 학생이 사진틀에 존재하는지 확인하고 다음의 과정을 거친다. 1. 사진틀에 존재하지 않는다면 - 사진틀에 공간이 있는지 확인하고 비어있다면 학생번호를 기록하고, 학생을 사진틀에 추가한다. - 사진틀에 공간이 없다면 추천수가 가장 낮은 학생의 사진틀을 삭제하고 추가한다. 2. 사진틀에 존재한다면 - 미리 기록해둔 인덱스를 통하여 벡터에 접근해 추천수를 증가시킨다. 이 과정을 순서대로 진행한 후에 최종적으로 벡터에 남은 값을 학생 번호를 기준으로 오름차순으..

[BOJ 1062(G4)리뷰] 처음에 문제 이해를 잘못해서 푸는데 시간을 오래 썼다. 문제의 조건을 보면 모든 단어는 "anta"로 시작되고 "tica"로 끝난다고 하였으니 K개의 글자에는 최소 "a,n,t,i,c"의 알파벳이 필요하다. 즉, K가 5미만 이라면 단 한개의 단어도 읽을 수 없다. 이 조건을 생각하며 나머지 알파벳에 대하여 완전탐색을 실시하면 된다. 이미 사용한 알파벳에 대하여 방문처리를 하고 남은 알파벳에 대해 완전탐색을 수행해 알파벳의 개수가 K개가 되었을때 읽을 수 있는 단어를 카운팅하고 최대값을 계산해주면 된다. 문제를 이해하고 나면 전형적인 백트래킹 문제로 바뀌게 된다. 그리고 알파벳을 체크하는 배열은 ASCII코드 값을 이용하여 관리하면 편하다. /* 21.01.11 BOJ : ..

[BOJ 3425(G2)고스택] 언뜻보면 가벼운 구현문제처럼 보이나 생각보다 푸는데 오래걸렸다. C++ STL에서 제공하는 스택을 이용하여 위에 주어진 연산들을 처리하면 된다. 주어진대로만 구현하는 것은 어렵지 않으나 몇가지 예외처리를 해야 할게있다. 문제에서 주어진것처럼 연산을 할 숫자가 부족할 경우, 0으로 나눴을 경우, 연산 결과의 값이 10억을 넘어갈 경우 에러로 간주해야 한다. 또 내가 오답처리를 받았던 이유 중 하나는 int 오버플로우를 생각하지 못했다. 10억 * 10억 연산을 할 경우 INT가 담을 수 있는 범위를 넘어버려 정상적인 연산이 불가능 하다. 따라서 자료형을 long형으로 처리해야 한다. 위에 나타난 예외들을 신경쓰며 문제에 주어진 조건대로 구현하면 정답처리를 받을 수 있다. /..

[BOJ 14921(G5)리뷰] 투 포인터 문제다. 투 포인터 개념을 안다면 어렵지 않게 풀 수 있다. 구간합을 구하는 일반적인 투포인터와 달리, 두 수를 더하여 0에 가장 가까운 수를 찾아야하는 문제이다. 오름차순으로 정렬된 상태에서 시작과 끝을 포인터로 가리키고 시작해야 한다. 예를들어 다음과 같은 INPUT이 있다고 하자. arr[5] = {-101 -3 -1 5 93} st는 0을 ed는 4를 가리킨 상태에서 시작한다. 처음엔 arr[st]+arr[ed] = -8 이라는 값이 나온다. 이 때 어느 포인터를 움직여야 할까? 만약 ed포인터를 1만큼 감소시킨다면 -96이라는 값이 나온다. 배열이 정렬되어 있으므로 ed를 감소시킬 수록 더 작은 값이 나오게 되므로 점점 0에서 멀어지게 될것이다. 그러므..

[BOJ 19238(G4) 리뷰] 시뮬레이션 + BFS문제다. 푸는데는 1시간 15분정도 걸린거 같다. 중간에 디버깅 하느라 시간을 좀 썼다. 정답비율이 낮길래 굉장히 어려운 문제일것이라 생각했는데 어렵다기 보단 구현을 하면서 여러가지 예외들을 신경 써야 한다. 우선 코딩을 하기전에 어떻게 구현을 해야할지 간략하게 정리를 하고 시작했다. 더보기 1.승객 탐색 ( BFS ) 2.거리,행,열 순으로 정렬 (가장 가까운 승객찾기) 3.가장 가까운 승객으로 이동. (연로 가능한지 계산) 4.목적지까지 거리계산 (BFS) +탐색중에 연료를 넘을경우 중단 (시간절약) 5.이동 가능하면 이동 이 정도로 정리를 하고 코딩을 들어갔다. BFS를 하나만 구현해서 하려고 했는데 약간 로직이 달라 승객을 찾는 BFS와 목적지..

[BOJ 1715(G4) 리뷰] 처음에 문제를 어떻게 풀어야 할지 고민했다. 이전에 이거랑 비슷한 유형의 문제 DP문제를 풀다 포기한적이 있었는데 이문제는 다행히 DP문제가 아니라 풀수있었다. 카드를 비교할때마다 그 값들이 더해지고 최종적으로 카드가 1묶음이 남을때 그 더해지는 값의 최소값을 구해야 한다. 인풋이 10만이기에 모든 경우를 탐색하는 경우 시간초과가 나게 된다. 따라서 방법을 탐색해야하는데 문제의 조건을 천천히 생각해보자. 일단 이 문제의 최종 목표는 카드를 1묶음으로 만드는것이다. 따라서 카드 두개를 합치는 과정은 계속 되야한다. 그리고, 카드를 합치는 과정에서 비용이 발생한다. 이미 존재하는 카드 묶음의 값을 바꿀수는 없으니 우리는 카드를 합치는 과정에서 발생하는 비용을 최소화 해야 한다..

[BOJ 17069(G5)리뷰] 오랜만에 푼 DP문제다. 오랜만에 DP풀려니까 역시 힘들었다. 이 문제는 예전에 풀려고하다 도중에 포기했던 문제지만, 이번엔 한번에 풀어서 기분이 좋다. 코드를 보면 알겠지만 문제에 주어진 조건을 그대로 구현하여 재귀함수로 처리하면 된다. 나는 미리 맵의 벽을 그린다음에 이동할 수 있는지 없는지 확인하고 이동이 가능하면 다음 함수를 실행하도록 했다. 맵의 최대크기가 엄청 크기에 dp를 사용하지 않으면 시간초과가 난다. 가고자 하는 경로가 이미 목적지에 도착한적이 있던 경로라면 굳이 가지 않고서도 도착할 수 있음을 알수있다. 이를 이용하여 실행시간을 단축해야 한다. /* 21.01.05 BOJ : 17069 파이프 옮기기 2 (https://www.acmicpc.net/pr..

[BOJ 1644(G3)리뷰] 지난 문제에 이어서 푼 투 포인터 문제이다. 이 문제는 N이 최대 400만 이므로 완전탐색을 통해 풀면 시간초과가 나게 된다. 또한 소수를 판별하는 알고리즘 역시 일반적인 방법이 아닌 속도를 개선한 알고리즘을 사용해야 한다. 나는 '에라토스테네스의 체' 알고리즘을 이용하여 N까지의 소수를 선별하여 arr벡터에 담는 작업을 했다. 그 후에는 N까지의 소수가 담긴 arr벡터를 이용하여 두개의 포인터로 부분합을 만족하는 경우를 찾으면 된다. 1과 2에대한 예외처리를 하고나서 정답처리가 나왔다. /* 21.01.04 BOJ : 1644 부분합 (https://www.acmicpc.net/problem/1644) 투 포인터 */ #include using namespace std; ..