https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션, 구현, 브루트포스 유형의 문제이다. 생각보다 구현이 빡빡하다. (체감 난이도 골드4) 이 문제를 풀 때 내가 실수했던 부분은 하나였다. 감시구역이 겹치는 점을 고려하지 못한 것이다. 그래서 백트래킹으로 감시구역을 바꿀때, 다른 CCTV에 의해서도 감시되는 구역에 대해 감시를 풀어버린 것 때문에 틀렸었다. 그래서 숫자를 이용해 감시 카운트를 세도록 했다. 감시가 생길때마다 숫..
https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쓸데없이 힘들게 푼 문제이다. 알고리즘 분류가 백트래킹에 브루트포스였는데, 그렇게 풀었으면 더 쉽게 풀었을 것 같다. 전체 경우의 수가 1023가지 밖에 되지 않아서, 그냥 모든 케이스를 순서대로 방문해보면 된다. 각 숫자가 중복으로 쓰일 수 없어서 비트마스킹을 활용한 풀이도 있었다. 나는 DP 에 역추적을 써서 풀었다. 정말 빙빙 돌아서 풀었다 ㅋㅋㅋ 내가 푼 풀이는 2차원 DP ..
https://www.acmicpc.net/problem/15778 15778번: Yut Nori 윷놀이는 한국의 전통놀이중 하나로 윷가락을 가지고 진행하는 놀이이다. 윷놀이는 윷가락 4개와, 내 말 4개, 상대편의 말 4개로 총 말 8개 그리고 윷판 하나를 가지고 진행한다. 윷판은 다음과 www.acmicpc.net 진짜 디버깅.. 너무 힘들었다. 내가 스스로 고안한 풀이 방법으로 풀 땐 죽어도 안풀리다가,,,, 다른 사람이 사용한 구현 아이디어를 활용하여 구현하니까 한번 틀렸는데, 다행히 틀린 부분이 예제 입력 2번으로 디버깅이 되서 바로 통과됐다. (그래서 자존심에 매우 큰 스크래치를 입은 상태이다..ㅡㅡ) https://swoon1.tistory.com/4?category=804646 [파이썬] ..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나는 투포인터를 안쓰고 풀었는데, 정해가 투포인터라서 놀랐다. 확실히 '어떤 정렬된 것들중 일부의 연속' 은 투포인터를 쓰기 좋다. 일단 이 문제가 골드3이라서 당연히 DP부터 의심했는데, DP가 아닌 풀이가 떠올라서 바로 구현했다. 내가 푼 풀이와 투포인터 풀이를 모두 적어보겠다. 이분탐색을 이용한 풀이 소수의 리스트 2, 3, 5, 7, 11, 13, ,,,, 가 있다고 하고 소수의 누적합 배열을 s 라고 해보자. (누적합 배열은 0부터 시작한다고 하자) 최적해가 되는 구간은 어떤 소수로 시작할 것이다. 2로 시..
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 간만에 만난 진짜 너무 이해하기 어려웠던 문제이다. 이 문제를 풀고 이해하는데 3시간이 걸렸다 (이래야 골드1이지..) 이 문제의 핵심은 3가지다. 1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다. 2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다. 3. 최소를 구할 때도 0을 조심하자. 1. 최적해는 결국 사이클..
윈도우 10에는 기본으로 닷넷 프레임워크 4.0 이상, C# 컴파일러, 빌드 프로그램인 MSBuild 라는 프로그램이 있다. 이 MSBuild를 이용하면 우리는 비주얼스튜디오 없이, 메모장만으로 윈도우 프로그램을 만들 수 있다. 하지만 가능하다면 VS Code는 깔려있기를 바란다. 문법 하이라이트가 있고 없고 차이는 생각보다 큰데다, VS Code에는 터미널이 프로그램 내부에 있어 번거로움도 적다. 그렇다면 MSBuild는 어떻게 이용하면 좋을까? https://docs.microsoft.com/ko-kr/visualstudio/msbuild/msbuild?view=vs-2022 MSBuild - MSBuild MSBuild(Microsoft Build Engine) 플랫폼에서 XML 스키마를 사용하여 ..
https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 보자마자 DP인건 알겠는데, 1시간동안 고민해도 답이 안보여서 풀이 아이디어를 보고 푼 문제이다. 이 문제는 내가 한번도 풀어본 적 없는 유형의 문제였다. 처음에는 '9876543210' 이라는 기본 틀에다가 앞뒤로 숫자를 붙이는 걸 고민했다. 당연히 뻘짓이었다 ㅋㅋ 12부터는 98767543210 이런식으로 기본틀 사이에 숫자가 들어갈 수 있기 때문이다. 이게 뻘짓이라는 걸 깨닫기까지 40분이 걸렸다.. 그 다음으로는 구간DP를 떠올렸다. 길이가 i 이고 첫숫자가 j 마지막 숫자가 k 인 수의 개수 이런식으로 DP를 ..
https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 분리집합 + 그래프 탐색 문제이다. 주어진 입력에서 연결요소의 개수를 세면 된다. 같은 연결요소인지 아닌지 구분하기 위해 나는 분리집합을 사용했는데, 2차원 분리집합 구현은 처음이라 조금 애를 먹었던 것 같다. 그냥 단순무식하게 튜플을 있는 그대로 비교했는데, 다른 방법도 있을 것 같다. 내가 사용한 알고리즘 1. 모든 배열을 순회하면서 아직 방문하지 않은 노드..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 사이클에 속하지 않는 노드의 개수를 세는 문제이다. 생각보다 최적화를 깐깐하게 요구했던 문제이다. 하지만 덕분에 내가 놓치고 있던 부분을 확실하게 바로잡을 수 있었다. 살면서 처음으로..!! python 그룹 언어에서 제일 빠르게 푼 사람이 되보았다 ㅋㅋㅋ (21.12.17 오전 10시 30분 기준) 물론 저 32ms 차이는 크게 의미있는 차이는 아니지만.. 기분이 좋다 ㅎㅎ 이 문제의 알고리즘 분류는..
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제를 읽어보면 그냥 MST의 정의를 적은 것과 같다. 다만 다른 MST 기본 문제와 다르게 간선 정보를 직접 계산해야한다. 물론 별이 최대 100개까지라서 모든 별 사이의 간선을 다 구해놓고 시작하면 된다. 처음에는 소수점 계산하다가 문제가 생길 것 같아서 Decimal 라이브러리를 이용했는데, 혹시 몰라서 그냥 내장 float 자료형을 써보니 풀렸다. 그리고 시간차이는 내장 자료형을 쓰는 편이 ..
