Algorithm 70

[백준] 수들의 합 2 2003번 (python)

출처 : https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 방법 투 포인터 문제를 연습할 겸 문제를 풀어 보았다. 이중 for문으로 풀면 시간초과가 난다. 투 포인터란 배열을 순회하는 하나의 방법으로 포인터를 2개를 사용해서 순회하는 방법이다. 왼쪽 포인터와 오른쪽 포인터를 두고 풀어보자 왼쪽 포인터부터 오른쪽 포인터까지 합을 리턴하는 함수를 작성한다. 이때 배열의 합에 따라 케이스를 분리하자 배열의..

Algorithm 2024.03.24

[백준] A->B 16953번 (python)

출처: 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, ..

Algorithm 2024.03.22

[프로그래머스] 리코쳇 로봇 (python)

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

Algorithm 2024.03.20

[프로그래머스] 석유 시추 (python)

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

Algorithm 2024.03.19

[프로그래머스] 붕대 감기 (python)

출처 : 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 =..

Algorithm 2024.03.13

[프로그래머스] 코딩 테스트 공부 (python)

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

Algorithm 2024.02.03

[프로그래머스] 두 큐 합 같게 만들기 (python)

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

Algorithm 2024.01.03

[백준] 동물원 1309번 (c++)

출처 : 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] 로 포현하면 가로로 세로로 붙어 ..

Algorithm 2022.11.23

[백준] 양 3184번 (c++)

출처 : 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(전체 양이 몇 ..

Algorithm 2022.11.02

[백준] 이동하기 11048번 (c++)

출처 : 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가지가 아닌 경우 재귀 함수를 ..

Algorithm 2022.10.06