본문 바로가기

Algorithm

 (72)
[1일 1알고] S4 10656 십자말풀이 https://www.acmicpc.net/problem/10656 오늘은 간단한 구현 문제입니다. NxM격자가 주어지기 때문에 이차원 벡터를 사용해야겠지만 구분이 없는 문자열로 주어지기 때문에 벡터의 요소로 string을 사용하는 것으로 대신했습니다. 그리고 결과가 r, c 순서로 정렬되며 중복을 제거해야되기 때문에 set 자료형을 사용했습니다.#include #include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector v(N); for (int i = 0; i > v[i]; } ..
[1일 1알고] G5 2011 암호코드 https://www.acmicpc.net/problem/2011 "정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다."라는 문장이 있는 것으로 보아 모든 경우를 직접 계산하는 것은 아니고, dp를 통해 계산하게 될 것임을 알 수 있습니다. 11이라면 AA 혹은 K로 해석될 수 있습니다.따라서 현재 시점에서 숫자를 따로 해석하는 경우와 합쳐서 해석하는 경우를 나눠서 보아야 합니다. 그렇다면 index i일 따로 해석하는 경우에는 i-1 시점의 경우의 수, 같이 해석하는 경우는 i-2 시점의 경우의 수와 같기 때문에전체 경우의 수 dp[i] = dp[i-1] + dp[i-2]가될 것입니다. 하지만 이것은 숫자가 따로 + 합쳐서 해석이 가능한 경우에만 그렇고 모든 경우를 따져봐야합니..
[1일 1알고] S4 27466 그래서 대회 이름 뭐로 하죠 개요https://www.acmicpc.net/problem/27466 간단한 문자열 가공 문제입니다.마지막 문자는 모음이 아니며 마지막에서 두 번째 ,세 번째 글자는 A인 문자열을 만들어야합니다. 조건에 맞게 가공 후 조건에 맞는다면 YES와 가공 문자열을, 아니라면 NO를 출력합니다. 의식의 흐름대로 코드를 만들어 인덱스가 헷갈리게 되었는데 직접 하시면 더 깔끔하게 코드를 만들 수 있을 것으로 보입니다.int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; string S; cin >> S; int len = N; int temp = N-1; reverse(..
[1일 1알고] G4 16169 수행 시간 https://www.acmicpc.net/problem/16169개요 1. 1~n개의 컴퓨터가 존재, 컴퓨터는 계급, 동작 속도를 가짐 > 0 2. ij의 전송 시간 = (i-j)^2 3. 계급은 ci, 오름 차순으로 정리한다면 |c(j)-c(j-1)| 1보다 크게 차이나지 않음 4. 최하위 계급을 제외한 컴퓨터는 한 단계 낮은 계급에게 "모두"전달받아야 동작 가능 5. 최하위 컴퓨터는 시동과 동시에 동작 6. c계급 컴퓨터가 동작을 마치면 "모든" c+1컴퓨터에 정보 전달 후 종료+ 가장 낮은 계급이 1위의 조건이 필요합니다. 처음에는 하나의 컴퓨터가 종료 후 다음 계급 컴퓨터 하나에 전달한다고 오해해 시간이 걸렸지만모두 전달받아야하며, 종료 시 모든 곳에 전..
[1일 1알고] 23352 방탈출 https://www.acmicpc.net/problem/23352개요1번 조건에 의해 bfs계열 탐색을 해야함을 알 수 있습니다.각 격자 당 추가적인 가중치가 존재하지 않기 때문에 굳이 다익스트라 등의 알고리즘을 사용할 필요는 없고 bfs를 사용할 것입니다. 전체에서 가장 긴 거리를 찾아야 하는데, 딱히 추가적인 조건이 없기 때문에 하나하나 bfs를 해야되나 싶습니다.그런데 문제에서 조건이 N,M 코드using namespace std;int N, M;void bfs(int sr, int sc, vector>& v, int* pmax_dist, int* presult);int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // NxM..
[1일 1알고] 32574 손이 닿는 범위 https://www.acmicpc.net/problem/32754 해당 문제는 간단한 거리 계산 문제입니다.다행히도 2차원 도형문제이기 때문에 크게 생각할 것은 없었습니다. 먼저 직사각형이기 때문에 무게중심은 각 꼭짓점을 더한 것의 4분의 1에 위치할 것입니다.그리고 원점에서 가장 가까운 거리를 가지도록 회전하기 위해서는 무게중심에서 가장 먼 위치인 대각 꼭짓점이 원점의 기울기에 맞게 회전해야할 것입니다. 무게중심 간 기울기와, 가장 가까운 거리의 점까지의 기울기가 같기 때문에 결론적으로 원점에서 가장 가까운 거리는 무게중심까지의 거리와 무게중심에서 꼭짓점 까지의 거리의 차이입니다.int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ..
[1일 1CS] TCP 오늘부터 잦은 CS개념 복습을 위해 하루에 하나의 개념을 복습해보는 시간을 가지려고 합니다. 이는 다른 포스팅에서 다루는 내용에 비해 얕으며 의식의 흐름에 따라 아는 내용을 적어보고자 합니다.TCP 개념 간단 복습TCP는 (Transmission Control Protocol)로 네트워크 모델 중 Transport Layer에 위치한 프로토콜입니다.통신계층 프로토콜이기 때문에 종단 간 위치하는 하나의 port까지의 데이터 전송을 담당합니다.( 이는 UDP와는 다르게, 신뢰성있는 전송을 위한 방식을 사용합니다. 1. TCP는 왜 연결지향 프로토콜이라고 부르는가?TCP는 신뢰성있는 통신을 위해 통신 전에 3handshake를 통해 서버(연결 요청을 받는)와 클라이언트(연결을 요청하는) 사이의 연결 정보를 서..
[PS] 소수점 제한하기(C++) 개요일반적으로 알고리즘 문제를 풀 때 소수점 단위의 답을 요구하는 경우 특정 소수점까지 제한하는 경우가 있습니다. 이를 표현하기 위한 방법을 모른다면, 어렵게 구현을 해놓고 정작 답은 맞을 수가 없는데요, 오늘은 이를 위한 방법을 간단하게 알아보겠습니다. 아래는 이를 활용하는 문제의 예시입니다.https://www.acmicpc.net/problem/6487(두 직선이 정확히 한 점에서 만난다면, POINT x y의 꼴로 출력한다. 이는 두 직선이 (x,y)에서 교차함을 의미한다. x와 y는 정확히 소수점 아래 둘째 자리까지 출력한다.) 선결론출력 시, std::fixed와 std::setprecision(n)을 사용하면, n자리수로 반올림해 출력하는 것이 가능해집니다.cout 실제로 값을 반올림해서 저..

티스토리툴바