개발하는 사막여우

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 자료..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 소스코드 풀이 ★ 주사위를 던지면서 모든 경우의 수를 확인해야 하는 완전탐색 문제입니다 ! 이 때 사다리와 뱀의 정보를 이용하는 것이 중요합니다. 뱀은 높은 칸에서 낮은 칸으로 이동하기에 100으로 가기에는 필요없다고 생각할 수도 있는데, 사다리 (10 - 50), 뱀 (50-28), 사다리 (28 - 99)처럼 뱀을 이용해서도 100으로 빠르게 이동..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 소스코드 풀이 ★ 수빈이가 이동할 수 있는 경우를 다 탐색한 후, 그 이후에 가지를 쳐서 뻗어나가는 형식의 전형적인 BFS 문제인 거 같습니다 ! ★ 수빈이가 이동할 수 있는 방법은 순간이동과 걷기가 있습니다 ! 이 떄 순간이동을 하는 경우는 초가 증가하지 않지만 걷는 경우에는 초를 1씩 증가시켜줍니다. ★ BFS 안의 for문을 돌 때 순간이동을 하는 경우 ..

알고리즘을 풀다보면 시간복잡도를 해결하기 위해 자료구조로 딕셔너리를 많이 사용합니다 ! 딕셔너리는 (key, value) 형태로 이루어져있는데, 문제에 따라 어떤 값을 기준으로 정렬해야 할지 달라지게 됩니다 ! 저도 문제를 풀 때는 활용법을 알고있다가도, 뒤돌아서면 자주 까먹는 거 같아 기록해보고자 합니당 :)

https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 소스코드 풀이 ★ 알고리즘을 풀다보면 리스트를 좌우로 회전하는 문제를 많이 만날 수 있습니다. 그런 유형을 만날 때마다 일일이 구현하는 경우가 대부분이었는데, deque의 rotate함수를 사용하면 회전을 쉽게 구현할 수 있습니다! ★ rotate()함수는 인자로 양수를 넣어줄 경우 오른쪽 회전을 하게 되고, 음수를 줄 경우 왼쪽 회전을 하게 됩니다. ex) dq = deque(..

https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 소스코드 오답 정답 풀이 ★ 위 두 코드의 차이점을 쉽게 발견하셨을까요 ?? 전 사실 이문제 엄청 간단하다고 생각했는데, 2번이나 오답을 받았습니다..! 그 이유는 테스트케이스가 하나가 아닌 t만큼 들어오기 때문에 반복해줘야 하지만 아무생각 없이 제출헀기 때문입니다 ! 꼭꼭 잘 확인하시길 바랍니당 :) ★ 저는 문제를 딕셔너리 자료구조를 사용하여 풀었습니다 ! 수첩 1에 적힌 수들을 딕셔너리에 넣어주고..

https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 소스코드 풀이 ★ 문제를 읽었을 때 이해하기가 조금 난해할 순 있지만 해당 회원 번호에서 모든 회원과 친구가 되기 위해서 몇번동안 BFS 안의 과정을 거쳐야 하는지 구해주시면 됩니다 ! ★ 점수를 구하기 위해 큐에 회원번호와 점수를 기록하는 수를 함께 추가하였습니다. 이 점수는 BFS 안에서 큐에 추가되는 과정마다 다른 루트로 이동하기 때문에 1씩 증가하게 됩니다. 예시 1번에서 1,2 2,3 3..

https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 소스코드 풀이 ★ 소수점 4번째자리까지 반올림 한 뒤 출력해줘야 하는데, 이때 round 함수를 사용하면 오답으로 처리됩니다 ! 그렇기에 format이나 f-string을 사용하여 반올림 해주시면 됩니다 :)

https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 소스코드 풀이 ★ 보통은 상하좌우 or 대각선까지 고려하여 움직이는 경우가 많은데, 이번 문제에서는 주어진 방향으로 움직이며 최소 이동횟수를 확인하는 것이 핵심입니다 !