문제 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 재귀함수를 이용해 출력하는 문제였다. 문제 이런 문제는 좀 킹받는다 출력을 잘 살피면서 풀어야겠다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exce..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 모든 bit가 0인 초기화 상태에서 입력값으로 주어진 상태로 만들기 위해 고쳐야 하는 최소 횟수를 구하는 문제였다. 문제 풀이 단순히 0의 값과 1의 값을 구해 더 적은 횟수가 정답인 줄 알았는데, 현재 bit를 변경하면 현재 위치부터 맨 끝까지 해당 bit로 덮어씌워지는 문제였다. 현재 값을 초기 상태인 0으로 지정하고, 메모리 bit의 맨 앞부터 순회하면서 다른 수가 나오면 다음 수로 변경..
문제 https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 그래프를 2가지 색으로 색칠하는 문제였는데, 서로 연결된 두 노드를 다른 색으로 칠할 수 있는지의 여부를 구하는 문제였다. 문제 풀이 그래프를 만들고 dfs로 모든 노드를 탐색하면서 색을 바꿔주면서 풀었다. dfs 현재 노드가 아직 색칠이 되지 않았으면 1로 색칠해준다. 현재 노드와 연결된 노드들을 탐색한다 다음 노드의 색이 없으면 방문 전이기 때문에 현재 노드 색과 다른 색으로 칠해주고 방문한다. 다음 노드의 ..
문제 https://www.acmicpc.net/problem/14629 14629번: 숫자 조각 곧 7살을 맞이하는 준하는 유치원에서 숫자가 적힌 나무 조각들을 가지고 노는 것을 좋아한다. 숫자 조각은 총 10개이며, 각각의 조각엔 0부터 9까지의 숫자가 한 숫자씩 적혀있다. 준하는 각 숫 www.acmicpc.net 준하가 수포자가 되지 않도록 0~9까지의 숫자를 한 번만 사용해 입력받은 숫자 N과 가장 차이가 적은 숫자를 구하는 문제였다. 문제 풀이 그리디로 풀면 될 것 같아서 그리디로 풀었다. 근데 백트래킹으로 푸는게 정신 건강에 더 좋을 것 같다. 처음에는 long long으로 N을 입력받고, int 배열에 각 자리를 저장해줬었다. 문제를 풀다가 string으로 받게 하는게 더 간단한 것 같아서..
문제 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를 구..
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 서로 붙어있지 않은 스티커를 골라 가장 높은 점수를 구하는 문제였다. 문제 풀이 N이 100000이라 완전탐색으로 풀면 시간 초과가 날 것 같아서 dp로 풀었다. 처음에 예시만 보고 점화식을 만들어 풀었더니 틀렸다고 나와서 반례를 찾아 점화식을 수정했다. 0 : 50 1 : 100 50+50 vs 10 -> 100 2 : 200 100+100 vs 50+70 -> 200 3 : 2..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 복구에 가장 적은 시간이 드는 경로를 찾아 최소 시간을 구하는 문제였다. 문제 풀이 처음에 당연히 int로 입력될 것이라 생각하고 했더니 입력에서 오류가 나서 당황했다. 문제를 자세히 보니.. string으로 입력을 받아야 해서 굳이 이렇게..? 라는 생각을 하긴 했지만 바꿔서 입력받았다. 우선순위 큐를 이용해 걸리는 시간이 짧은 곳부터 방문하도록 했다. 처음에는 메모리 limit을 넘었다는 ..
