코드 주유소 코드 주유소

Algorithm/Algorithm Problem

• 백준 5557번: 1학년 (Python/Java)

  Algorithm/Algorithm Problem 2022. 4. 9. 17:45

  https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 접근 점화식만 제대로 찾는다면 어렵지 않게 풀 수 있는 문제다. 예제를 통해 풀이를 생각해보자. 총 열한 개의 숫자가 주어지고, 숫자 배열은 [8, 3, 2, 4, 8, 7, 2, 4, 0, 8, 8]이다. 여기서 배열의 가장 마지막 수는 연산을 통해서 '만들어야 하는 숫자'지 실제 연산에 쓰이는 숫자가 아니다. 즉, 우리가 실제로 쓸 숫자 배열은 마지막 인덱스 숫자를 뺀 [8, 3, 2,..

  Read More
• 백준 24524번: 아름다운 문자열 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 30. 22:18

  https://www.acmicpc.net/problem/24524 24524번: 아름다운 문자열 첫째 줄과 둘째 줄에 영어 알파벳 소문자로만 이루어진 문자열 $S$와 $T$가 각각 주어진다. ($1\leq \left|S \right|\leq 10^6$, $1\leq \left|T \right|\leq 26$, $\left|T \right|\leq \left|S \right|$, $\left|S \right|$와 $\left|T \ www.acmicpc.net 접근 만들 수 있는 단어를 찾기 위해 몇 번씩이나 주어진 문자열을 반복 탐색하는 것은 비효율적이고 연산이 늘어난다. 이런 연산을 줄이기 위해 최대한 주어진 문자열 탐색을 줄이도록 하겠다. 이번 풀이에서는 문자열을 딱 한번 탐색할 것이다. 그만큼 아..

  Read More
• 백준 6068번: 시간 관리하기 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 28. 22:33

  https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1= 0){ System.out.println(thisTime); }else{ System.out.println(-1); } } } 후기 포스팅하며 풀이과정을 살펴보다가 생각난 건데, 사실 위 코드에는 굉장히 쓸데없는 정렬이 들어가 있다. 사실 정렬은 '끝내야 하는 시간의 내림차순'으로만 정렬하면 된다. 근데 위 코드에선 끝내야 하는 시간이 같다면 걸리는 시간을 기준으로 다시 내림차순을 해줬다. 전혀 필요 없는 연산이다. 정렬하면 뭐할 거냐, 1+2나 2+1이나 같은 건데 굳이 정렬을...? 왜 그랬냐 물어본다면, 어....

  Read More
• 백준 17828번: 문자열 화폐 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 27. 13:53

  https://www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 접근 사전 순으로 가장 빠른 문자열을 구하라는 말은 A부터 Z까지 순서대로 문자가 들어가야 한다는 뜻이다. 하지만 문자열 길이는 정해져 있고, 가장 처음에 A 하나 넣고 그 뒤에 조합될 수 있는 모든 경우의 수를 비교하기에는 연산이 비상식적으로 늘어날 것이 분명하다. 때문에 조금 더 과감해졌다. 모든 문자열을 A로 채워 넣었다. 예시를 살펴보자. 만일 길이가 5인 문자열을 통해 가치를 7로 만들어야 한다고 생각해보..

  Read More
• 백준 11497번: 통나무 건너뛰기 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 22. 23:22

  https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 접근 반복 for문을 돌려서 매번 두 수의 차를 구하고 최댓값을 구한 뒤 배열에 집어넣으면 무조건 시간 초과가 날 수밖에 없는 문제. 때문에 수들을 정렬시킬 규칙을 찾아야 한다. 사실 이 부분에서 조금 헷갈리긴 했으나 잘 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 우선 숫자들을 순서대로 정렬한다. 그 뒤 첫 번째에 가장 작은 수, 마지막에 다음 수, 두 번째에 다음 수, 뒤에서 두 번째에 다..

  Read More
• 백준 2036번: 수열의 점수 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 21. 23:23

  https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net 접근 그리디 알고리즘의 기본 원리만 생각하며 원론적으로 접근해봤다. '배열에서 가장 큰 숫자를 만들어 더하는 것'이 현재 단계에서 해야 하는 최선의 선택이다. 이 부분을 구현하기 위해 우선 두 가지 경우로 나눠서 생각해봤다. 첫 번째는 홀수인 경우다. 홀수인 경우는 무조건 두 개를 곱해야 최종 값이 가장 큰 값이 나온다. 홀수 숫자의 개수가 홀수개인 경우에는 두 개씩 곱하다가 마지막 홀수를 더해야..

  Read More
• 백준 17267번: 상남자 (Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 12. 19:32

  https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하 www.acmicpc.net 접근 간단한 너비 우선 탐색 알고리즘처럼 보이지만, 좌우 이동 횟수 제한 조건에 의해 굉장히 까다로워진 문제. 구현 자체는 어렵지 않으니, 우선 평소와 같이 현재 좌표에서 상하좌우 이동해 Queue에 넣고, 다시 Queue에서 값 하나 꺼내 또 상하좌우 이동하고... 이런 방식으로 구현한다고 생각해보자. 물론 좌우 이동 횟수도 꼭 체크를 해줘야겠지? 이렇게 풀면 너무 간단하게 예제 답을 구할 수 있다...

  Read More
• 백준 9019번: DSLR(Python/Java)

  Algorithm/Algorithm Problem 2022. 3. 11. 00:39

  https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 접근 구현만 차근히 잘 해낸다면 어렵지 않게 풀 수 있는 너비 우선 탐색 문제. 때문에 굳이 풀이 방법을 포스팅할 필요가 있나 싶지만, 구현 방식에서 재밌는 아이디어가 있어 기록해놓기 위해 풀이를 작성한다. 문제에서 주어진 네 가지 명령 중, D와 S는 굉장히 쉽게 구현할 수 있다. D는 그냥 현재 값을 두배 한 다음에 10000으로 나눈 나머지를 가져가면 된다. '결과 값이 9999..

  Read More