Algorithm

[백준] 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": ..

[프로그래머스] 코딩 테스트 공부 - 파이썬

2022 KAKAO TECH INTERNSHIP - 118668. 코딩 테스트 공부 [Lv. 3] https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 보자마자.. DP로 접근해야 될 것 같은 문제라고 생각했다. [백준] 2342. Dance Dance Revolution - 파이썬 과 비슷한 느낌으로, Bottom-Up으로 풀면 된다. dp[alp][cop] => 특정 alp, cop를 달성하기 위한 최소 시간(cost) def soluti..

[프로그래머스] 두 큐 합 같게 만들기 - 파이썬

2022 KAKAO TECH INTERNSHIP - 118667. 두 큐 합 같게 만들기 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 deque를 이용해 greedy하게 풀이하면 되었던 문제. 주의할 점은, 반복문 안에서 sum() 을 이용하면, TLE가 날 수 있다는 것! from collections import deque def solution(queue1, queue2): queue1 = deque(queue1)..