개발조아

문제 링크 : https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 비트 연산, 비트마스킹 문제이다. 명령 1은 해당 자리 비트를 1로 변경한다 명령 2는 해당 자리 비트를 0으로 변경한다 명령 3은 왼쪽 쉬프트 연산이다 명령 4는 오른쪽 쉬프트 연산이다. 주의 할점이 있다. 1. 쉬프트 연산 방향 - 비트는 오른쪽에서 왼쪽으로 순서이므로 방향에 주의하자. 2. 왼쪽 쉬프트 연산 좌석은 최대 20개 이다. 만약 20번째 좌석에 승객이 앉..

문제 링크 : https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 투 포인터로 해결가능하다. 두개의 포인터(left, right)의 간격을 k로 유지하면서 진행하면 된다. 주의점은 끝나는 시점이다. right가 한바퀴 돌고 다시 right로 오는 시점까지 즉, 같은 구간으로 올때 까지 검사해야한다. 왜냐면 원형으로 이어진 회전초밥이기 때문이다. 이 부분을 놓쳐서 계속 틀렸다. 예를 들어 1 2 3 4고 ..

문제 링크 : https://www.acmicpc.net/problem/22944 22944번: 죽음의 비 가로, 세로 길이가 $N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지 www.acmicpc.net 나는 BFS로 풀었고 방문체크는 해당 칸을 방문했을 때의 체력을 기록했다. 그래서 다음번에 다시 방문했을 때 해당 칸보다 체력이 높아야 이동이 가능하게 했다. 더 낮은데 해당 칸으로 이동해봐야 기존의 방문했을 때보다 적게 가기 때문이다. BFS 진행시 범위 안에 들어왔을 때 조건들을 체크한다. 만약 E점이라면 종료한다. 아니라면 다음 점이 우산이라면 현재 내구도를 d로 바꾼다. ..

문제 링크 : https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 건물의 개수가 최대 100개고 모든 건물사이의 최단 거리를 구해놓으면 쉬우므로 플로이드 와샬로 해결하였다. 입력으로 반은 건물로 배열을 구성하는데 가중치는 1로 넣자 그리고 플로이드 와샬로 각점에 대해서 최단거리를 구해 놓자. 다음 치킨집을 지으려는 매장 두곳을 골라야한다. 이중포문으로 골라도 되지만 귀찮으니 combinations을 사용했다. 두개의 ..

문제 링크 : https://www.acmicpc.net/problem/22868 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 짧은 경로가 사전순으로 먼저 나온것이 우선으로 되어야한다고 해서 입력으로 생성한 인접 리스트를 정렬해주고 시작했다. 일단 나는 두번의 BFS를 수행했다. S에서 E로, E에서 S로 BFS를 두번 진행한다. S에서 E로 진행할 때는 경로를 저장한다. 방문체크 할때 다음 점이 어느 점에서 왔는지 넣어 준다. 그리고 도착했을 때는 마지막 점에서 거꾸로 올라..

문제 링크 : https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 각각의 샘터에서 좌우로 집을 하나씩 집을 놔보고, 그리고 그 집 양옆으로 집을 하나씩 놔보면 결국 불행도가 최소로 되게 집이 위치하게 된다. 그래서 큐에 집의 좌표를 넣고 집이 k개가 될 때 까지 수행해주면 된다. 결국 BFS를 수행하면 된다. 문제는 범위이다. 샘터는 -1억에서+1억까지다. 거기까지이고 집까지 놀 위치를 고려한다면 2억개가 넘는다. 따..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 시간 관련 구현문제이긴하나 시간은 간단했다. 일단 timetable의 시간을 분으로 바꾼 후 정렬하자. 9시에서 부터 시작하여 t 시간만큼 도착시간을 증가시키고 총 n번 수행하면서 사람들을 태우자. 이제 도착시간을 기준으로 timetabl..

문제 링크 : https://www.acmicpc.net/problem/22860 22860번: 폴더 정리 (small) main 폴더 하위에는 FolderA 폴더 하위에 있는 File1, File2, FolderB 폴더 하위에 있는 File1, File3이 있다. 파일의 종류는 File1, File2, File3 총 3가지이고, 파일의 총 개수는 File1, File2, File1, File3 총 4개이다. mai www.acmicpc.net 그냥 트리 구조 만들어서 했다. 노드는 이름, 종류, 파일 리스트, 폴더 리스트 4가지로 구성했다. 그리고 folders라는 딕셔너리에 입력으로 주어지는 폴더 정보의 상위 폴더 노드를 저장했다. main FolderA 1 FolderA File1 0 위의 두개 입..