🔗문제 보러가기 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 👨‍💻풀이 과정 2부터 N까지 소수를 구하는 "에라토스테네스의 체" 알고리즘 1번에서 구한 소수들의 누적합을 저장해 둔 배열 투 포인터를 사용하여 부분 구간을 이동해가며, N이 나오는 구간의 개수를 카운트 위 순서대로 저는 문제를 풀었습니다. 투 포인터와 관련된 소스 코드는 많이 작성해보지 않아서 그런지, 짜는 데에 조금 시간이 걸리네요. ✏️소스 코드 및 결과 #include #include using namespace std; #define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); ..

🔗문제 보러가기 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 👨‍💻풀이 과정 내부 공기와 외부 공기를 어떻게 구별할까 고민했습니다. 문득 떠오른 생각은 다각형 외부 내부 판별 알고리즘이었는데, 치즈가 다각형이 아닐 수도 있기 때문에 적용할 수가 없더라구요. 그래서 문제에서 주어진 정보인, "가장자리에는 치즈가 놓이지 않는다"라는 걸 활용해 가장자리에서부터 BFS를 통해 외부 공기를 만들어주기로 결정하였습니다. 이 로직을 위해, 입력 세팅을 할 때 조금 다르게 세팅해주었습니다. // 전역 변수들..

🔗문제 보러가기 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 👨‍💻풀이 과정 BFS로 코드를 작성했지만 17%에서 자꾸 틀렸는데, 반례를 도무지 모르겠어서 다른 분들 코드를 약간 참고했습니다. 참고해보니, 제가 간과한 사실들이 있었습니다. 고슴도치의 시작 위치는 여러 개일 수 있다. 매 분마다 주어진 물의 위치들을 모두 확장하지 않고, 하나만 확장했다. 이 부분들만 고쳐서 다시 제출하니 통과할 수 있었습니다. 다음에는 조금 더 신경써야겠네요. ✏️소스 코드 및 결과 #include #include #include #i..

🔗문제 보러가기 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 👨‍💻풀이 과정 세그먼트 트리(Segment Tree) 첫 입문 문제로 풀었습니다. 첫 시도고, 조금 변형된 문제인지라 결국 다른 분들의 풀이를 참고하여 풀었지만, 세그먼트 트리라는 개념과 어느정도 친숙해진 그런 계기가 아니었나 싶습니다. 백준 문제를 풀면서 느낀 거지만, 다양한 알고리즘 문제들을 접해볼 수 있다는 게 되게 좋은 것 같습니다. 아직 접해보고 풀어봐야 할 문제들이 많지만 하나씩 천천히 해봐야죠...

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑🏻‍💻 풀이 과정 [1차 시도] 다익스트라 알고리즘 (실패) 출발지(s)로부터 각 노드에 대한 최단 경로 배열을 구해놓고, 각 노드(i)마다 다익스트라 알고리즘을 돌려서 s👉🏻i + i👉🏻a + i👉🏻b 값들 중 최솟값을 구하는 방식으로 풀었습니다. 노드의 개수(N)가 최대 200개라 될 줄 알았는데 효율성 테스트에서 시간 초과가 나더군요. [2차 시도] 플로이드 워셜 알고리즘 (성공) 매 노드마다 다익스트라 알고리즘을 돌린 것이 원인이라 생각되어, 모든 노드 간의 최단 경로를 구할 수 있는..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 다익스트라 알고리즘을 활용하여 풀었습니다. 목적지(Destination)를 시작점으로 하여 각 지역에 대한 최단 거리 배열을 구하고, 출발지(source)들에 해당하는 값들을 answer 배열에 담아주었습니다. 만약 어떤 출발지의 최단 거리 값이 초깃값과 같다면, 그 지역은 못 간다는 의미이므로 -1을 담아주면 되구요. 또한, 모든 지역 간의 이동 비용이 1이므로, 우선순위 큐 대신 일반 큐를 활용하여 시간을 줄였습니다. ✏️소스 코드 및 결과 #include #include ..