IT 잣눈 IT 잣눈

C++

• [카카오 인턴] 키패드 누르기 (c++, 파이썬)

  알고리즘/프로그래머스 2022. 7. 27. 20:35

  https://school.programmers.co.kr/learn/courses/30/lessons/67256 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제풀이 전] 우선 거리계산은 숫자로 하면 될 것 같아서 * = 10, 0 = 11, # = 12로 수정해서 문제를 풀었다 문제에 나온 설명대로 코드를 짜고 거리 계산하는 법만 고민하면 쉽게 풀릴 것 같았다 거리 계산은 뭔가 규칙이 있어서 식으로 정리할 수 있을 것 같아 보다가, 이동하는 것을 아래와 같이 정리할 수 있었고 ← : -1, ↑ : -3, ↓ : +3, → : +1 이를 이용해 문제..

  Read More
• 11066 파일 합치기

  알고리즘/백준 2022. 4. 1. 00:43

  백준 11066번 파일 합치기 : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [풀이 전] 예를 들어, 40 30 30 50의 입력을 받으면 1 : 40 / 30 / 30 / 50 2 : 40 30 / 30 30 / 30 50 3 : 40 30 30 / 30 30 50 4 : 40 30 30 50 와 같은 순서로 1부터 4까지 파일 묶음의 최소 비용을 순서대로 구해가면 될 것이라 생각했다. ( ex. 3 : 40 30 30의 최소비..

  Read More
• 1260 DFS와 BFS

  알고리즘/백준 2022. 3. 25. 00:28

  백준 1260 DFS와 BFS : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [개념(간단하게 정리)] 깊이 우선 탐색(DFS, Depth First Search) : 탐색 방법 : 현재 노드에서 분기를 완벽하게 탐색 후 다음 분기로 넘어감의 반복 스택으로 구현 가능 너비 우선 탐색(BFS, Breadth First Search) 탐색 방법 : 현재 노드에서 연결된 노드를 모두 방문하면 다음 노드로 넘어..

  Read More
• 2805 나무 자르기

  알고리즘/백준 2022. 3. 23. 10:26

  백준 2805번 나무자르기 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 이분탐색으로 풀 수 있는 문제다 이분 탐색 참고 -> https://wh514.tistory.com/20 [코드 작성 전] 우선, 높이를 입력받으며 미리 나무 중 가장 높은 높이(hmax)를 저장한다. 탐색 범위를 0 ~ hmax로 설정하고 이분 탐색을 진행한다. 중간 값(cutter)를 절단기 설정 높이로 가정하고 ..

  Read More
• 6549 히스토그램에서 가장 큰 직사각형

  알고리즘/백준 2022. 3. 21. 01:14

  백준 6549 히스토그램에서 가장 큰 직사각형 : https://bit.ly/3Jtkc86 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net [코드 작성 전 정리] 우선 분할 정복으로 풀 것이기 때문에 재귀함수로 구현 필요한 것 ① 반(left, right) 나누기 return max, 높이 정보 필요 (높이는 참조로 전달) ② 합치기 left, right 중 더 낮은 높이를 기준으로 합치기 ③ 합칠 때 겹치는 부분 생각하기 겹치는 부분 기준으로 왼쪽, ..

  Read More