개발하는 리프터 꽃게맨입니다.

1. 아이디어1) 음의 가중치가 존재하고, 문제 자체가 음의 사이클 또한 염두하고 있기 때문에 해당 문제는 벨만-포드 알고리즘을 사용하는 것이라고 볼 수 있습니다. 2) 즉, 1번 노드에서 출발하여 그래프에 대해서 최단 거리를 갱신한 뒤 문제의 요구에 맞게 출력을 하면 되겠습니다. 3) 음의 사이클을 분별하는 방법은벨만 포드 알고리즘의 결과 dist 배열과벨만 포드 루프를 1번 더 돌린 dist 배열이 다를경우 음의 사이클 이라고 판단할 수 있습니다.2. 주의할 점1) 가중치의 경우의 수가 int 오버플로를 발생시킬 수 있기 떄문에 long long 이나 __int64를 사용해야 합니다.2) 1번 노드에서 그 어떤 노드로 간선이 존재하지 않는 경우에는 그래프에 음의 사이클이 존재하던 말던,-1 을 N-1..

https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 아이디어 우선순위 큐를 이용한 스케줄링 문제입니다. 큰 아이디어는 이렇습니다. 1) 작업의 길이가 짧은 것을 먼저 해야한다. 2) 1)을 만족해도 요청되는 작업만 수행해야한다. 즉, 이 2가지를 고려해서 해결해야합니다. 풀이이 먼저 1) 이전에 2를 해결하기 위해 jobs를 실행시간 기준으로 오름차순 정렬해줍니다. 그러면 일단 2)를 해결했고, 다음은 1)을 해결해야하는데 현재 jobs 배열..

https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 1. 아이디어 첫 번째로 떠올린 아이디어는 '시뮬레이션'이었습니다. 직접 시뮬레이션을 돌려서 문제를 해보고자했죠. 그래서 작성한 코드가 다음과 같습니다. 말그대로 방향을 바꿔가면서 움직여보는 것이였죠. 시간 제한이 0.15초 이고, t가 한 없이 커도 w*h 를 간격으로 똑같은 패턴을 보이기 때문에 나머지를 통해 for문을 돌리면 시간초과가 나오지 않을 것이라 생각했습니다. 하지..

https://www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 아이디어 처음에는 그리디 알고리즘 문제인줄 알고 deque를 이용해서 현재 최고 가치를 가지는 카드를 뽑는 방식을 로직을 사용했는데, 최선의 전략으로 게임이 끝났을 때, 최고 점수를 얻어야 하는 것이더라구요. 그러면 현재 최선의 선택잉 미래에는 최선이 아닐 수 있습니다. 이럴 때는 다이나믹 프로그래밍을 사용해야죠! dp[i][j] 는 i번째 카드 ~ j번째 카드가 있을 때, 근우의 최대 점수를 뜻합니..

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 1. 문제 2. 아이디어 이 문제는 기본적으로 스위핑 알고리즘을 사용해서 풀이합니다. 스위핑 알고리즘은 뜻 그대로 휩쓸고 지나가며 문제를 해결하는 방식으로, 특정 기준에 따라 정렬한 후 순서대로 처리하는 알고리즘입니다. 그러므로 스위핑 알고리즘의 복잡도는 O(N log N + N) = O(N log N) 의 복잡도를 가집니다. 즉, 이 문제는 선..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 아이디어 BFS 문제의 대표격 중 하나인 미로찾기 문제입니다. 그러나 시간 제한이 1초이기 때문에 O(N^2) 인 BFS로는 풀 수 없고, O(N logN) 인 다익스트라 알고리즘을 이용해서 풀어야만 합니다. 맨 좌측 상단에서 시작해서 맨 우측 하단까지 어떻게 도달할 것인가? 에 대한 문제이고 1은 벽인데 필요하다면 벽을 부술수도 있습니다. 단, 벽을 최대한 적게 부수면..

1. 문제 https://www.acmicpc.net/problem/17070 2. 아이디어 다이나믹 프로그래밍으로 풀 수 있는 문제일 것 같다. 특정 좌표를 (y, x) 라고 했을 때 파이프의 우측 좌표를 기준으로 (좌측 좌표는 생각할 필요 없다.) (y, x) 에 가로로 도착할 횟수 + (y, x) 에 세로로 도착할 횟수 + (y, x) 에 대각선으로 도착할 횟수 의 합을 구하면, 해당 좌표에 도달할 수 있는 모든 경우의 수가 된다. 이 때, 벽에 막힐수도 있기에 예외처리에 신경쓴다. 3. 풀이 먼저 전역변수 목록이다. tableSize는 격자의 크기 table은 격자의 정보를 입력하는 부분 dpRight, dpDown, dpRD 는 각각 특정 좌표에 가로로 도착하는 경우, 세로로 도착하는 경우, 대..

참고: https://powerclabman.tistory.com/13 [C++/알고리즘] 퀵 정렬 (Quick Sort) 참고: https://powerclabman.tistory.com/12 [C++/알고리즘] 분할정복 (Divide and Conquer) + 병합정렬 (Merge Sort) 📕 개요 '분할 정복 알고리즘'이란, 엄청나게 크고 방대한 문제를 해결할 수 있는 단위까지 쪼개서 powerclabman.tistory.com 이번 글은 퀵정렬을 모르면 이해하기 힘듭니다. 📕 문제 N 사이즈의 정수배열 arr 이 존재할 때 배열 arr에서 k번 째로 작은 수를 선택해라 예시) N = 7 arr = {5, 9, 3, 7, 11, 2, 0} k = 4 일 때, 결과값은 5 설명) arr을 오름차순 ..

참고: https://powerclabman.tistory.com/4 [C++] Bitwise Operator와 빠른 홀수, 짝수 찾기 📕 비트 연산자의 개념 비트 연산은 '2진수' 연산을 뜻하는데, 특정 연산자를 이용해서 이진 수로 표현된 정수에 대하여 논리적인 연산을 수행합니다. 2진수 연산은 10진수 연산에 익숙한 사람에 powerclabman.tistory.com 📕 해밍 거리란? 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지 세는 것을 뜻합니다. 두 문자열 A, B가 다음과 같을 경우 A = 1011 B = 1001 밑줄 친 부분을 고려하면, 해밍 거리는 1이 되겠죠 A = Hello! B = Halro! 이 경우에는 해밍 거리는 2가 됩니다. 저는 '비트 연산'을 활..