얼레벌레

문제 링크 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 간단한 DFS + 구현/시뮬레이션 문제인 것 같다. (사실 문제유형 같은 거 잘 모른다.) 문제를 정리해보면, 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 탐색하는데, 1) 왼쪽에 아직 청소를 안한 공간이 있다면 -> 그 방향으로 회전하고 한 칸을 전진하고 나서 1.로 돌아간다. 2) 왼쪽에 청소할 공간이 없다면 -> 그 방향으로 회전하고 2.로 돌아..

문제 링크 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 구현 문제다. 별다른 알고리즘 없이 시뮬레이션으로 풀 수 있었다. (삼성 문제에는 시뮬레이션 문제가 참 많은 것 같다.) 1. 주사위 면 주사위의 면(동, 서, 남, 북, 위, 아래)을 구분하기 위해 dice 배열을 생각했다. dice 배열의 0번째 인덱스는 위, 1번째는 아래, 2~5번째는 순서대로 동서남북으로 정..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 생각해 본 것 벽을 딱 3개 세워야 하니까 처음에는 보드의 (x, y)를 mx+y 수식을 통해 일차원 배열로 만들고, 그 중 3개를 비트마스크를 통해 고르고, 고른 것을 바탕으로 바이러스 확산과 안전구역 계산을 하려고했다. 그런데 비트마스크가 너무 오랜만이라서 생각은 했으나 구현이 어려웠다.. (8*8 배열이고 1자로 펼치면 8*8+8=72개의 비트가 필요한게 아닌가? 생각이 들면서 점점 미궁에 빠졌음...

문제 설명 풀이 재귀를 이용해 풀 수 있는 백트랙킹 문제이다. 백트랙킹은 재귀로 함수를 호출하다가 특정 조건일 때 호출을 중단하고 리턴한다. 처음에는 연산자들을 순서대로 벡터에 저장하는 방법을 사용했다. sol 함수에서 현재 숫자들을 보는 인덱스, 지금까지 저장된 순서대로의 연산자 벡터를 파라미터로 넘겼다. 그리고 나서 현재 숫자들을 보는 인덱스가 N(숫자들의 수)와 같아지면 연산자를 끝까지 다 선택하는 것이므로, 만든 연산자 벡터를 통해 식을 계산하고, 최댓값과 최솟값을 갱신시켰다. 그런데 이렇게 하니까 계속해서 오류가 발생했다. (SIGSEGV, SIGTRAP 등..) 벡터 범위때문에 발생하는 문제인것 같았다. 그래서 연산자들을 벡터에 저장하지 않고, 그때 그때 연산자를 이용해 식을 계산하고, 계산한..

문제 설명 위키백과에 들어가서 H-Index에 대한 설명을 한 번 보고 푸는 게 좋아 보인다. (문제 이해가 안 될 수 있어서) 첫번째 시도 처음엔 H-Index 값이 citations 배열에 있는 수 중에 하나여야 하는 줄 알았다. 그래서 citations를 정렬하고, citations를 뒤에서 부터 보며 (n-i) 개수가 citations[i]보다 크거나 같을 때 answer에 citations[i]를 담아주었다. #include #include #include using namespace std; int solution(vector citations) { int answer = 0; sort(citations.begin(), citations.end()); int n = citations.size(..

문제 설명 첫번째 시도 처음엔 정렬문제여서 numbers 배열을 정렬하려고 했다. 정렬하는 기준을 (수 a와 수 b가 있다고 가정하면) 1) a가 b보다 맨 앞의 수가 크다면 a가 b보다 우선순위가 높음 2) a가 b보다 맨 앞 수가 작다면 b가 a보다 우선순위가 높음 3) a와 b가 맨 앞수가 같다면 그 다음 수를 봐야했다. 나는 3)부터 갑자기 문제가 복잡해졌다. 자릿수를 벗어날 수 있어서 자릿수 조건을 걸어줘야하고, 계속해서 수가 같다면 계속해서 다음 수를 봐야했다. 그래서 코드가 굉장히 더러워졌다.. #include #include #include using namespace std; bool compare(const int &a, const int &b) { int aArr[4], bArr[4]..

문제 설명 정렬문제이다. 레벨1로 어렵지 않게 해결할 수 있었다. 풀이 1. commands 벡터를 돌면서 (각 범위마다) 2. tmp 벡터에 넣고 정렬함 3. commands벡터의 맨마지막 인덱스에 있는 수를 tmp에서 빼서 answer에 넣음 #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; for(auto i:commands){ vector tmp; for(int j=i[0]; j

문제 설명 문제 설명에 나와있는 대로 베스트앨범 수록곡을 작성하면 되는 문제이다. input: genres(문자열 배열, 노래의 장르가 담김), plays(정수 배열, 노래 별 재생 횟수 담김, plays[i]는 i번째 노래의 재생횟수) output: 베스트 앨범에 들어갈 노래의 고유 번호 순서대로 리턴 첫번째 시도 1. map을 이용해 각 장르의 play 수를 입력 각 장르별 total 재생횟수를 더해서 map에 저장했다. 그리고 많이 재생된 장르를 먼저 수록하기 위해 cmp 함수를 만들어 정렬했다. 2. 각 장르별로, 재생횟수 내림차순으로 노래를 저장 vvii 배열과 vii 배열을 만들었다. vvii 배열은 (int, int)의 이중배열인데, vvii[0]에는 0번째(total 재생횟수가 많은)장르의..

문제 설명 전화번호 배열 phone_book 이 주어진다. 한 번호가 다른 번호의 접두어인 경우 (어떤 번호가 다른 번호로 시작하는 경우) false를 반환하도록 해야 한다. 만약 그런 경우가 하나도 없다면 true를 반환하도록 한다. 나의 풀이 방법 처음엔 이게 왜 map 문제인지 몰랐다. 하지만 코테 연습을 설렁설렁해 온 나같은 사람은 문제 분류를 보고 그냥 그 분류에 있는 대로 문제 풀이를 해야 한다고 생각해서.. (다른 방법이 있을 수도 있지만 당장에 문제 풀이 연습이 중요) 그냥 map으로 해결해 봤다. 1. phone_book 배열에 있는 번호를 길이 순으로 정렬 어떤 번호(A)로 시작하는 다른 번호(B)가 있을 수 있는 상태이므로, 짧은 길이인 A를 먼저 map에 넣어놓을 수 있게끔 phon..

map STL을 사용하는 문제였다. (이전엔 다른 방법으로 푼 기억이 있긴 함..) 문제 정리 string 배열 두개가 주어진다. participant 배열은 참여 선수들, completion 배열은 완주한 선수들이 담겨있다. 그 때 완주하지 못한 선수의 이름을 return 해야 한다. 첫 번째 시도 map에 participant를 다 담고, completion으로 한 명씩 빼냈다. 그리고 마지막에는 map에 담긴 사람의 이름을 answer에 넣어서 return 했다. #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; map m; /..