post-thumbnail

[BOJ] 2263 - 트리의 순회 (C++)

트리의 순회img솔직히 처음 접하자마자 풀기에 쉽지 않은 문제다. 이전에 리트코드에서 풀었던 기억이 있어 접근하는데 유리했다. 중위, 후위순회의 값을 알고 있기 때문에 우리는 어떤 노드가 루트 노드인지 알 수 있고 중위순회 값과 비교해 왼쪽, 오른쪽을 구별할 수가 있다

약 3시간 전
·
0개의 댓글
post-thumbnail

[BOJ] 1167 - 트리의 지름 (C++)

트리의 지름img이전에 풀었던 트리의 지름 문제와 유사해서 다시 풀었다. 입력의 형태만 다르고문제 접근이나 코드는 비슷하다.

약 3시간 전
·
0개의 댓글
post-thumbnail

[BOJ] 1967 - 트리의 지름 (C++)

트리의 지름지름을 구하기 위해서 한 노드에서 리프노드까지 도달하는 값의 합을 모두 살펴보았는데 이런 경우 시간초과가 발생하였다. 그래서 이 문제는 다른 분이 정리한 것을 참고하였다. 트리의 지름을 구하는 문제는 풀이법이 알려진 문제라고 한다. 이 풀이법을 근간으로 코드

약 3시간 전
·
0개의 댓글
post-thumbnail

[BOJ] 5639 - 이진 검색 트리

이진 검색 트리img전위 순회는 루트노드, 왼쪽, 오른쪽으로 순회하는 방식이고, 후위 순회는 왼쪽, 오른쪽, 루트 노드로 순회하는 방식이다. 따라서 전위 순서의 첫번째 원소는 루트 노드인 것을 알 수 있고 BST이기 때문에 왼쪽에는 루트보다 작은 값들만 나오는 것도 알

약 3시간 전
·
0개의 댓글
post-thumbnail

[BOJ] 9465 - 스티커 (C++)

스티커img한 스티커를 사용하게 되면 주변 상하좌우의 스티커를 사용하지 못한다는 조건을 더 생각할 필요가 있었다. 2행 n열로 구성되기 때문에 아래와 같은 선택지들만 존재하는 것을 알 수 있다. img2살펴보게 되면 1열의 원소들은 둘 중 하나 반드시 선택하게 되고 이

약 3시간 전
·
0개의 댓글
post-thumbnail

[BOJ] 5582 - 공통 부분 문자열 (C++)

공통 부분 문자열img이 문제는 전형적인 LCS(Longest Common substring) 이다. 진행 과정은 다음과 같다.현재 두 문자가 같을때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만

2022년 1월 18일
·
0개의 댓글
post-thumbnail

[BOJ] 14716 - 현수막 (C++)

현수막img굉장히 전형적인 dfs문제였다고 느꼈다. 다른 점이 있다면 상하좌우 뿐 아니라 대각선까지 총 8방향을 살펴야 했던 점이다. 살펴보면서 dfs로 살핀 영역의 개수를 카운트하면 글자 수가 나오게 된다.

2022년 1월 15일
·
0개의 댓글
post-thumbnail

[BOJ] 11722 - 가장 긴 감소하는 부분 수열 (C++)

가장 긴 감소하는 부분 수열img먼저 dp의 값을 1로 초기화 하고 이전 값들을 살펴보면서 값을 갱신시켜 주었다. 현재 값을 이전 감소 수열에 이을 수 있는지 확인하기 위해 두 값을 비교하고 dp 값을 dpi와 dpj+1 을 비교해서 갱신해준다. 중간에 위치한 값이

2022년 1월 15일
·
0개의 댓글
post-thumbnail

[BOJ] 11725 - 트리의 부모 찾기 (C++)

트리의 부모 찾기img한 노드의 인접한 노드는 자식이거나 부모일 것이다. 트리의 루트는 1로 정해져 있으니 루트부터 bfs탐색을 하면서 나오게 되는 노드들은 현재 노드의 자식일 것이다. 이를 up에 저장하여 노드의 부모를 가리키게 하였다.

2022년 1월 13일
·
0개의 댓글
post-thumbnail

[BOJ] 3067 - Coins (C++)

Coinsimg사실 동전 문제의 경우 어느 정도 정형화 된 것 같다.금액 0의 경우 1가지의 경우의 수이므로 arr0 = 1로 초기화를 해주었다. 현재 금액을 기존 금액에서 특정 동전을 추가로 사용했을 때 만들 수 있는지, 그 가짓수를 세주면 되기 때문에 모든 동전에

2022년 1월 13일
·
0개의 댓글
post-thumbnail

[BOJ] 21278 - 호석이 두 마리 치킨 (C++)

호석이 두 마리 치킨img일단 N의 최대 값이 100 이고 특정 도시를 거쳐 다른 도시로 이동할 때의 최소 값을 구해야 하기 때문에 플로이드-와샬 알고리즘이 떠올랐다. 결과적으로 답은 배열의 맨 앞에 위치하게 된다.

2022년 1월 11일
·
0개의 댓글
post-thumbnail

[Leetcode] 1022. Sum of Root To Leaf Binary Numbers (C++)

1022\. Sum of Root To Leaf Binary Numbersimg루트 노드부터 리프 노드까지 가서야 어떤 이진수 인지 확인할 수가 있다. 따라서 리프 노드에 도달 했을 때의 값을 반환해야 한다고 생각했고 이에 따라 그때까지 값을 유지해야 한다고 생각했다.

2022년 1월 11일
·
0개의 댓글
post-thumbnail

[BOJ] 7569 - 토마토 (C++)

토마토img1img2기존에 풀었던 토마토 문제에서 한 차원이 늘어난 형태이다. 따라서 인접한 4개의 위치만 살피던 이전 문제와 다르게 위, 아래도 살펴야하는 부분이 달라졌다. 이전 문제를 풀었다면 충분히 풀만한 문제였다고 생각한다.

2022년 1월 11일
·
0개의 댓글
post-thumbnail

[BOJ] 1012 - 유기농 배추 (C++)

유기농 배추img배추가 있는 부분에 벌레가 최소 하나씩 있으면 된다. 따라서 인접하게 위치하는 배추 군락(?)을 찾아주면 된다. 이를 위해 dfs 탐색을 했다. 방문했던 배추 위치는 다시 방문하지 않기 위해 visited 배열을 사용했고 한 군락을 발견할 때마다 개수를

2022년 1월 11일
·
0개의 댓글
post-thumbnail

[BOJ] 11047 - 동전 0 (C++)

동전 oimg이 문제는 동전의 개수가 무한대이기 때문에 현재 사용할 수 있는 금액의 최대 개수를 사용하면 된다. 따라서 금액을 역순으로 살펴보면서 현재 남은 K보다 작은 경우에 한해 개수를 세고 금액을 감소시키면서 답을 찾으면 된다.

2022년 1월 11일
·
0개의 댓글
post-thumbnail

[BOJ] 15681 - 트리와 쿼리 (C++)

트리와 쿼리img각 노드를 기준으로 그 노드를 루트로 하는 서브 트리에 속한 노드의 개수가 몇 개인지 저장하려고 했다. 이를 위해 주어진 루트노드를 기준으로 dfs를 수행하였고 이때 부모 노드는 개수에 들어가지 않게 하기 위해 visited 배열을 사용하였다. 방향성이

2022년 1월 9일
·
0개의 댓글
post-thumbnail

[BOJ] 2502 - 떡 먹는 호랑이 (C++)

떡 먹는 호랑이img첫째날의 떡 개수를 a, 둘째날의 떡 개수를 b라고 생각하였다. 이를 바탕으로 각 날짜 별로 주게 되는 떡의 개수를 계산한다면 m\*a + n\*b개가 된다. 따라서 우리가 D일차 떡의 개수를 통해 a, b에 들어갈 수 있는 값을 알기 위해서는 각각

2022년 1월 9일
·
0개의 댓글
post-thumbnail

[BOJ] 13241 - 최소공배수 (C++)

최소공배수img최소공배수를 구하기 위해서 최대공약수 gcd를 먼저 구하였다. 이는 유클리드 호제법을 이용하여 재귀함수를 통해 구할 수 있었다. 또한 최대공약수를 아는 상태에서는 최소공배수 lcm는 a\*b/gcd(a,b) 와 같기 때문에 쉽게 구할 수 있었다.https

2022년 1월 9일
·
0개의 댓글
post-thumbnail

[BOJ] 7576 - 토마토 (C++)

토마토img먼저 익은 토마토가 어디에 있는지 확인하는 것이 중요하다. 이를 위해서 전체를 순회해서 찾을 것인지, 익은 토마토만 따로 관리해 살펴볼 것인지가 시간초과를 나누는 부분인 것 같다. 따라서 큐에 익은 토마토만 넣어서 관리하면서 익어가는 날짜를 저장하고 큐가 빌

2022년 1월 9일
·
0개의 댓글
post-thumbnail

[BOJ] 2644 - 촌수계산 (C++)

촌수계산img부모-자식 관계이기 때문에 트리 관계라고 생각할 수 있다. 또한 이 트리 안에서 특정 노드를 찾기 위해 아래로, 위로 모두 이동할 수 있어야 한다. 따라서 양방향 연결로 저장하였다. 이를 가지고 재귀함수를 통해 촌수 찾을 다른 하나의 번호를 찾아 나섰고 방

2022년 1월 9일
·
0개의 댓글