Jonyo Programming

[BOJ 17837(G2) 리뷰] 2차원 벡터를 이용해 풀었다. 조건에 주어진 대로 구현하면 된다. 다만 이동하려는 곳이 파란색이거나 범위를 벗어날 경우 방향을 바꿔주는 작업을 좀 신경써야 한다. 말들이 이동하는 방법은 가장 간단한 방법을 사용했다. 이동하기전에 현재 위치에 있는 말들을 탐색하면서 남아있어야 할 말들과 이동해야 할 말들을 각각의 벡터에 넣은 후, 이동시키면 된다. 만약 이동하고자 하는곳이 빨간색이라고 하면 이동해야 할 말들을 넣은 벡터만 reverse해주면 된다. 방향을 바꾸는 작업은 방향을 바꾼후에 다시 한 칸을 이동해야 한다는 조건때문에, 방향을 바꾸고 반복문 i의 값을 감소시켜 한번 더 반복문을 돌게 했다. 이때 이미 한번 방향을 바꾼적 이 있다면 그대로 움직이지 말아야 한다. 구현..

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

[BOJ 16235(G4) 리뷰] 2021년에 푸는 첫 문제이다..! 문제를 보면 알겠지만 조건에 대한 설명이 아주 친절하게 나와 있다. 그렇기에 문제에서 주어진대로만 구현을 하면 될것같았다. 각 계절마다 함수를 만들어 벡터와 배열을 이용하여 구현하고, 테스트케이스도 다 맞길래 기분좋게 제출을 했다. 하지만 역시.. 이렇게 쉽게 풀릴 문제는 아니였다. 제출하자마자 시간초과가 떴다. 시간초과의 원인이 뭔지 분석을 해봤다. 일단 첫번째 문제로는 봄에 죽은 나무들을 별도의 벡터에 저장을하고, 여름 함수를 만들어서 여름함수에 양분을 추가하는 작업을 했는데 이 작업이 매우 비효율적으로 보였다. 두번째는 나이가 어린 나무부터 양분을 먹기위한 조건을 만족하기 위해 1년이 지날때마다 현재의 나무들을 오름차순으로 정렬했..

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

[BOJ 14890(G3) 리뷰] 삼성 SW역량테스트 기출문제다. 요즘 하나씩 풀고있다. 이 문제도 예전에 풀다가 포기했던 문제인데 지금 풀리는걸 보니 실력이 늘고있긴 한가보다. 신기하다. 문제 조건은 다음과 같다. 길을 건너기 위해서는 칸의 높이가 같아야 한다. 높이가 다를때는 경사로를 놓아 길을 지날 수 있다. 경사로의 높이는 1로 고정되어 있다. 경사로는 입력받은 L의 길이만큼 놓을 수 있다. 이것보다 적게,크게 놓을 수 없다. 경사로가 겹치면 안된다 나는 문제를 풀기위하여 천천히 하나하나씩 시뮬레이션하며 경우의 수를 생각해보았다. 일단은 2N만큼의 길을 탐색해야 하므로, 행 우선 탐색을 수행 한 후에 동일한 코드에 행과 열의 위치만 바꿔 열 우선 탐색을 수행 했다. 그리고 값을 하나 하나씩 비교한..

[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) 일때 최대값이 된다. 따라서 나는 입력을 받을때 음수의 값과 양수의 값을 구별하여 우선순위 큐를 통하여 정렬하여 저장했다. 그후 음수의 값은 가장 작은 값끼..