컴굥일지

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121683?language=cpp 문제 내용 소문자로만 이루어진 문자열에서, 2회 이상 나타난 알파벳이 2개 이상의 부분으로 나뉘어 있으면 "외톨이 알파벳"이라고 부른다. 입력받은 문자열에 대해, 외톨이 알파벳을 모두 구하여 사전순으로 출력하면 된다. 문제 풀이 문자열을 잘 처리해 주면 되는 문제이다. 코드 #include #include #include using namespace std; string solution(string input_string) { vector position(26,-1); //-1로 초기화 vector alone(26,false); bool flag =fals..

문제 https://www.acmicpc.net/problem/16234 문제 내용 N*N 크기의 땅이 있고, 1*1 크기의 나라들로 채워져 있다. r행 c열에 있는 나라에는 arr[r][c] 명이 살고 있고, 인접한 나라들끼리는 인구 이동이 일어날 수 있다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 공유하는 국경선을 하루 연다. 위의 조건에 의해 열어야 하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. (소수점은 버린다.) 연합을 해체하고, 모든 국경선을 닫는다. 인..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87694 (문제가 길기 때문에, 전체 내용은 링크에서 확인) 문제 내용 직사각형이 여러 개 주어진다. 캐릭터는 이 직사각형들을 다 합쳤을 때의 나타나는 다각형의 테두리만을 걸어 다닐 수 있다. 캐릭터의 좌표와 아이템의 위치가 주어질 때, 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 출력하면 된다. (아래는 주의 사항) 1. 직사각형이 다른 직사각형에 포함되는 경우는 없다. 2. 직사각형들이 서로 꼭짓점에서 만나거나, 변이 겹치는 경우는 없다. 3. 직사각형들을 다 합치면 반드시 하나의 다각형이 나온다. 4. 캐릭터,아이템의 위치는 반드시 다각형의 테두리에 위치한다. 문제 풀이 이 문제는 ..

문제 https://www.acmicpc.net/problem/15683 문제 내용 N*M 크기의 사무실에, CCTV가 달려있고, CCTV는 벽을 넘어서 감시할 수 없다. CCTV의 종류는 5가지가 있는데, 그 종류는 위의 문제에 나와 있다. CCTV의 방향을 조절하여, 사각지대를 최소화하고자 한다. 문제 풀이 이 문제는 코드의 길이가 좀 길기는 하지만, 차근차근 진행하면 할 만하다. 구현해야 하는 순서는 아래와 같다. 1. 각각의 cctv 방향 결정하기 => 백트래킹 사용 2. 결정된 cctv의 방향대로, 감시 영역 표시하기 3. 사각지대 개수 세기 1. 각각의 cctv 방향 결정하기 1,3,4번 cctv는 방향이 4가지가 나오지만, 2번은 2가지, 5번은 1가지로 충분하기 때문에 range 변수로 f..

문제 https://www.acmicpc.net/problem/15686 문제 내용 "치킨 거리"는 집과 가장 가까운 치킨집 사이의 거리이고, "도시의 치킨 거리"는 모든 집의 치킨 거리 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 크기가 N*N인 도시에 치킨집이 여러 개 있다. 이 중에 최대 M개만 남기고 나머지는 폐업시키려 한다. 이때 도시의 치킨 거리가 가장 작게 되는 경우를 구해야 한다. 문제 풀이 일단 도시의 치킨 거리가 가장 작게 되야 하기 때문에, 치킨집은 M개여야 한다. (치킨집이 많아야 각각의 집과의 거리도 줄어든다) 그럼 해당 문제는 아래의 과정으로 나눌 수 있다. 1. 전체 치킨집 중에 M개를 고른다. => 백트래킹..

문제 https://www.acmicpc.net/problem/17406 문제 내용 크기가 N*M인 배열 A가 있다. 배열 A의 값은 각 행별로 합을 구한 후, 그 중에서 최솟값을 의미한다. 배열은 회전 연산을 수행할 수 있다. 회전 연산 (r, c, s)가 주어지면 (r-s, c-s) 부터 (r+s, c+s) 까지의 정사각형을 (r,c)를 중심으로 시계방향으로 한 칸 회전시키는 것이다. N*M 크기의 배열과 회전 연산 k개를 입력 받아, 연산 k개의 순서를 조정하여 배열의 값이 최소가 되는 값을 구하면 된다. (단, 연산 k개는 모두 1번 씩 수행해야 한다.) 문제 풀이 이 문제는 구현할 양이 꽤 많다. 그렇기 때문에 과정을 나누어 해결할 필요가 있다. 1. 배열의 값 구하기 => 단순 구현 2. 연산..

문제 https://www.acmicpc.net/problem/17070 문제 내용 (1,1), (1,2)에 걸쳐 가로로 놓여있는 파이프를 이동시켜 한쪽 끝이 (N, N)에 위치하게 하는 방법의 개수를 구하면 된다. 파이프는 한 번 이동할 때, 벽을 긁으면 안 되고 빈칸만을 차지해야 한다. 파이프는 밀면서 45도 회전이 가능하다. 또한, 밀 수 있는 방향은 →, ↘, ↓ 뿐이다. 문제 풀이 bfs를 사용하여 문제를 해결할 수 있다. 파이프가 가로로 위치했을 때는 →, ↘ 방향으로 이동할 수 있고, 세로로 위치했을 때는 ↘, ↓ 방향으로 이동할 수 있고, 대각선으로 위치했을 때는 →, ↘, ↓ 방향으로 이동할 수 있다. 즉, 우리는 매 순간 파이프가 놓여있는 방향과 좌표를 알아야 한다. bfs를 통해 각 ..

문제 https://www.acmicpc.net/problem/5014 문제 내용 건물의 높이는 F층이고, 현재 강호가 있는 곳은 S층이다. 강호는 G층으로 가려하는데, 엘리베이터는 U층 위로 가거나 D층 아래로 가는 버튼뿐이다. 강호가 G층으로 가기 위해 버튼을 몇 번 눌러야 하는지 구하면 된다. (만약, 버튼을 어떻게 눌러도 G층으로 갈 수 없다면 use the stairs를 출력한다.) 문제 풀이 1차원 int 배열을 선언해 두고, bfs 방식으로 문제를 풀면 된다. bfs를 통해 방문 체크를 할 때, 버튼을 누른 횟수를 같이 저장한다. 그러면 반복문이 끝나고 visited[G]를 했을 때 결과를 구할 수 있다. 코드 #include #include using namespace std; int f,..

문제 링크&사진 문제 내용 출석이 되기 위해서는 개강총회가 시작할 때까지 입장을 하고, 개강총회가 끝나고부터 스트리밍이 종료될 때 나가야 한다. 각 학생들의 채팅 기록과 닉네임이 주어질 때, 출석이 된 학생의 수를 모두 세면 된다. 문제 풀이 개강 총회가 시작되는 S 시간과 같거나 더 빠른 시간에 채팅이 남아있는 사람을 unordered_set에 추가한다. 이후 개강총회가 끝나는 E 시간부터 스트리밍이 끝나는 Q 시간까지 남아있는 사람 중, 제시간에 출석을 한 사람만 다시 unondered_set에 추가한다. 이후 크기를 구해서 출력해주면된다. 시간 비교가 이 문제에서 그나마 까다로운 부분인 것 같은데, 나는 substr()을 통해 시간과 분을 따로 비교해 주었다. 코드 #include #include ..

문제 https://www.acmicpc.net/problem/16165 문제 내용 걸그룹 팀 이름과 걸그룹 멤버들을 입력받는다. (한 개의 팀이 아닌 여러 개의 팀이다. 입력 형식에 맞게 처리할 것) 이후 팀 이름이 입력되면 멤버들을 출력하고, 멤버 이름이 입력되면 팀 이름을 출력하면 된다. 문제 풀이 unordered_map을 사용했다. (팀, 멤버 벡터) 형식으로 저장하기 위한 team_member와, (멤버, 팀) 형식으로 정하기 위한 member_team을 선언하여 사용한다. 팀에는 멤버가 여러 명이기 때문에 벡터 형식으로 지정했다. 또한, 팀을 입력했을 때는 멤버를 사전순으로 출력해야 하기 때문에 sort로 정렬을 진행했다. 코드 #include #include #include #include..