Jonyo Programming

[BOJ1946 리뷰] 오랜만에 푼 그리디 문제이다. 문제 조건을 잘 풀어보면 다음과 같다. 신입사원으로 선발 되려면 다른 지원자보다 최소한 점수 하나가 더 높아야 한다. 즉, 점수가 둘다 낮으면 선발될 수 없다. 문제를 해결하기 위해서 먼저 첫번째 기준으로 정렬을 하자. (두번째 기준으로 정렬을 해도 상관이 없다.) 정렬이 되면 서류성적순으로 1등부터 꼴등까지 쭉 정렬이 될 것이다. 이제 여기서 문제의 핵심을 잘 생각해보면 된다. 신입사원으로 선발이 되기 위해서는 최소한 점수 하나가 더 높아야 한다. 지금은 서류성적 순으로 정렬이 되어있기 때문에, 그 밑에 있는 사원들은 일단 서류성적은 첫번째 지원자보다 무조건 낮을 수 밖에 없다. 그렇기에 이 사람이 선발이 되기 위해서는 면접 점수가 무조건 높아야 한..

[BOJ 13908(G5)리뷰] 오랜만에 브루트포스 문제를 풀었다. 숫자는 0~9까지의 수이므로 총 10개이고, 최대 비밀번호의 길이가 7이므로 O(10^7)의 연산으로 모든 경우를 탐색할 수 있다. 1천만 정도 되는 연산량 이므로 1초내에 충분히 계산이 가능하다. 백트래킹으로 코드를 짰으며 따로 값들을 저장하지 않고 숫자 사용여부만 체크해주면서 올라가면 된다. 결국 길이가 n이 되었을때 반드시 들어가야 하는 숫자들이 사용되었는지 확인하고 다 사용되었다면 정답의 갯수를 늘려주면 된다. /* 21.02.08 BOJ : 13908 비밀번호 (https://www.acmicpc.net/problem/13908) 백트래킹/브루트포스 */ #include using namespace std; int n, m; i..

[BOJ 2660(G5)리뷰] 주어진 관계를 이용해 BFS를 수행해 DEPTH를 기록하여 해결할 수 있는 문제다. 플로이드 문제를 풀려고 봤는데 BFS로 푸는게 더 간단할 것 같아 BFS로 풀었다. 주의해야 할 조건은 회원 사이에 친구를 통해서 모든 회원을 알 수 있다는 점이다. 즉, 각각의 회원은 자신을 제외한 모든 회원간의 DEPTH가 반드시 존재한다. 따라서 BFS를 돌며 각 회원간의 DEPTH를 기록하면 된다. 점수가 1점이라는 의미는 모든 회원간의 DEPTH가 1이라는 의미이고, 점수가 2점이라는 의미는 모든 회원 중 최대 깊이의 DEPTH가 2라는 의미이다. 그래서 나는 크게 '1. BFS를통해 회원간 DEPTH계산, 2.각 사람별 최대 DEPTH를 통한 점수계산 3.점수 중 최소값 계산하여 ..

[BOJ 1956(G4)리뷰] 문제를 요약하면 사이클이 있는 경로 중 최단경로를 찾으면 된다. 시작점과 도착점을 특정한 상태에서 최단거리를 구할 수 없으므로, 플로이드-와샬 알고리즘을 통해 모든 노드 간의 최단거리를 구한다. 알고리즘을 수행한 후에 dist[i][j]는 i노드에서 j노드까지의 최단거리가 된다. 문제에서 사이클이 존재해야 한다고 했으므로 dist[i][j]와 dist[j][i]가 모두 존재해야 한다. 즉, 'i번 노드에서 j번노드까지의 최단거리 + j번 노드에서 i번 노드까지의 최단거리' 중 가장 작은값이 정답이 될 것이다. /* 21.02.05 BOJ : 1956 운동 (https://www.acmicpc.net/problem/1956) 플로이드-와샬 알고리즘 */ #include usi..

[BOJ 1865(G4)리뷰] 벨만포드 알고리즘을 이용하는 문제다. 시간이 되돌아 가는것 = 음의 가중치를 갖는 간선이라고 생각하면 된다. 도로는 양방향으로 이동이 가능하므로 양방향으로 입력을 받고, 웜홀은 단방향이므로 단방향으로 입력을 받는다. 그 후에 벨만포드 알고리즘을 수행하며 사이클이 있는지 확인하여 결과를 출력하면 된다. 나는 이 문제에서 두가지 실수를 했다. 첫째는 MAX값을 INT_MAX값으로 설정하여 거리를 갱신하는 부분에 오버플로우가 나 올바른 결과가 나오지 않았다. 둘째는 방문했던 적이 있던 정점에 대해서만 거리를 갱신하는 작업을 수행했었는데, 만약 시작노드가 다른 노드와 연결되어 있지 않은 노드라면, 나머지 노드는 거리를 갱신할 수 없게된다. 따라서 이 조건을 없애야 한다. 위 두가지..

[BOJ 10282(G4) 리뷰] 단순히 몇대의 컴퓨터가 감염되는지 구하는 문제가 아닌, 감염이 가능한 모든 컴퓨터가 감염되는 최단 시간을 구해야 한다. 그러므로 이 문제를 해결하기 위해서는 다익스트라 알고리즘을 사용해야 한다. 시작 컴퓨터가 주어졌으니 시작컴퓨터로부터 다익스트라 알고리즘을 수행한다. 그 후에 시간이 기록된 DIST배열 전체를 확인하여, 거리가 갱신된 노드들이 감염된 컴퓨터의 숫자가 된다. 그리고 감염이 되는 시간은 항상 0보다크므로 DIST배열중 가장 큰 값이 모든 컴퓨터가 감염되는 최단경로가 될 것이다. /* 21.02.02 BOJ : 10282 해킹 (https://www.acmicpc.net/problem/10282) 다익스트라 알고리즘 */ #include using namesp..

[BOJ 1854(P5) 리뷰] 다익스트라 알고리즘 + 우선순위 큐를 이용하여 풀었다. 다익스트라 알고리즘을 통해 1번노드부터 N번노드까지의 최단경로를 구할 수 있다. 이때, 최단경로만 저장하는 것이 아니라 가능한 모든 경로를 저장하면 된다. K번째 최단경로를 찾기위해 정렬된 모든 경로중 K번째에 있는 값을 출력하면 될것이라 생각했지만 그렇지 않았다. 가능한 모든 경로를 담을 수가 없기에 필요한 경로들만 담아야 한다. 이때 우선순위큐가 필요하다. 우선순위 큐를 내림차순으로 정렬한다면 큐의 SIZE가 K일때 큐의 TOP에 있는 값이 K번째로 큰값이라는것을 알 수 있다. 이 원리를 이용하면 된다. 새로운 경로가 계산될때마다 큐의 사이즈를 확인하여 큐에 넣는작업을한다. 큐의 사이즈가 K보다 작다면, 아직 K번..

[BOJ 1747(G5)리뷰] N을 입력받아 N보다 크거나 같은 소수 중 팰린드롬인 수를 출력하면 된다. 예를들어 31을 입력받았다면, 31보다 큰 소수중 팰린드롬인 수 101을 출력하면 된다. 이 문제를 풀기위해 크게 두가지 과정을 거쳤다. 1.소수 판별 (에라토스테네스의 체) 2.팰린드롬 판별 처음에 N의 범위가 최대 100만이라 100만까지의 수만 소수판별을 했는데 만약 100만이 입력되었을 경우 100만보다 크거나 같은 소수를 출력해야하므로, 100만보다 크거나 같은 소수 중 팰린드롬 수인 1003001까지 소수판별을 해야 한다. 1003001까지의 소수판별을 한 후에 소수들을 하나의 벡터에 넣고, 입력받은 N의 위치를 lower_bound로 구했다. 이러면 N에서 가장 가까운 소수의 위치를 알 ..

[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; } } 내가봐도..