devlog

출처: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B구하는 거 보단 B->A로 구해야겠다고 생각했다. 하지만 예제 정답 부분만 보고 짝수이면 나누기 2 홀수이면 -1 후 나누기 10을 했다. 예시 부분은 다 정답처리가 되었지만 1 25같은 수가 입력된다면 제대로 해결하지 못할 것이다. 그래서 10으로 나누었을 때 나머지가 1인 경우, 2로 나누었을 때 나머지가 1인 경우 다른 경우는 실패 이렇게 3가지 경우로 나누게 되었다. A, ..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 기존 bfs 문제와 다른 점은 board를 벗어나거나 벽에 부딪힐 때까지 한 방향으로 쭉 이동하는 것을 한 번 이동했다고 카운트하는 점이다. 하지만 기존의 bfs를 조금 변형해서 풀 수 있었다. 현재 위치에서 move 함수를 이용해서 다음 위치점을 찾아야 했다. move 함수의 인자로 현재 위치, 이동 방향을 나타내는 인덱스 i를 넘겨주었다. 그 후 while 루프를 통해 벽..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 처음엔 문제를 x축으로 나누어서 진행했다. 같은 x축일 때 까진 visited 배열을 초기화하지 않고 진행했고 x축이 증가할 때마다 visited 방문 배열을 초기화해주었다. 이렇게 하니 효율성 문제가 발생했다. 그래서 다른 분들의 풀이 방법을 참고하니 정사영이라는 알고리즘을 사용하는 것을 볼 수 있었다. 먼저 x축에 따른 추출 가능한 석유량을 count하는 배열 result..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/250137 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 단순 구현문제이다 현재 시간에서 다음 공격 시간으로 바로 이동했다. 그런 후 공격 데이미를 입기 전에 얻는 회복량을 계산하고 데이미를 주었다. 그런 다음 현재 시간을 최근에 받은 공격 시간으로 이동했다. def solution(bandage, health, attacks): max_health = health health_time = 0 now_t = 0 last_time =..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118668# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 처음에는 그리디 하게 풀 수 있는 방법이 있나 생각해 봤는데 복잡할 거 같아서 dp로 풀어야겠다고 생각했다. dp로 풀기 위해 중복되는 계산이 뭔지 생각해 봐야 한다. 이차원 배열로 dp[알고력][코딩력] = cost 알고력과 코딩력을 가지는데 필요한 최소 시간으로 설정했다. dp배열을 모든 문제를 푸는데 필요한 최대 알고력과 코딩력의 크기로 int max값으로 초기화했다...

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 처음에는 두 큐의 합이 같게 만드는 알고리즘이 있을까 생각해 봤는데 떠오르지 않았다. 그래서 그냥 완전 탐색으로 합이 작은 쪽에서 큰 쪽으로 원소를 이동해 가며 특정 횟수가 넘으면 return -1 하게 풀어야겠다고 생각했다. 처음에는 sum 메서드를 활용해서 매번 loop마다 합을 구해서 비교했는데 이러면 sum 메서드 때문에 시간 초과 된다. 그래서 변수 total1, t..

출처 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 방법 가로로도 세로로도 붙어 있으면 안되기 때문에 경우의 수를 3가지로 나누었다. dp_l[i] = i 번째 줄에 왼쪽에 사자가 있고 오른엔 사자가 없는 경우 dp_r[i] = i 번째 줄에 오른쪽에 사자가 있고 왼쪽엔 사자가 없는 경우 dp_z[i] = i 번째 줄에 왼쪽 오른쪽 둘다 사자가 없는 경우 점화식 은 dp_l[i] = dp_z[i] + dp_r[i]; dp_r[i] = dp_z[i] + dp_l[i]; dp_z[i] = dp_z[i] + dp_l[i] + dp_r[i] 로 포현하면 가로로 세로로 붙어 ..

출처 : 3184번: 양 (acmicpc.net) 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 방법 조건 몇 가지만 추가해서 bfs로 풀이할 수 있다. board전체를 for 문을 통해 돌며 #이 아니며 방문한 적이 없다면 bfs를 호출 한다. board[y][x]가 양이면 sheep변수에 +1 board[y][x]가 늑대이면 wolf변수에 +1을 해주고 bfs가 종료되기 전에 sheep의 변수 값이 큰지 wolf의 변수 값이 큰지 비교해서 sheep이 크면 n_sheep(전체 양이 몇 ..

출처 : https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 방법 동적 계획법으로 재귀 함수를 사용해 해결했다. 재귀 함수의 기저 조건으로 1. y, x 좌표가 모두 0이면 return board[0][0] 2. y, x 좌표가 범위를 넘어가면 return 0 을 해서 선택되지 않도록 설정 3. dp[y][x] 가 -1 이 아닌 다른 값으로 설정되어 있으면 그 값을 리턴 3가지를 설정 했다. 위 3가지가 아닌 경우 재귀 함수를 ..

출처 : 1926번: 그림 (acmicpc.net) 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 방법 bfs 문제로 맵 전체를 for 문을 돌며 board[y][x] 가 1이고 visited[y][x]가 -1 인 점을 bfs(y, x)를 호출하여 그 점과 연결된 점들을 방문하여 넓이를 구하고 가장 큰 곳이면 답을 변수 ans에 저장한다. 그리고 bfs가 호출 될 때마다 그림의 개수 카운터를 증가시킨 후 출력한다. #include using namespace std; int n, m, ans = 0, cnt..