개발하는 사막여우

https://www.acmicpc.net/problem/1590 1590번: 캠프가는 영식 예제 1의 경우 150분, 200분, 250분, ..., 600분에 한 대씩 버스가 출발한다. 따라서 영식이는 300분에 버스를 타면 된다. www.acmicpc.net 소스코드

https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 소스코드 풀이 ★ 이분탐색을 연습하는 중이었는데, 실버4의 난이도를 가지고 있어서 이분탐색을 활용하는 전형적인 문제라고 생각했습니다 ! 하지만 3~4번의 시간초과를 겪고 구글링 해봤는데, lower bound를 구현하여 해결하는 문제였습니다 ! 문제를 풀면서 경계값을 찾는 lower bound와 upper bound에 대해서 공부할 수 있는 기회였습니다. ★ 일반적인 이분탐..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 소스코드 풀이 ★ 중간값을 찾기 위해 2개의 리스트를 만들어줍니다. 왼쪽, 오른쪽 리스트를 만들어주는데, 왼쪽 리스트는 최대힙으로, 오른쪽 리스트는 최소힙으로 만들어줍니다 ! ★ 왼쪽 리스트를 최대힙으로 만드는 이유는 최소힙의 경우, 가장 작은 수부터 정렬되게 됩니다. 하지만 최대힙일 경우 가장 큰 수부터 정렬되기 때문에 왼쪽의 가장 큰수는 왼쪽의 나머지 수들보다 크고, 오른쪽의 ..

https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 소스코드 풀이 ★ 위와 같은 풀이방식은 1부터 n까지의 수 전체를 확인해봐야 해서 비효율적이라 통과하지 못할 줄 알았는데, 통과하더라구요 ! 알고리즘 분류가 브루트포스여서 가능한 거 같습니다 :)

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 소스코드 풀이 ★ 전형적인 BFS 문제입니다. 목표지점이라고 해서, 거기까지 가는 거리를 구하는 것이 아닌 목표지점으로부터 각각의 땅이 얼마만큼 떨어진 위치에 있는지 확인해주면 됩니다 :) ★ 거리를 측정하는 그래프인 visited 배열을 -1로 초기화 해줍니다. -1로 초기화하는 이유는 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을..

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 소스코드 풀이 ★ 문제를 처음 읽었을 때, 투 포인터를 사용하여 풀 수 있는 문제라는 것을 알고 시도하였습니다 ! 하지만 67%에서 무려 5번의 실패를 겪고 정답을 맞출 수 있었는데요, 가장 중요한 부분은 문제를 꼼꼼히 읽는 것이라고 생각합니다. ★ 문제 첫 줄을 보면 n개의 수 중 어떤 수가 다른 수 두개의 합으로 나타낼 수 있다면 그 수를 "좋다"고 합니다. 여기서 주목해야 할 부분은 어떤 수를 "다른 두 수"로 만들어야..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 소스코드 풀이 ★ 전형적인 DFS 문제입니다. 한가지 주의해야 할 점이 있다면 방문하는 정점을 출력하는 것이 아닌, 정점을 방문하는 순서 즉, 방문 순서를 출력해야 합니다 ! ★ 양방향 간선이 주어졌기 때문에 for문을 사용하여 정점에서 정점으로 이동하는 모든 경우를 확인해줍니다. ★ 정점을 방문할 때는 오름차순으로 방문해야..

https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 소스코드 풀이 ★ 문제에서 주어진 조건대로 시리얼 번호를 정렬해야 합니다. sort 안에서 lambda함수를 통해 정렬을 진행하는데, 1번 조건은 len() 함수로 시리얼번호의 길이를 비교해줍니다. ★ 2번 조건의 경우에는 내장함수로 정렬할 수 없기에 직접 확인해줘야 합니다 ! 저는 주어진 시리얼 번호를 읽으면서 자릿수의 숫자일 경우 그 합을 시리얼 번호의 마지막에 추가해줬습니다. 이를 사용..

https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 소스코드 풀이 ★ solved.ac 기준 실버5 난이도의 문제여서 쉽게 해결할 수 있을 줄 알았는데, 아니었습니다 ㅠㅠ ★ 먼저 문제에 주어진 조건에 따라 정렬하는 부분은 간단합니다 ! lambda 함수를 통해 금,은,동 순으로 내림차순 정렬을 해줬습니다. ★ 이후 찾고자 하는 나라 K의 순위를 출력해야 하는데, 공동 순위를 고려해줘야 하며 공동의 순위가 있을 경우 그 다음 ..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 소스코드 풀이 ★ 먼저 좌표 압축에 대해서 잘 이해가 안될수도 있는데, 문제에서 주어진 좌표 압축이란 만약 5,55,555,5555가 주어졌을 때, 좌표 압축을 한 결과는 각각 0,1,2,3이 되게 됩니다, 즉 가장 작은 수부터 차례대로 0,1,2, ... 가 부여되는 방식입니다 ! ★ 입력받는 수들 중, 중복이 있을 수 있기 때문에 set 자료..