알고리즘 1481

[Programmers] 외벽 점검

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr weak와 dist 크기가 별로 크지 않기 때문에 단순 구현으로 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 외벽이 원형이므로 weak 벡터 크기를 두 배로 늘려 (각각의 약점 + n) 값들을 추가해줍니다. 1.1 기존 weak 벡터 사이즈를 weakSize라고 정의하겠습니다. 2. answer를 최댓값으로 설정합니다. (INT_MAX) 3. 취약지점을 모두 점검..

[Programmers] 공 이동 시뮬레이션

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 쿼리의 역순으로 계산하면 AC를 받을 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 열과 행의 범위를 나타내는 pair 변수를 선언하고 주어진 쿼리의 역순으로 진행합니다. 1.1 역순이므로 문제에서 주어진 방향은 반대가 되어야 합니다. ex) query(0, dx) -> 열 번호가 증가하는 방향으로 이동하는 쿼리로 치환 1.2 또한, 정방향으로 쿼리를 진행했을 ..

[Programmers] 카드 짝 맞추기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백트래킹과 다익스트라 알고리즘을 이용하여 푸는 문제였습니다. 두 지점을 이동할 때 최소 조작 횟수를 다익스트라 알고리즘을 통해 구하는 것이 핵심이었습니다. 4 * 4 보드판이기 때문에 백트래킹을 통해 모든 경우의 수를 구하더라도 TLE가 발생하지 않으며 보다 자세한 내용은 코드를 통해 판단할 수 있을 것이라고 생각됩니다! 개발환경: Programmers IDE 지적, 조언, 질문..

백준 15235번 Olympiad Pizza

문제 링크입니다: https://www.acmicpc.net/problem/15235 15235번: Olympiad Pizza The contestants that get a slice are, in order: 1, 2, 3, 4, 2, 4, 2, 4, 4. So at t=1s the first contestant get all slices, at t=3s the third contestant gets a slice, at t=7s the second student finishes and finally at t=9s the fourth student gets the last s www.acmicpc.net 간단한 큐 구현 문제였습니다. N의 최댓값이 1,000이기 때문에 단순 구현으로 풀 수 있는 문제..

알고리즘/BOJ 2022.08.04

[Programmers] 캠핑

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/1833 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n이 최대 5000이라 O(n^3)으로 풀 수 없는 문제라고 생각했는데 적절한 가지치기를 진행하니 AC를 받을 수 있는 문제였습니다. 사실 문제에서 주어진대로 구현을 하고 제출을 해봤는데 얼떨결에 맞은 문제라 제대로 풀었는지 잘 모르겠습니다. 알고리즘은 아래와 같습니다. 1. 우선, data 벡터를 y좌표(문제에서는 x좌표라고 칭함)를 기준으로 정렬을 했습니다. 2. 쐐기의 모든 ..

[Programmers] 호텔 방 배정

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Union Find를 이용하여 풀어야 하는 문제였습니다. k의 범위가 큰 것을 보고 이분탐색으로 접근했다가 도저히 모르겠어서 ChanBLOG님 글을 참고하여 풀 수 있었던 문제였습니다. https://chanhuiseok.github.io/posts/prog-1/ [2019 카카오 겨울인턴십] 호텔 방 배정 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io..

[Programmers] 징검다리 건너기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분 탐색을 이용하는 문제였습니다. 알고리즘은 아래와 같습니다. 1. stones 배열의 각 원소의 값이 최소 1이므로 left를 1, right를 stones 배열 내 최고 원소로 선언합니다. 2. 1번에서 구한 left와 right를 기준으로 이분 탐색을 진행하여 mid를 기준으로 조건을 성립하는지 확인합니다. 2.1 조건을 성립하면 answer를 업데이트하고 mid를 높여야..

[Programmers] 길 찾기 게임

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제에서 주어진 조건 "모든 노드는 서로 다른 x값을 가진다."이 핵심인 문제였습니다. 알고리즘은 아래와 같습니다. 1. 주어진 nodeinfo 이차원 벡터의 각 벡터에 노드 번호를 부여합니다. 2. x 좌표 기준으로 오름차순 정렬을 진행하고 3. drawTree 메서드를 통해 이진트리를 생성해줍니다. 3.1 x 좌표 기준으로 오름차순 정렬이 되어있으므로 y 좌표가 제일 큰 노드..

[Programmers] 기둥과 보 설치

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현력을 요구하는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 주어진 build_frame 벡터를 전처리하여 설치/제거 가능 여부를 판단한 뒤 set 자료구조에 추가/삭제를 해줍니다. 1.1 저는 세로를 y, 가로를 x로 처리했고 좌상단을 0, 0으로 봤기 때문에 y를 n - frame[1]로 처리한 뒤 설치/제거 가능 여부를 판단했습니다. 2. 설치 가능 여부는 문제에서 주..

[Programmers] 광고 삽입

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72414# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 슬라이딩 윈도우 기법을 이용하는 문제였습니다. 시스템 케이스 17번에서 거의 10초가 걸렸기 때문에 아슬아슬하게 통과한 코드입니다. 알고리즘은 아래와 같습니다. 1. 입출력 예 #2를 보면 01:00:00-11:00:00 : 해당 구간이 1회(2번 기록) 재생되었으므로 누적 재생시간은 10시간 00분 00초라고 주어집니다. 따라서, 주어진 광고의 범위는 사실상 [시작 시간 + ..