전체 글

[백준] 2169. 로봇 조종하기 - C++

[Gold II] https://www.acmicpc.net/problem/2169 풀이 일반적인 Bottom-Up 형식으로 풀어낸 DP 문제. 아래, 오른쪽으로만 갈 수 있는 것이 아닌, 왼쪽으로도 갈 수 있기 때문에 이를 고려해줘야 했으나, "한 번 방문한 곳은 다시 방문하지 않는다" 라는 조건이 있기 때문에, 각 줄에서, 왼쪽부터 DP 배열을 갱신하고 (line 43~45), 또 오른쪽부터 다른 DP배열을 갱신한 후 (line 47~49), 둘 중 더 큰 것(최댓값)을 택하여 DP 배열을 최종적으로 갱신해주는 식으로 모든 줄을 반복하면 된다. 다만 주의할 것은, DP 배열을 초기화할 때, 음수 value값이 있으므로, 최댓값을 구하기 위해서는 0으로 초기화하지 않고, 나올 수 있는 가장 작은 값(-..

[백준] 1520. 내리막 길 - C++

[Gold III] https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 1 Bottom-Up 방식의 DP. 오른쪽 아래부터 왼쪽 위까지 채워나가는 방식으로 구현했다. 오른쪽과 아래로만 갈 수 있는 줄 알았는데, 위와 왼쪽으로도 갈 수 있어서 WA. #include #include #include #define init cin.tie(0)->ios_base::sync_with_stdio(0); typedef long long ll; using nam..

[백준] 28257. 알록달록 초콜릿 만들기 - C++

[Gold III] https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 백준 제 2회 초콜릿컵 C번 문제 대회 당일 런타임 에러로 애를 먹었던 문제다. 이분탐색할 때 vector를 사용했었는데, 큰 숫자 범위 때문에 메모리 제한을 벗어난 듯 했음. 풀이 조금의 규칙성(?)과, 이분 탐색을 이용해야 하는 문제. 우선, 첫 번째 규칙은, 각 줄에 존재하는 민트초코의 개수. 1개 0개 1개 / 2개 1개 2개 / 3개 2..

[백준] 12899. 데이터 구조 - C++

[Platinum IV] https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 풀이 1 Segment tree 응용 문제. 2042. 구간 합 구하기 나 11505. 구간 곱 구하기 와는 다르게 삭제 연산이 있어 구현이 헷갈렸다. 첫 시도는 TLE. #include #include #include #include #define initialization cin.tie(0)->ios_base::sync_with_stdi..

[백준] 16118. 달빛 여우 - C++

[Gold I] https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 풀이 1 몇 번째 step인지를 계산하며, 늑대의 경로를 다익스트라로 잘 계산하면 되겠다 싶었지만, 어느 한 그루터기에 조금 늦게 도착하는 경로가 있더라도, 다른 그루터기에 더 빨리 도착할 수 있는 경로가 될 수 있는데, 그것을 무시하므로 WA. (예제에서, 아래와 같이 계산하면, 늑대 입장에서 2로 가는 거리는 처음에 1이..

[백준] 9370. 미확인 도착지 - C++

[Gold II] https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 1 다익스트라 문제. 다익스트라로 목적지 후보까지의 최소 경로 길이(value)를 구하고, 경로를 저장한 후, 저장한 경로가 g-h를 지나는 지 확인했다. 예제는 알맞게 답이 나왔으나, 특정 목적지로 향하는, 최소 길이인 경로가 여러 개 존재한다면, 그 중 g-h를 지나는 경로가 있는 지 확인하지 않고, 하나의 경로에 대해서만 확인하여 오답이 나온 듯 하다. WA. #..

[프로그래머스] 양궁대회 - 파이썬

2022 KAKAO BLIND RECRUITMENT - 92342. 양궁대회 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음 보았을 때는, Greedy하게 접근해야 할 지, DP로 접근해야 할 지.. 고민이였으나, 정확성 테스트로 제한 시간이 10초, 성능 테스트가 없었으며, 배열의 길이도 11이므로 2^11 = 2048가지 정도의 경우의 수를 다 따져보아도, TLE가 나지 않을 것이라 생각. 따라서, Brute-For..

[프로그래머스] 주차 요금 계산 - 파이썬

2022 KAKAO BLIND RECRUITMENT - 92341. 주차 요금 계산 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 조건에 맞게 구현만 해주면 되는, 간단한 문제! import math def solution(fees, records): P = dict() R = dict() for record in records: time, num, state = record.split() if state == "IN": ..