문제 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net dfs를 이용해 장애물 설치의 모든 경우의 수를 다 해보고 감시를 피할 수 있는지 확인하는 문제였다. (백트래킹) 문제 풀이 처음에는 빈 칸의 좌표를 따로 저장하지 않고, 상하좌우로만 이동하며 장애물을 설치했는데 비효율적인 것 같아서 빈 칸의 좌표를 map 입력받을 때 같이 저장해줬다. 그리고 엄청난 실수를 했는데, dfs에서 count+1과 i+1을 넘겨줘야 했는데 count+1과..
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net dfs를 이용해 모든 경우의 수를 다 계산해 최솟값과 최댓값을 찾아내는 문제였다. 성공 떠있길래 보니까 1년 전에 풀었던 문제였는데 푼 기억이 없고 처음 보는 문제같았다. 만약 1년쯤 뒤에 또 이 문제를 보면 처음 보는 문제같을까..? 문제 풀이 dfs를 이용해서 연산자 4개에 대해 모든 경우에 다 적용해주었고, 종료 조건에 도달했을..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 순서에 따라 괄호를 올바르게 바꾸는 문제였다. 그냥 시키는대로 따라서 코드를 작성하기만 하면 됐다. 풀이 방법 4번째 순서에 대한 코드를 작성할 때, u의 괄호를 반대로 저장하는 부분을 u를 뒤집어서 저장하도록 만들어서 조금 헤맸다; 이런 실수는 대체 왜 하는걸까? 집중력의 문젠가? 졸리긴 했음; #include #include #include using namespace std; b..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr command 리스트에 따라 주어진 조건에 맞게 기둥과 보를 설치/해제하는 문제였다. 조건 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다. 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다. 문제 풀이 처음에 문제를 잘못 이해해서 다시 풀었다... 보의 양 끝이 하나의 보를 말하는게 아니라 ..
문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 사과를 먹으면 몸이 길어지는 뱀을 이동시키면서 자신의 몸에 닿거나 벽에 닿으면 종료되는 게임의 끝나는 시간을 구하는 문제였다. 문제 풀이 뱀의 머리가 먼저 이동하고 꼬리와 닿는지 확인 후에 꼬리를 이동해야 했고, 범위 지정을 N보다 클 때만 break하도록 했는데 이부분을 나중에 깨달아서 시간이 조금 걸렸다. 전체 map이 있고, 사과가 있다면 2, 뱀이 있으면 1, 아무것도 없으면 0으로 지정했다..
문제 구현 문제로 NxN 자물쇠를 MxM 열쇠로 푸는 문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 두 번에 걸쳐 문제를 풀었는데 처음에는 열쇠를 4번 회전하고, 각각의 상황에서 dfs를 이용해 한 칸씩 옮겨가며 unLock을 확인해 주도록 구현했는데 시간 초과로 인해 60점이 나와서 다른 방법으로 다시 풀었다. dfs보다 훨씬 간단한 방법이었는데, N+(2*M) 사이즈의 비교용 map을 만들어 가운데에 자물쇠를 놓고 열..
서로소 집합(Union-find), 크루스칼 알고리즘(최소 신장 트리), 위상 정렬과 관련한 문제들이다. 각 알고리즘의 설명 및 구현은 따로 올릴 것이다. 팀 결성 팀 합치기, 같은 팀 여부 확인 연산을 하는 문제로 Union-Find 방법을 이용해 푸는 문제였다. 0번 연산이 union을 만드는 연산, 1번 연산이 같은 parent를 가지는지 확인하는 연산이었다. 각각에 대해 makeUnion, findParent 연산을 만들어서 해결했다. int parent[100001] = { 0 }; int find_parent(int a, int b) { //항상 a
최단 경로 알고리즘은 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있는데 이를 각각 구현하는 포스트는 다음에 올리겠다. 한 지점에서 특정 지점까지의 최단 경로를 구할 때에는 다익스트라를, 모든 지점에서 모든 지점까지의 최단 경로를 구할 때는 플로이드 워셜을, 다익스트라와 같은 경우지만 음의 가중치를 가진 간선이 존재할 경우 벨만 포드 알고리즘을 사용하면 된다. 미래 도시 방향이 없고 가중치가 없는 그래프로 1번 회사에서 K번 회사로, K번 회사에서 X번 회사로 가는 최단 경로를 구하는 문제였다. 나는 이 문제를 1번부터 K번, K번부터 X번까지의 최단 경로를 다익스트라를 이용해 구한 후 두 개의 값을 더해서 풀었는데 책에서는 전형적인 플로이드 워셜 유형의 문제라고 했다. 노드와 간선의 개수가 100..
