boj
-
[백준 BOJ/C++] 1707 이분 그래프알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 28. 01:04
1707번: 이분 그래프 이분 그래프 (Bipartite Graph) 의 개념을 알고있거나 문제에서 빠르게 이해했다면 그리 어렵지 않은 탐색 문제다. 하지만 문제의 설명이 짧고 친절하지도 않은 편이라 혼란스러울 수 있는 부분들이 있었다. 노골적으로 그래프 문제임을 보여주고있지만 자세한 설명이나 예시 없이 이분 그래프인지 아닌지를 판별하도록 하고있다. 이분 그래프라는 개념을 어느정도 알고 있었다면 그나마 접근이 용이하겠지만 그렇지 않은 경우 예시도 없는 한줄 설명 만으로 빠르고 정확히 이해하기에는 쉽지 않은 편이었다. 문제 자체에서 여러번 탐색이 필요하다거나 특정 알고리즘을 사용한다거나 구현 양이 많아지는 문제는 아니지만 생소할 수 있는 문제라 한번쯤 풀어보면 좋을 문제다. 문제의 포인트 이분 그래프의 개..
-
[백준 BOJ/C++] 9466 텀 프로젝트알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 23. 23:20
9466번: 텀 프로젝트 그래프에서 사이클을 찾고 사이클을 이루지 않는 노드들의 갯수를 세는 문제다. 제한시간에 걸리지 않기 위해서는 탐색했던 노드를 다시 방문하지 않도록 해야 한다. 학생들이 노드로 주어지며 다른 학생을 지목하는 간선을 통해서 그래프(Graph)가 만들어진다. 그래프에서 사이클(Cycle) 은 특정 노드에서 탐색해가다가 다시 해당 노드로 돌아오게되는 형태의 연결을 말한다. 팀은 자기 자신을 지목한 학생이나 사이클을 이루는 학생들로 만들어지며 팀을 이루지 못한 학생들의 수를 카운트 하면 된다. 문제는 간단해 보이지만 일반적인 그래프 탐색 알고리즘 보다 고민하고 체크해야할 것이 추가되어 난이도가 꽤 있는 편이다. 중복을 피하기 위해 방문했던 노드를 체크해야 하는데 추가적으로 싸이클에 포함되..
-
[백준 BOJ/C++] 1431 시리얼 번호알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 21. 22:51
1431번: 시리얼 번호 문자열 내에서 각 문자의 정렬이 아니라 문자열들을 정렬하는 문제다. 별도의 정렬 기준이 주어지기 때문에 문자열들 간의 비교와 정렬을 연습하기 좋은 문제다. 일반적인 정수나 문자들 사이에서의 정렬 문제는 간단하지만 문자열들의 순서를 바꾸는 문제는 직접 경험하지 않은 상태로 만나게 된다면 헷갈릴 수 있는 부분이 있어 풀어보는 것이 좋다. 사용하는 언어의 문자열 혹은 정렬 알고리즘 라이브러리에 어느정도 익숙해야 문자열 기준의 정렬을 어렵지 않게 할 수 있다. 사용 언어에 따라 난이도 차이가 발생할 수 있으며 특히 C언어를 사용한다면 문자열 포인터와 관련해서 신경써야할 부분이 꽤 있으므로 차라리 vector를 제공하는 C++을 이용해서 쉽게 접근하는 것이 이득일 수 있다. 문제의 포인트..
-
[백준 BOJ/C++] 18870 좌표 압축알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 19. 22:14
18870번: 좌표 압축 정렬을 통해 풀어내는 문제고 실버 II 난이도라서 쉽게 생각했지만 의외로 까다로운 문제다. 조건이 타이트하진 않지만 문제 설명이 자세하지 않고 생각을 좀 해야 풀이 방법에 다가갈 수 있다. 특히 사용하는 언어에 따라 난이도 차이가 심해질 수 있는 문제다. 우선 문제 설명이 짧은 편이라 단번에 파악하기 어려울 수 있는데 간단히 표현해 입력 받은 각 좌표들 보다 작은 좌표의 갯수를 출력하면 된다. 여기에서 한가지 조건을 추가해 압축이라는 형태를 만들었는데 바로 중복된 좌표는 1개로 간주해야 한다는 것이다. 이정도만 파악하면 문제가 간단해 보이지만 의외로 풀어가다보면 고민해야 하는 지점이 몇가지 있었다. 다른 언어에서는 훨씬 간단할 수 있지만 적어도 C나 C++에서는 쉽게 풀어내기에 ..
-
[백준 BOJ/C++] 1759 암호 만들기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 18. 00:52
1759번: 암호 만들기 아주 어렵지 않고 재밌게 풀 수 있는 순열/조합 문제다. Input으로 주어지는 알파벳 소문자를 중복 없이 조합하되 간단한 룰을 만족하는 조합을 찾아내면 된다. 1. 알파벳 사전 순서로 정렬 2. 1개 이상의 모음(a, e, i, o, u)과 2개 이상의 자음을 포함 위 규칙을 만족하면서 각 요소의 중복이 없는 조합을 만들어 모두 출력해야 한다. 이런 순열, 조합의 문제는 DFS로 구현하거나 간단히 각 언어마다 제공되는 API가 있다면 이를 이용해 어렵지 않게 풀어낼 수 있다. 문제의 포인트 순열 혹은 조합 구하기 순서가 의미를 가지고 중복을 허용하지 않는다는 점에서 순열이라고 할 수 있겠지만 사실 순서는 정해져 있는 것이기 때문에 일반적인 순열 문제와 같이 접근하지는 않았다. ..
-
[백준 BOJ/C++] 1987 알파벳알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 16. 01:33
1987번: 알파벳 백트랙킹, DFS를 연습하기 적당한 문제다. 요구사항이 복잡하거나 구현량이 많지 않고 중복된 알파벳을 피해서 가장 멀리 갈 수 있는 경로를 찾아야 한다. 알파벳으로 채워진 맵에서 같은 알파벳을 중복하지 않게 방문하여 갈 수 있는 최대 거리를 구하는 문제다. 시작점은 항상 (0, 0) 이며 상하좌우 한 칸 씩 탐색해 나가면 된다. 몇 몇 실수하기 쉬운 부분이 있는지 정답 비율이 낮은 편이지만 복잡한 문제는 아니라서 백트랙킹, DFS 문제와 관련해 기본기를 쌓기 좋은 문제다. 문제의 포인트 백트랙킹 알고리즘 알파벳의 중복 피하기 백트랙킹 알고리즘 일반적으로 맵 형태의 입력이 주어지고 이동시켜가는 문제는 BFS든 DFS든 탐색 알고리즘을 이용해야하는 경우가 많다. 최단 경로를 찾아야 하는 ..
-
[백준 BOJ/C++] 9663 N-Queen알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 16. 00:06
9663번: N-Queen 알고리즘 공부나 코딩 테스트를 준비하는 사람들이라면 꼭 한번 풀어봐야한다고 할 수 있을만큼 백트래킹을 대표하는 유명 문제다. 컴퓨터가 등장하기 훨씬 전부터 존재했던 문제로 8*8 크기의 체스판에 8개의 퀸을 배치하는 8-Queen 문제에서 시작되었다. Chess에서 Queen은 N * N 크기의 체스판에 정확히 N개까지 서로의 이동 경로를 피해서 배치할 수 있다. 이동 방법도 복잡하지 않아서 프로그램으로 단순화해서 풀이하기도 쉬운 편이다. N의 갯수가 15 미만인 것에서 흰트를 얻는다면 모든 경우의 수를 직접 따져봐야함을 알 수 있다. 하지만 이 문제를 처음 접하면 백트랙킹이나 브루트 포스에 대해 알고있더라도 막상 Queen을 놓는 상황과 앞서 놓은 Queen과의 위치 확인을 ..
-
[백준 BOJ/C++] 1781 컵라면알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:56
1781번: 컵라면 주어진 문제 리스트에서 각 시간당 가장 많은 보상을 얻을 수 있도록 최선의 선택을 해야하는 문제다. 문제 설명이 자세하진 않은 편이라 완전히 이해는데 시간이 좀 걸렸다. 풀고 나면 간단하고 구현도 쉽지만 그리디 문제 답게 접근하는 방법이나 아이디어를 떠올리기가 만만치는 않은 문제다. 한 시간에 한 문제씩 풀 수 있는데 각 문제에는 데드라인이 있어서 해당 시간 내에 풀어야 한다. 즉 반드시 그 시간에 푸는 것이 아니라 데드라인 시간 이전 어느 시간이든 풀 수 있다. 또한 데드라인은 얼마든지 중복될 수 있어서 매 시간마다 어떤 문제를 선택하는지에 따라 총 보상 수가 달라진다. 마치 각 조합을 모두 탐색해 최적해를 찾는 문제처럼 보이기도 하지만 문제의 수 N이 200,000으로 커서 모든 ..