Coding Test/Solution

1. 문제 설명 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net 이제 MT 갈 때 됐으니, MT 문제를 풀어보라던 스터디원의 권유로 보게 된 문제. 오랜만에 코테 문제 푼다고 새벽 3시까지 못잤다. 장장 10시간 정도를 풀었던 것 같다. 🤮 물론, 그 사이에 프로젝트 때문에 개발을 멀티로 수행했다는 것도 문제였던 거 같기도 한데, 문제만 봤어도 금방은 못 풀었을 것 같다. 2. 아이디어 보자마자 위상정렬(Topological Sort) 문제겠거니 했다. "내가 가려면 누군가(선행조건)가 가야 한다."식의 문제이므로, '나'의..

1. 문제 설명 요새 너무 바빠서 문제 하나 풀 여유조차 없다는 게 너무 서러워서 골드 문제라도 오랜만에 풀어봤다. 플래티넘은 푸는데 시간이 얼마나 소요될 지 감이 안 잡혀서 ㅠㅠ 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 2. 아이디어 이 문제를 처음 보자마자 vertex cover 문제로 접근하면 되겠구나 싶었다. (그러면 이분 매칭 문제로 바뀐다.) 하지만 조금 더 생각을 해보자. 가중치가 따로 존재하진 않으므로, 유량을 1로 전부 고정시키고 포스 풀커슨 알고리즘을..

1. 문제 설명 15721번: 번데기 예를 들어 7명이 있고, 16번째 등장하는 “뻔”을 부른 사람의 번호를 알고 싶다면 입력은 7 16 0이다. 4명이 있고 6번째 등장하는 “데기”를 부른 사람의 번호를 알고 싶다면 입력은 4 6 1이며, 이 www.acmicpc.net 2. 아이디어 심심해서 구글링 하면서 놀다가 우연히 발견한 문제였는데 문제 유형은 브루트 포스라고 되어 있고 실제로 그렇게 해도 상관 없지만, 수학적으로 최적화가 가능할 것 같아서 풀어봤다. (꽂히면 해봐야 하는 타입) 근데 문제가 워낙 간단해서 별다른 성과를 얻지는 못했다. 잘 생각해보면 이 문제는 T번 째 0 혹은 1의 위치만 알면 인원수의 나머지를 구하면 답이 나온다. result = T_index % A 그럼 이 문제는 "T번 ..

1. 문제 설명 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 테스트 케이스가 한 개 뿐인 동일한 티어의 문제가 또 있다. 경험치 2배 이벤트 댕꿀~ algospot.com :: ..