Jonyo Programming

[BOJ 20057(G4)리뷰] 지난번 풀었던 마법사 상어와 파이어볼의 후속(?) 문제인 것 같다. 이 문제 역시 시뮬레이션 문제이며 문제에 주어진 조건들을 구현하면 된다. 크게 생각해야 할 부분은 '1. 토네이도가 이동하는 부분, 2. 모래가 이동하는 부분' 이다. 토네이도의 이동을 어떻게 구현할까 고민했다. 분명 수식으로 표현되는 규칙이 있을 것 같은데 그걸 찾지는 못하겠어서 그냥 내 기준 가장 간단한 방법을 사용했다. order라는 맵과 똑같은 크기의 배열을 만들어 토네이도가 이동하는 순서를 미리 기록하는것이다. 이건 반복문을 통해 노가다로 토네이도의 이동방향에 맞게 order배열에 순서대로 채워 나갔다. 그 다음부터는 시작지점부터 시작하여 미리 구현해 놓은 토네이도의 방향대로 BFS를 수행하며 모..

[BOJ 20056(G5)리뷰] 삼성SW 역량테스트 기출문제다. 문제에 주어진 조건에 따라 천천히 시뮬레이션 하듯이 구현하면 된다. 효율적으로 풀어보려고 노력해보다 생각보다 시간이 많이 걸렸다. 문제에서 주의해야 할 부분은 N*N맵이 서로 이어져있다는것이다. 1번행에서 1칸 위로 올라가게되면 N번행이 나오고 N번열에서 1번 오른쪽으로 이동하게되면 1번 열이 나오는 식이다. 따라서 이 부분에 대한 변환식을 따로 구현했다. int getRotation(int cur) { if (cur = N) { return cur % N; } else { return cur; } } 내가봐도..

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

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

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

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

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

[BOJ 1339(G4) 리뷰] 쉬운듯 어려운 문제이다. 자리수가 가장 높은 알파벳에 최대한 높은 값을 주어야하는 그리디 문제이다. 그리디 문제이지만 이 문제는 백트래킹으로도 풀수가 있다. 알파벳의 갯수가 최대 10개 등장하니 각각의 알파벳을 9부터 0까지의 값으로 변경하여 계산하면 10!에 문제를 풀 수 있다. 그러나 나는 백트래킹말고 그리디+시뮬레이션으로 풀고싶었다. 그래서 일단 머리속에 떠오르는대로 구현을 하고 예제TC가 다 잘 나오길래 제출을 했더니 오답처리가 되었다. 예제에서 놓친 예외사항이 있었다. 처음에 구현했을땐 문자열을 입력받아 check배열을 통해 각각의 문자열의 INDEX에 자리수를 저장하고, 저장된 자리수를 우선순위큐에 담아 자리수 큰 숫자부터 높은숫자를 부여할 생각이였다. 그러나 ..

[BOJ 1966(S3) 리뷰] 시뮬레이션 문제다. 설명에 나온대로 프린터 큐가 존재하고 큐에 있는 각각의 작업마다 중요도가 있다. 큐의 맨앞 작업부터 하나씩 내보내야 하는데 만약 뒤에서 기다리고 있는 작업 중 현재의 작업보다 중요도가 높은 작업이 있다면 현재의 작업을 맨 뒤로 보내고 중요도가 높은 작업먼저 수행해야 한다. 이 때 M번 작업이 몇번만에 수행이되는지를 출력해야 한다. 가장 먼저 떠올렸던 구현은 큐가 빌때까지 반복문을 돌며 계속해서 뒤에있는 큐중 중요도가 있는작업이 있는지 확인하고 있다면 현재 큐를 뒤로 보내는 작업이다. 이 작업은 시간복잡도 O(n^2)에 수행된다. N이 100이하이므로 이 코드도 충분히 통과가 가능하지만, 나는 O(n)에 구현하기 위하여 우선순위큐를 이용했다. 우선순위큐를..

[BOJ 17140(G4) 리뷰] 풀면서 이게 시간내에 통과될까? 라는 생각을 몇번했는지 모르겠다. 구현방법은 바로 떠올랐는데 어떻게 하면 효율적으로 처리할수 있을지가 문제였다. 아무리 고민해도 더 좋은 코드가 떠오르지 않아 그냥 처음 생각한 방법대로 했는데 TC가 약해서인지 통과되었다. 이 문제는 R연산과 C연산을 통해 이루어진다. R연산을 하면 각 행마다의 숫자와 등장횟수를 오름차순으로 변경해주면 된다. 예를들어 1 1 2 라는 행이 있으면 1이 2번등장 2가 1번등장했으므로 -> 2 1 1 2 로 변경된다. 1 2 1 2 1 3 3 3 3 라는 행렬이 있으면 1 2 2 1 0 0 1 1 2 1 3 1 3 3 0 0 0 0 으로 변경된다. 가장 큰 행을 기준으로 나머지값은 0으로 채워주는 작업도 필요..