Tempo Tempo

BFS를 이용해, 시작 좌표부터 최종 좌표까지 도달하기위한 최소 시간을 구하는 문제이다. 시작 좌표로부터 그 다음 좌표로 이동하는 방법이 총 3가지 이다. 시작 좌표를 C라고 했을 때, (C - 1, C + 1, C * 2). 따라서 시작 정점으로부터 3개의 자식 노드를 가지는 트리 형식이라고 생각하고 풀이했다. 틀렸던 점들은 주석으로 표시해두는 방식을 채택했다. 각 2차원 배열들의 역할은 map -> 방문 여부 time -> 해당 좌표에 도달하기 위한 최소 시간 이다. 첫 번째 실수는 사소한 실수였고, 두 번째 실수가 엣지 케이스에대한 실수였다. 시작 지점이 0이 아닌 수이고, 도착 지점이 0이라면 항상 -1을 이용해 도착 지점에 도달해야 한다. 하지만 양수 범위만 생각한 나머지 cur - 1 > 0 ..

BFS를 이용해 문제를 풀이했다. dx, dy는 각 좌표로부터 이동할 변화량들을 가진 배열로, 익은 토마토가 다른 토마토들에게 영향을 끼칠 때의 좌표변화를위해 사용했다. 각 2차원 배열의 역할은, tomato -> 해당 토마토가 익었는가? 익었다면 1 map -> 해당 토마토가 익기까지 걸린 시간. 처음부터 익어있었다면 0 이다. 해당 문제를 풀다가 실수했었던 점은, "처음부터 익어있었던 토마토들의 좌표를 미리 Queue에 넣어두지 않았던 점"이다. 처음 좌표부터 모든 좌표를 돌며 토마토가 익어있을 경우 BFS를 돌리면, 가장 처음으로 나온 익은 토마토를 기준으로 걸린 시간이 미리 다 정해지기 때문이다. BFS는 어차피 Queue를 이용해 FIFO 형식으로 동작하므로, Queue [익은 토마토들의 좌표]..

문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 해당 경우의 수를 1,000,000,000로 나눈 나머지를 출력하시오. 문제설명 정수 K개를 더해서 N을 만들어야 한다. d[K][N] -> "K개의 정수를 이용해 N을 만들었다" 라고 생각하자. 점화식을 구하기 위해 이전 항을 생각해보면, 정수 한 개를 빼야 하므로 d[K - 1]\[N - ?]와 같이 나타낼 수 있다. ?는 여러가지 경우가 있기 때문에 답을 구하기 전에는 알 수 없는 값으로, 이러한 수들을 반복문을 이용해 찾아주어야 한다. 따라서 d[K][N] = sum(d..

문제 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. package backjoon; import java.io.*; public class Sum_of_power { public sta..

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 44267 26509 21036 59.311% 2 x n 직사각형을 1 x 2, 2 x 1, 2 x 2 타일로 채우는 경우의 수를 구하는 문제이다. 이렇게 여러가지 방법으로 경우의 수를 구할 때는 점화식을 이용해서 푸는게 일반적이다. 각 n에대해 2 x n 크기의 직사각형을 채우는 방법의 수가 들어있는 배열을 d라고하자. d[N]에대한 점화식을 구하기 위해 아래와 같은 과정이 필요하다. d[N - 1]의 값을 임의로 구했다고 했을 때, d[N - 1]을 구한 후에는 한 줄이 남으므로 1 . 2 x 1 타일 1개로 한 줄을 채우는 경우 한 가지이고, d[N - 2]의 값을 구했다고 하면 d[N - 2]를 구한 후에는 두 줄이 남으므..

1. Hash Table 내부적으로 배열로 구현되어있다. key, value와 같이 한 쌍으로 데이터를 저장하며, key는 특정한 Hash Function에의해 결정된다. 각각의 데이터는 고유한 key를 가지고 있기 때문에, 일반적으로 탐색 시간은 O(1)만큼의 시간이 소요된다. 하지만, Hash Function이 다른 데이터에대해서 고유한 키 값이 아닌 중복되는 키값을 도출해낼 경우, 충돌이 발생하게되기 때문에 항상 탐색에대한 시간복잡도가 O(1)은 아니다. (Python에서 Dictionary, JAVA에서 Hashmap으로 구현되어있음) 1-1) Hash Function 데이터에대해서 고유한 Key값을 만들어주는 함수이다. 데이터 일부만을 사용하는것이 아닌 데이터 전체를 Hash Function에 ..

문제 설명 다른 사람들의 코드에 비해서 빠르다거나 메모리를 효율적으로 사용한 것은 아니지만, 쉽게 이해 할 수 있는 코드라고 생각하게되어 포스팅을 하게되었습니다. 기본적인 개념은, https://www.acmicpc.net/problem/14503 백준 14503번 로봇청소기로부터 따왔습니다. 알고리즘은 이렇습니다. 해당 도형을 y축 대칭시켜서 나온 모양이 원래 모양과 다르지 않다면, 동서남북 각 방향으로 도형을 그리게 되면 모든 경우의 수를 나열 할 수 있게 됩니다. 모양이 다른 경우, y축 대칭 시킨 도형에대한 메소드를 하나 더 만들어줘야 합니다. y축 대칭시킨 후에도 모양이 같은 경우(메소드 1개) y축 대칭 시킨 후에 모양이 변하는 경우(메소드 2개) ※ Y축 대칭해서 달라지는 도형들은 h와 ㄱ ..

1. Array vs Linked List Array Linked List 요소 접근 시간 O(1) O(n) 삽입, 삭제 연산 O(n) O(n) ※ Linked List의 실제 삽입, 삭제 연산 수행시간은 O(1) 이지만 삽입, 삭제 연산을 수행 할 target value를 찾기 위한 시간이 O(n)만큼 소요되므로 삽입, 삭제 연산은 O(n)의 시간복잡도를 가진다. 해당 표만 보면 Linked List 보다는 Array를 사용하는것이 시간적 이득을 가지지만, Linked List는 Tree 구조로 사용되었을 때 유용하게 사용된다. 또한 선언시에 최대 크기가 고정되어버리는 Array에 비해 Linked List는 새로운 Node를 객체로 만들어 최대 크기를 유연하게 조정 할 수 있다. 2. Stack vs..