문제 https://school.programmers.co.kr/learn/courses/30/lessons/1831 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N을 만들 수 있는 경우의 수를 구하는 문제였다. *++이 3단고음이고 *은 3을 곱하기, +는 1을 더하기이다. 3단고음 중간에 3단 고음을 실행할 수 있다. 문제 풀이 처음에 1에서 시작해 N을 만드는 방법으로 했는데, 시간 초과가 계속 났고 풀이를 참고해서 다시 풀었다.. N부터 시작해서 1까지 도달하게 했고, *는 3으로 나누기, +는 3으로 나눈 나머지를 빼도록 했다. 3으로 나눠진다..
문제 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 트리의 기둥 길이(루트~기가)와 가장 긴 가지의 길이(기가~리프)를 구하는 문제였다. 문제 풀이 처음에는 단순하게 size가 2보다 작은 노드가 나올 때까지 dfs를 돌려 기가 노드를 구하고, 기가 노드에서부터 각 노드들까지 dfs를 돌려 가장 긴 가지의 길이를 구하려고 했다. ..
문제 https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 치르보기 빌딩의 엘리베이터 디스플레이의 숫자를 변경할 수 있는 경우의 수를 계산하는 문제였다. 아래는 각각의 숫자가 보이는 방식이다. 문제 풀이 0~9까지의 숫자들의 7개의 표시등을 모두 저장하고 각각의 숫자가 다른 숫자로 바뀔 때 필요한 반전 횟수를 계산해 저장했다. 그리고 숫자를 변경할 때 K자리의 LED이기 때문에 12라는 숫자를 0012라고 표기해야 하기 때문에 string 으로 변환해준 후, 백트래킹을 하며 앞자리부터 계속해서 바꿔줬다. 처음에 아무리 생각해도 로직상 ..
문제 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 왼쪽부터 계산하는 수식에 괄호를 추가해 식의 최댓값을 구하는 문제였다. 문제 풀이 처음에 이 문제를 굳이 그리디로 풀려고 시도하다가 조건이 너무 많아져서 실패했다. 그냥 dfs로 푸니까 쉽게 해결됐다.. dfs를 할 때, 다음 연산을 바로 하는 경우와 다음 숫자와 다다음 숫자가 다다음 연산을 먼저 하는 경우로 나뉘게 하면 된다. #define _CRT_SECURE_NO_WAR..
문제 https://www.acmicpc.net/problem/23747 23747번: 와드 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다. 지나온 경로를 모두 시야로 확보하지는 않는다. www.acmicpc.net 여행 기록을 입력받아 맵에서 이동하고, 기록이 W일 경우에 같은 구역의 시야를 밝힌 후 모든 여행이 끝난 후의 맵의 시야를 출력하는 문제였다. 문제 풀이 입력받은 방향대로 이동하다가 W가 나오면 dfs를 호출해 같은 구역(같은 문자)인 곳을 탐색해줬다. 마지막에 이동한 곳과 그 위치의 상하좌우까지 방문처리 해준 후, isVisit 값이 true면 .을 false면 #을 출력했다. #define _CRT_SECURE_NO_WARNINGS..
문제 https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 그래프를 2가지 색으로 색칠하는 문제였는데, 서로 연결된 두 노드를 다른 색으로 칠할 수 있는지의 여부를 구하는 문제였다. 문제 풀이 그래프를 만들고 dfs로 모든 노드를 탐색하면서 색을 바꿔주면서 풀었다. dfs 현재 노드가 아직 색칠이 되지 않았으면 1로 색칠해준다. 현재 노드와 연결된 노드들을 탐색한다 다음 노드의 색이 없으면 방문 전이기 때문에 현재 노드 색과 다른 색으로 칠해주고 방문한다. 다음 노드의 ..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그래프에 있는 도넛, 막대, 8자 그래프의 개수를 구하는 문제였다. 문제 풀이 사실 카카오 코딩테스트를 풀 때 이 문제는 시간이 없어서 덜 푼 문제였었다. 그때도 진입 노드를 저장해 진입 개수가 0인 곳이 root라고 생각은 했었는데, 풀다가 시간이 다 가버렸다.. 먼저 edges를 돌며 그래프를 만들고, 그래프를 만들면서 in에 각 노드의 진입 개수를 저장했다. 처음에는 진입 노드가 0이..
문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프를 맵의 마지막 위치로 옮길 수 있는 경우의 수를 구하는 문제였다. 문제 풀이 dfs로 완전탐색을 해서 풀 수 있었다. 처음 풀이 (고쳐서 맞추긴함) 문제를 풀다 시행착오가 2번 정도 있었다; 처음엔 문제를 제대로 읽지 않고 항상 3방향으로 갈 수 있는 상황이라 생각하고 풀어서 테케가 다 맞지 않았다. 그 다음에는 lx,ly,rx,ry를 넘겨 pipeDir를 구..
