영

https://www.acmicpc.net/problem/14244 14244번: 트리 만들기 n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오. 항상 정답이 존재하는 경우만 입력으로 주어진다. 트리는 사이클이 없는 www.acmicpc.net 트리만들기. 이번 하반기 카카오 블라인드 공채 4번문제도 트리문제이기도 했고 그래프탐색과달리 트리문제에는 약한것 같아서 이 위주로 풀어보려고 한다. 트리문제라던데 이 풀이가 맞나? 싶으면서 푼 문제. 난이도는 실버이지만 풀이가 다양해 재밌어 보이기도하고 독특해서 들고왔다. 풀이 : n은 node, m은 리프노드 갯수로 주어지는데 트리의 소소한 특성정도만 알면 '구현력'으로 풀 수 있는 문제같다...

자료구조 알고리즘/백준 2022. 10. 19. 23:14

https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2019 카카오 개발자 겨울 인턴십 마지막 5번 문제이다. 인턴십 문제라 그런지 생각보다는(?) 평이한 이분탐색 문제였다. 문제해결 길이가 20만인 stones를 순차탐색을 하지만 값이 최대 2억인 값을 기준으로 이분탐색을 진행한다. O(N*logN) 시간복잡도를 띄기에 시간복잡도 내에 통과가능하다. left = 1, right = max(stones)로 잡고 k를 기준으로 left,right를 ..

자료구조 알고리즘/프로그래머스 2022. 9. 12. 21:06

https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net https://www.acmicpc.net/probl..

자료구조 알고리즘/백준 2022. 9. 8. 11:48

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 문제해결 양방향 연결노드에 대한 정보가 주어지고 노드 a에서 b까지의 거리를 구하는 문제 방문처리는 1차원 배열로 가능하지만 a~b 까지 도달하는 각 거리를 저장하기 위해서 graph는 2차원으로 처리하였다. 완전탐색으로 dfs, bfs 둘중 한방법을 선택해도 되지만, 한 점에서 목표지점까지를 방문함에 있어서 거리를 파라미터로 넘기고싶어 dfs로 처리하였다. import sys def input(): return sys.stdin.readli..

자료구조 알고리즘/백준 2022. 8. 28. 21:10

https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 문제해결 샘터를 기준으로 삼아 -1, +1 로 이동하는 bfs 탐색을 해주고 k채의 집이 지어졌을 때 불행도의 값을 리턴한다. 이 문제는 단순한 bfs문제임을 유추하는데엔 큰 어려움이 없었지만 //==(1)==// 아래코드부분을 //==(2)==// 에 위치시켰을 때 메모리초과가 나는 문제였다. (우연히지만 틀려서 정말 다행이었다.) 이 문제 또한 창을 켜놓고 살면서..

자료구조 알고리즘/백준 2022. 8. 26. 23:01

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제 해결 문제 : 1이 들어있는 칸을 연결한 것을 모양이라 부른다. 배열 칸 하나의 수를 변경해서 만들 수 있는 모양의 최대 크기를 구하자 1을 변경하면 모양에 변화가 없으니 0을 변화시켜야 함을 알 수 있다. 배열의 한 칸의 수를 변경하여 만들 수 있는 모양의 최대 크기에서 0의 칸을 하나 변경시켜 인접한(상하좌우) 곳을 살펴서 서로 다른 영역의 크기의 합 + 1(현재칸)의 최댓값을..

자료구조 알고리즘/백준 2022. 8. 26. 22:51

https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net [백준_1953_사과나무] 골드 5 수학, greedy 기법으로 푸는 문제이다 목표로 하는 사과나무의 높이가 주어지는데 1,2의 성장세가 주어지는 성장 약으로 이 높이를 해당 조건에 충족할 수 있는지 묻는 문제이다. x : 우선 사과나무의 높이의 총합이 3으로 나누어져야 물이 동시에 주어지기 때문에 성장 속도가 1과 2가 되는 물을 주는 물뿌리개의 조건에 부합할 수 있다. 그러고 나서가 조금 까다로울 수 있는데, 목표로 하는 나무 높이들의 ..

자료구조 알고리즘/백준 2022. 8. 25. 23:35

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지..

자료구조 알고리즘/백준 2022. 6. 19. 21:43