구현

[프로그래머스 level2] 프렌즈4블록 (C++)

카카오 코딩테스트 [1차] 문제 2차원 배열의 원소가 떨어지는걸 구현하는게 핵심인 구현 문제이다. 문제에서 구현할 부분이 확실하게 나눠져 있음을 확인했다. 2x2 블록을 모두 찾아서 지우기 지워진 블록 떨어뜨리기 2x2블록을 찾아서 삭제하는 부분이다. bool deleteBoard(){ int del = 0; for(int r = 0; r < N; r++){ for(int c = 0; c < M; c++){ if(!board_records[r][c]) continue; del += delete2x2(nboard[r][c], r, c); } } for(int r = 0; r < N; r++){ for(int c = 0; c < M; c++){ if(board_records[r][c] == 2){ board..

[백준 5547] 일루미네이션 (C++)

5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net BFS 구현 문제이다 위 그림에서 2,3 좌표는 비어있는데 건물에 둘러싸인 '내부 공간'이다. 건물이 좌표 바깥이나 외부 공간과 맞닿아 있다면 답을 +1 해주면 되는데, 내부 공간이라는 변수 때문에 단순한 bfs로는 풀리지 않는다. 따라서 빈 공간이 내부 공간인지, 외부 공간인지를 미리 판단 해 놓아야 한다. 그걸 어떻게 판단하는가? 하나 이상으로 이어진 외부 공간은 좌표 바깥 부분과 맞닿아있다. 따라서 좌표의 경계선에 위치한 빈 ..

[프로그래머스] level2 빛의 경로 사이클 (C++)

월간 코드 챌린지 시즌 3 그림만 보면 무시무시하지만 실제 풀이는 그렇지 않다. 하나의 격자에 빛을 쏘면 내부에서 사이클을 이룬다. 내부에서 퍼지는 게 아니라 하나의 길로 쭉 들어간다고 생각해서 바로 dfs로 풀었다. bool cache[501][501][4]; cache 배열이 중요하다 cache[r][c][dir] r, c 의 격자에 dir 방향으로 들어온 적이 있는지를 체크하는 배열이다. 나는 dir 방향으로 들어온 적이 있다면 반드시 그 경우에 해당하는 사이클이 존재한다고 생각했다. 적어도 위 예제만 봐도 모든 경로를 다 탐색한다. 만약 다른 예제가 오더라도 아직 방문하지 않은 경로를 시작점으로 탐색을 하는데, 이미 탐색한 다른 경로를 건드릴일이 절대로 없다는 것이다. bool &ret = cac..

[프로그래머스] level2 튜플 (C++)

2019 카카오 겨울 인턴십 배열이 주어지고, 튜플을 만드는 방법을 문제에서 친절히 알려줬다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다. {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}} 예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는 {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 문제에서 원하는 답은 튜플을 분석해서 원래의 배열을 구하라는 것이다. 문제는 튜플이 문자열로 주어진다는 것이다.. 나는 C++..

[프로그래머스] level2 행렬 테두리 회전하기 (C++)

2021 Dev 매칭-벡엔드 2차원 좌표에서 직사각형을 정하고, 테두리를 시계방향으로 회전시키는것을 구현하는 문제이다. 완전히 구현력을 요구하는 문제이다. 삼성 A형 기출문제와 느낌이 비슷했다. 직사각형과 회전시킬 영역이 주어진다. 나는 회전을 위해서는 4개의 꼭짓점만 알면 된다고 생각했다. 그래서 주어지는 queries배열에서 4개의 꼭짓점을 추출하고, 되돌아오는 것 까지 생각해서 총 5개의 점을 vertex 벡터에 입력했다. for(auto &q: queries){ vector vertex; vertex.push_back({q[0], q[1]}); vertex.push_back({q[0], q[3]}); vertex.push_back({q[2], q[3]}); vertex.push_back({q[2]..

[프로그래머스] level2 메뉴 리뉴얼 (C++)

2021 카카오 블라인드 채용 문제를 읽어봤는데 요구사항을 한 번에 이해하지 못했다. 카카오 문제 특징인 것 같다. 지문이 너무 길다.. 그래서 처음 풀때는 시간내에 풀지 못하고 풀이만 어렴풋이 생각해둔채로 넘겼었다. 다시 풀기위해서 차분하게 풀이를 머릿속에 모두 정리하고 코딩에 들어갔다. 개인적으로 깔끔하게 풀린것같아서 마음에 드는 코드이다. 먼저 orders로 들어온 string을 오름차순 정렬하기 위해서 char로 모두 분해한 다음에 알파벳 순으로 정렬해서 2차원 벡터 형태로 만들어줬다. vector norders; for(auto str: orders){ vector temp; for(int i = 0; i < str.size(); i++){ temp.push_back(str[i..

[백준 20165] 인내의 도미노 장인 호석 C++

20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 구현, 시뮬레이션 도미노 넘어뜨리는 구현 : crash_domino() 참고 현재 넘어지고 있는 도미노 : last 곧 넘어질 수도 있는 도미노 : Map[nr][nc] 현재 넘어지는 도미노의 최대길이를 구한다. last = max(last, Map[nr][nc]) 만약 도미노가 있다면 넘어뜨린다. Map[nr][nc] = 0 nr과 nc를 현재 방향에 맞춰서 이동시킨다. 하나 넘어뜨렸으므로 현재 넘어지고 있는 도미노의 길이를 1 감소시킨다. 1 2..

[백준 14891] 톱니바퀴 C++

14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 하나의 톱니가 돌아가면 다른 톱니도 돌아가야하므로 연쇄반응을 구현해야한다. 재귀로 풀어내려고 했고 현재 바퀴를 시계/반시계 방향으로 회전시키기 전의 3시, 9시 방향의 자기정보를 가지고 있어야 한다. 현재 영향을 주는 방향을 매개변수로 입력받아서(lr) (0은 양방향, 1은 오른쪽으로, -1은 왼쪽으로) 영향을 줄 바퀴를 정해서 함수를 호출했다. 로직은 이게 전부인듯 하다. 삼성 SW기출답게 구현력을 요구하는..

[백준 14890] 경사로 C++

14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 구슬 탈출 2 문제를 풀다가 코드가 너무 길어지고.. 구현이 더러워져서 도망치듯 풀게 된 문제다. 도망쳐왔지만 이 문제도 절대 만만하진 않았다. 분명 문제에는 경사로는 서로 겹치면 안 된다고 적혀있어서 가로와 세로 경사로끼리도 겹치면 안되는줄 알았다. 그런데 알보고니 가로 경사로와 세로 경사로는 서로 영향을 주지 않기 때문에 문제가 더 쉬워졌다! 가로길 + 세로길 해주면 답이 나오게 되었다! 문제 설명이 부실한듯해서 시간을 좀 잡아먹었..

[백준 14499] 주사위 굴리기 C++

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 삼성 SW 역량 테스트 기출 문제 주사위가 굴러가는걸 내가 어떻게 아냐고.. 라고 처음에 생각했었는데 생각보다 할 만했던 문제였다 삼성 역량평가는 물체가 좌표상에서 움직이는 시뮬레이션 문제가 정말 주된 유형인듯하다 주사위가 굴러가는걸 어떻게 표현할까? 문제에 그려져 있는 주사위 평면도를 보고 풀이방법을 떠올릴 수 있었다.. 저게 없었으면 못풀었을지도 dice[i] 는 i번 면에 적힌 숫자를 의미한다..