코딩 공부하는 코딩류

회의실 한 개로 최대한 많은 회의를 하려고 한다. 각 회의가 겹치지 않으면서 최대한 많이 할 수 있는 회의 수를 찾는 문제 문제의 조건 1. 총 회의 갯수 N이 주어진다. 2. 다음 줄부터 각 회의의 시작 시간과 종료시간이 주어진다. 3. 가능한 회의의 최댓값 출력 풀이 과정 현재 진행 중인 회의의 종료 시간보다 다음 회의의 시작 시간이 같거나 크다면 정답 수에 포함시키는 방식으로 코드를 짰습니다. 하지만... 처음엔 예제의 답이 마치 정렬을 하지 않고 주어진 순서 그대로 푸는 것 처럼 보여서... 정렬을 하지 않은 상태로 위의 알고리즘을 적용했더니 틀림 ㅠ.ㅠ 예제를 보면 아시겠지만 정렬을 하지 않는다고 충분히 오해할 만한 내용이지 않나요???? 내가 아직 경험이 짧아서 그런 것인지..흑흑 암튼 또 질..

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 문제의 조건 1. 준규가 가진 동전의 개수 N, 만들어야 하는 금액 K가 주어진다. 2. 둘째 줄부터 동전의 가치가 오름차순으로 주어지는데 i ≥ 2인 경우에 Ai는 Ai-1의 배수 풀이 과정 동전의 최솟값을 구해야 하니까 가지고 있는 금액 중 가장 큰 금액부터 빼 나가면 된다고 생각했습니다. 그래서 그렇게 금방 코드를 짜고 예제도 통과가 잘 되고 반례도 통과가 잘 됐는데도 계속 틀렸다고 하는 것입니다. ????? 모징...ㅠㅠ 또 한시간정도 게시판을 헤매다가 문제를 알게 되었습니다. 전 처음에 준규..

제목 그대로 DFS와 BFS로 그래프를 탐색한 결과를 출력하는 문제 문제의 조건 1. 주어진 그래프를 DFS와 BFS로 각각 탐색한 결과를 순서대로 출력하면 된다. 2. 단, 방문할 수 있는 정점의 개수가 여러 개면 정점의 수가 작은 것 부터 방문한다. 풀이 과정 처음에는 요즘 알고리즘을 공부하고 있는 책에 나와 있는 알고리즘을 썼는데... (대충 엣지 좌우 저장하는 구조체 만들고 전체 그래프를 구성하는 클래스를 만든 뒤 그렇게 만들어진 그래프 클래스를 이용해서 bfs와 dfs를 수행하는 내용 코드 길이가 A4 한 장 정도 됨) 알고 보니 모든 정점이 서로서로 연결되어 있다는 것을 전제로 한 알고리즘이라 이번 문제에는 맞지 않았습니다. 주륵 ㅠ.ㅠ 그리고 제게는 그것을 수정할 능력이 없었습니다...ㅋㅋㅋ..

ATM이 한 대 밖에 없는 은행에서 N명의 사람들이 차례대로 줄을 서서 돈을 뽑을 때, 모든 사람들이 돈을 뽑는데 걸리는 시간의 최솟값을 구하는 문제 문제의 조건 1. 돈을 뽑으려는 사람들의 수 N, N명의 사람들이 각각 돈을 뽑는데 걸리는 시간을 나타낸 배열이 주어짐 (둘째 줄에 주어지는 것이라 실제로는 반복문 돌리면서 배열에 값 입력받기) 2. 사람들이 각각 걸리는 시간은 다 다른데 사람들이 뽑는 순서에 따라 최종적으로 걸리는 시간의 합계가 달라진다. 3. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 ..

상근이가 최소로 옮기면 되는 설탕 봉지가 몇 봉지인지 구하는 문제 문제의 조건 1. 상근이는 설탕을 정확하게 N kg을 배달해야 한다. 2. 하지만 상근이는 좀 귀찮아서 최대한 적은 봉지를 배달하고 싶다. 3. 상근이가 배달할 수 있는 설탕 봉지의 무게는 3kg과 5kg 짜리 두 가지가 있다. 4. 두 종류의 설탕 봉지들만 사용해서 가장 적게 가져갈 수 있는 봉지가 몇 봉지인지 구하기 5. 만약 정확하게 N kg을 배달할 수 없으면 -1을 리턴한다. 풀이 과정 1. 상근이는 최대한 적은 봉지를 배달하고 싶기 때문에 5kg 짜리를 최대한 많이 쓰는 것이 이득이다. 2. 그렇기 때문에 먼저 5kg 짜리로 N kg을 나눠본 후 0으로 나눠 떨어지면 그 몫이 정답이다. 3. 하지만 2번에서 나눠 떨어지지 않는다..

권투 선수들의 승패에 따른 순위를 매겨야 하는데 몇몇 경기 결과는 분실되었다. 경기 결과를 확실하게 알 수 있는 선수들만이라도 추려보려고 하는데 순위를 정확하게 매길 수 있는 선수가 몇 명인지 구하는 문제 문제의 조건 1. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 주어짐 2. results 배열의 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 뜻이다. 3. 모든 경기 결과에는 모순이 없다. 아직 그래프에는 많이 약하기 때문에 힌트를 봤는데 플로이드-와샬 알고리즘을 이용하면 쉽게 풀린다고 해서 무엇인지 찾아보았습니다. 플로이드-와샬 알고리즘 최단 거리를 구하는 그래프 알고리즘 중 하나 모든 쌍을 표현하는 행렬(2차원 배열)을 이용해서 다이나믹 프로그래밍 방식으로 각 정점간의 최단..

캐릭터가 상대방 진영까지 가는데 걸리는 최단거리를 구하는 문제 제목 보고 그래프 문제인 줄 알고 시작했는데 알고보니 bfs 문제였다. 하지만 아직 bfs도 숙련되지 못했기 때문에 푸는데 오래 걸렸다... 문제의 조건 1. 게임 맵에서 벽과 길을 표시한 2차원 배열 maps가 주어짐 2. maps에서 0은 벽이라서 지나갈 수 없고 1은 길이라서 지나갈 수 있다. 3. 캐릭터의 초기 위치는 항상 [0,0] 이고 상대방 진영 위치는 항상 맵의 우측 하단이다. 즉 상대방 진영 위치는 n x m 크기를 가진 maps 배열 상에서 [n-1, m-1] 이다. 풀이 과정 1. bfs로 이동할 수 있는 다음 칸을 탐색하면서 다음 칸까지의 최단 거리를 계산한다. => bfs로 이동할 다음 칸을 저장할 queue 필요 qu..

신입사원 네오의 업무를 도와주기 위해 새로운 카카오 아이디를 만드려는 고객들이 규정에 맞지 않는 아이디를 입력한다면 규정에 맞는 새로운 아이디를 추천해주는 프로그램을 개발해야 하는 문제 문제의 조건 1. 고객이 입력한 아이디를 담은 string 배열 new_id가 주어짐 2. 아이디 변환 규칙 위 순서대로 차례차례 구현만 하면 된다. #include #include #include using namespace std; string solution(string new_id) { string answer = new_id; int stage = 1; //5단계부터는 new_id가 빈 문자열이 될 수도 있기 때문에 처음 4단계까지만 반복문 속에서 반복 while (4 >= stage) { for (int i =..