Jonyo Programming

[BOJ 20055(S1) 리뷰] 오늘 푼 시뮬레이션 문제다. 설명은 위에 나온대로 친절하게 나와있다. 어떻게 구현을 할까 고민하던 중에 원형큐나 연결리스트를 사용하면 될 것같아 C++ STL에 존재하는 리스트를 사용해보기로 했다. 리스트를 사용해본적이 별로없어서 사용법을 익히느라 시간을 꽤 오래썼다. (그냥 연결리스트를 구현하는게 빨랐을듯) 시간은 오래걸렸지만 이 문제를 통해 반복자라는 개념에 대해서 조금 알게되었다. 난 이 문제를 해결하기 위해 리스트를 통해 입력을 받고 "올라가는 위치"와 "내려가는 위치"를 별도의 변수에 담았다. 그리고 벨트를 회전할 때 마다 이 값들을 바꿔주었다. 벨트를 회전하는것은 매우 간단하다. 리스트의 맨 끝에 있는 요소를 맨 앞에다 붙이고, 맨 끝에 있는 요소를 삭제하면 ..

[BOJ 14500(G5) 리뷰] 삼성 SW역량테스트 기출문제다. 처음엔 엄청 간단한 문제인 줄 알았다. 그냥 DFS로 구현하면 쉽게 풀릴것같아 쓱 구현해서 돌려보니 문제가 발생했다. DFS로는 이 모양을 만족할 수가 없는것이였다. 어떻게 처리할까 매우 고민했다. 이왕 하는거 논리적이고 깔끔하게 코드를 짜고싶어서 머리를 이리저리 굴려보았는데 답이 잘 안나왔다. 계속 고민하다보니 집중력이 계속 떨어져서 그냥 무식한 방법을 사용하기로 했다. DFS를하면서 두번째 블록에 위치할때, 위 모양이 나올 수 있는 경우의 수를 생각해서 그냥 인덱스로 접근해서 구해버렸다. 그나마 순열로 구현하는게 깔끔할테지만, 넥퍼뮤 사용법도 까먹고해서.. 그냥 무식하게 구해버렸다. 어쨌든 맞았으니 기분은 좋긴한데 왠지모를 찝찝함이 남..

[BOJ 14503(G5) 리뷰] 1월에 있을 삼성SDS 알고리즘 교육을 대비하여 시간이 날때마다 하루 1~2문제씩 풀고있다. 이 문제는 삼성SW역량테스트 기출문제이다. 예전에도 한번 풀려고 했던적이 있는데 그땐 뭣모르고 DFS로만 풀어야하는 줄 알아 이리저리 머리 굴려보다 포기했던 문제다. 시간이 지나고 다시 문제를 천천히 읽어보니 굳이 DFS를 사용하지 않고도 구현을 할 수 있을것같아 시도했다. 푸는데는 1시간정도 걸린거같다. 일단 조건들은 문제에 친절히 설명이 되어있다. 따라서 설명에 맞게만 구현해주면 된다. 다만 방향을 바꾸는 부분, 후진하는 부분에 조금 헷갈리는게 있어 그 부분에서 시간을 꽤 잡아먹었다. 방향을 바꾸는것과 후진하는것은 %연산을통해 하도록했고, cnt변수를 통해 네 방향을 모두 탐..

[BOJ 1963(G5) 리뷰] 네자리의 소수로 된 비밀번호를 다른 네자리의 소수로 바꾸려고 한다. 그러나 바꿀때는 한 자리씩 밖에 변경할 수 없고 한자리씩 바꾸었을때의 네자리 역시 소수여야 한다. 기존 비밀번호와 바꾸고자 하는 비밀번호가 주어질때 원하는 비밀번호까지 최소 몇번의 단계를 거쳐야 하는지 출력해야 하는 문제이다. 우리는 원하는 비밀번호까지의 최소 단계를 구해야 하므로 BFS로 접근해야 한다. BFS를 수행하기 전에 소수 확인 작업을 O(1)에 처리하기 위하여 먼저 1000~9999의 숫자에 대해 소수판별 작업을 거쳤다.그 후에 현재 비밀번호의 첫번재 자리부터 네번째 자리까지에 0~9의 수를 넣어보고 넣어봤을때의 숫자가 소수라면 큐에 넣고 이어서 탐색하도록 하면 된다. 처음엔 코드가 비효율적이..

[BOJ 1202(G2) 리뷰] 상덕이에게는 가방이 K개가 있고 가방마다 담을 수 있는 무게가 다르다. 보석점에는 보석이 N개가 있고, 보석의 무게와 가격이 주어진다. 상덕이가 최대한 가격이 높은 보석들을 훔치려면 어떻게 해야 할까? 보석가격의 합이 최대가 되게하려면 다음과 같은 조건을 만족해야 한다. 가지고 있는 가방 K개를 다 사용해야 한다. 가방에 담을 수 있는 보석의 무게 중 가장 가격이 높은것을 훔쳐야 한다. 위와 같은 조건을 만족하며 보석을 훔치기 위해서는 먼저 가방의 무게를 오름차순으로 정렬해야 한다. 왜냐하면 가방에 담을 수 있는 무게가 높음에도 낮은 무게의 보석을 훔치게되면 낮은 무게를 담을 수 있는 가방이 가격이 높은 보석을 훔칠 수 없는 가능성이 생기기 때문이다. 예를들어 가방에 담을..

[BOJ 1700(G2) 리뷰] 처음에 문제를 보고 '골드2 문제치고는 쉽네..?' 했지만 실제 구현하는 부분에서 엄청나게 애를 먹었다. 머리론 어떻게 하면 답이 나올지 알겠는데 그걸 코드로 옮기는 과정이 조금 복잡했다. 알고리즘은 그리디 알고리즘이다. 항상 최선의 선택을 해야 한다. 멀티탭이 비어있다면 비어있는 공간에 먼저 꼽아야 한다. 이미 해당 작업이 멀티탭에 꼽혀 있다면 그냥 사용하면 된다. 멀티탭은 꽉차있고 새로운 작업을 해야 할때는 가장 나중에 사용되는 작업의 코드를 뽑아야 한다. 위 세가지의 규칙을 만족하며 진행시키면 코드를 빼는 작업을 가장 최소로 만들 수 있다. 내가 애를 먹었던 부분은 가장 나중에 사용되는 작업을 고르는 과정이였다. set도 사용해보고, 배열하나 더 만들어서 해보고 별의..

[BOJ 1744(G4) 리뷰] 이 문제도 조건을 살펴보면 그리디 문제임을 알 수 있다. 엄밀한 증명은 못하겠지만, 우리는 수의 합이 최대가 나오도록 묶어야 한다는 점을 기억하자. 따라서 우리는 다음과 같은 조건을 항상 만족하게 해야 한다. 양수는 양수끼리 곱해야 한다. 음수는 음수끼리 곱해야 한다. 양수 중 최대한 큰 값 끼리 묶어야 한다. 음수 중 최대한 작은 값 끼리 묶어야 한다. 0은 음수랑만 곱해야 한다. -1,2,1,3 이라는 값이 존재할때 어떻게 묶어야 합이 최대가 나오게 할 수 있을까? 위 조건을 만족시킨다면 -1 + 1 + (2*3) 일때 최대값이 된다. 따라서 나는 입력을 받을때 음수의 값과 양수의 값을 구별하여 우선순위 큐를 통하여 정렬하여 저장했다. 그후 음수의 값은 가장 작은 값끼..

[BOJ 2457(G4) 리뷰] 전형적인 그리디 문제라지만 나에겐 너무 어려웠다 ㅠ.. 날짜를 저장하는 방식과 꽃을 선택하는 방식에 대해 이해는 했지만 막상 코드로 짜려니 막막했다. 알고리즘은 다음과 같다. 현재 날짜를 기준으로 현재 일보다 이전에 핀 꽃들중 가장 오랫동안 피는 꽃을 선택해야 한다. 공주는 3월1일부터 꽃이 피어있어야 한다 했으므로 3월1일을 기준으로 3월1일 이전에 핀 꽃들 중 가장 오랫동안 피는 꽃을 선택하면 된다. 예를들어 3월1일부터 6월3일까지 핀다면 다음 꽃은 6월3일 이전에 피는 꽃 중 가장 오랫동안 피는 꽃을 선택해야 한다. 위 알고리즘으로 11월 30일까지 꽃이 피어있도록 하고, 11월 30일이 지나면 반복문을 종료하고 정답을 출력하면 된다. 말로 설명하면 쉽지만 경계조건..

[BOJ 2096(G4) 리뷰] 전형적인 DP문제처럼 보였으나 메모리 제한이 걸려있다. 가장 쉽게 풀기 위해서는 DP[3][100001]을 선언하며 각 위치에 대해 DP계산을 해주면 되지만 이렇게 하면 불필요한 메모리 공간때문에 메모리 초과를 맞게 된다. 따라서 우리는 계산 후 불필요한 데이터는 굳이 메모리에 저장하지 않도록 해야 한다. 그러기 위해서 입력받는 순간 MAX DP, MIN DP값을 계산하며 단계를 거듭할때마다 값을 복사하여 한정된 메모리를 통하여 DP계산이 가능하게 했다. 결국 실질적으로 사용하는 메모리는 MAXDP[2][3], MINDP[2][3]이 된다. /* 20.09.01 BOJ : 2096 내려가기 (https://www.acmicpc.net/problem/2096) 다이나믹 프로..

[BOJ 1937(G3) 리뷰] 이 문제는 내리막 길 문제와 굉장히 유사하다. 언뜻 보기에는 단순한 BFS,DFS문제로 보이지만 만약 모든 경우에 대해 탐색하려 한다면 당연히 시간초과가 날 것이다. 따라서 이 문제 역시 이미 팬더가 지나갔던 길에 대해서는 다시 탐색할 필요가 없게 해야 한다. 예를들어 아래와 같은 맵이 존재할때 14 9 12 10 1 11 5 4 7 15 2 13 6 13 16 8 (1,2)인 9가 존재하는 위치에서 팬더의 최대 생존일은 9->11->15 3일이다. 따라서 만약 다른 위치에서 (1,2)를 다시 방문하게 된다면 이미 그곳에서의 최대 생존일을 알고 있으므로 다시 한번 탐색을 진행하지 않아도 된다. 이를 DP배열을 통해 관리하면 된다. 위 로직을 이해 하고 코드를 본다면 바로 ..