아무코딩

문제풀이 매우 복잡하게 푼거 같은느낌이 든 문제이다. 1. 탐색은 bfs를 사용하였고 bfs를 사용하여 계속 파이프를 따라간다. 2. 파이프가 이어져야 하는 곳에 파이프가 없을때('.' 일때) 3. 해당 위치에서 사방을 탐색하여 적절한 파이프를 기존에 저장해놓았던 map에서 반환한다. 모든 걸 넣어보고 문제없는지 확인하는 방법도 있겠지만 더 효율적으로 짜보고자 map을 활용하였다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ..

문제풀이 카카오에 블록이동과 비슷한것 같지만 다른 문제입니다. 그때는 기준을 왼쪽 위(목적지와 상대적으로 가까운 지점)를 기준으로 잡았지만 이번에는 목적지와 상대적으로 가까운 지점을 기준으로 잡습니다. 그리고 현재 방향, 다음 방향을 모두 고려하여 불가능한 케이스를 제거해주고, 다음 위치의 벽유무, 범위 체크등을 해주며 dfs를 진행해 주면 되는 문제입니다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 6..

문제풀이 위상정렬을 활용한다. 이 문제에서는 위상정렬이 성립되지 않는 경우를 생각해야된다. 위상정렬이 이루어지는 조건은 노드가 다 출력될때까지 in-degree가 0이 아닌 노드가 없는 것인데 그거 말고 이상한 방법으로 사이클 체크를 하려해서 고생을 했다. 개념에 충실하자... 추가로 위상정렬을 간략하게 설명하자면 indegree가 0인 노드를 큐에다 추가하는 방식 프린트는 물론 큐에서 하나씩. 그러면 순서가 보장된다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54..

문제풀이 c++로만 풀다가 첨으로 java로 푼 문제이다. 가장 긴 오름차순 수열을 찾는 LIS문제와 동일하다. 마지막 인덱스 접근을 위해 초기에 0을 넣어두고 사용한다. 마지막 인덱스를 size-1로 접근하는데 없으면 에러뜨기때문.. 마지막보다 큰값이 들어오면 뒤에 삽입. 작거나 같은값이 들어오면 lower_bound값을 찾아 그값과 변경한다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Baekjoon..

문제풀이 next_permutation 으로 그냥 돌리고 해당 index에서 반환하는 방식을처음 썼는데 시간초과가 났다. 효율성 문제였다. 순열의 특징을 이용하여 앞자리부터 계산해 나간다. 첫자리가 같은 경우의 가짓수는 (n-1)! 이다. 이개념을 바탕으로 아래에 코드를 작성하였다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include #include using namespace std; vector people; vector solution(int n, long long k) { vector answer; long long factorial = 1; for(i..

문제풀이 시뮬레이션 문제이다. 순열을 만드는 방법은 next_permutation() 을 써도 되지만 여기서는 그냥 dfs를 이용하여 순열을 생성하였다. 순열을 생성하여 타순을 매번 정하여 해당 타순을 기준으로 점수를 산출한다. 출루는 베이스에 1을 추가한뒤 배열을 미는 방식으로 점수를 산출한다. 1루이동을 매루에 적용하여 재사용하였다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 7..

문제풀이 너무 꼬아서 생각했다.. 내가 너무 쉬운 스도쿠만 풀었는지 확실하게 유니크한 값들을 채워나가면 공백이 줄지 알고 공백들을 계속 돌려 유니크한 1개의 값을 채워나가는 방식으로 생각했는데 예외가 너무 많았다. 고려할게 2가지 이상인게 모두일때 그 방법은 무한루프 상태가 된다. 그래서 남들 처럼 dfs 방법으로 풀었다. 자리확인은 원래 bool 배열로 해도 됐으나 그전에 짠 비트마스크 코드가 아까워 그대로 사용하였다. 하고보니 그냥 간단한 dfs문제였다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 4..

문제풀이 이분 탐색을 공부하려고 푼 문제인데 특정 공식을 알지 못해 전혀 접근 조차 못했다. 배열안에 값이 i*j일때 인덱스를 구하는 방법은 해당 수를 각 열으로 나눠 몫수가 그 열에서 8보다 작은 행의 개수이다. 만약 몫>행의수 일 경우에 행의수를 반환 나머지는 이분탐색으로 찾는다 가장 작은수는 1 가장 큰수는 n*n임을 알수있기때문. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include using namespace std; long long N; long long k; long long getMidIndex(long long ..