본문 바로가기

알고리즘 문제풀이259

[백준 3190] 뱀 (C++) https://www.acmicpc.net/problem/3190 구현그 snake 게임? 생각하면 될 듯N * N 보드에서 길이 1짜리 뱀으로 시작해서 한칸씩 늘리면서 이동하면서도처에 위치한 사과들을 먹으면 길이가 +1 되고, 못 먹으면 길이가 유지되는 (그래서 꼬리가 이동함 - 사라짐)입력으로는 사과의 위치와 S초후에 바뀌는 방향이 주어진다.-> 머리의 방향을 바꿔가면서 한칸씩 이동하는 스네이크 게임~종료 조건: 벽에 닿거나, 본인과 본인의 머리가 부딪힐 경우 접근방법구현문제여서 시뮬레이션으로 풀었다.- 정사각보드 구성: 2차원배열로 격자판을 만들어 놓고, 빈칸은 0, 뱀은 1, 사과는 2로 설정했다.- 뱀의 이동 방향: 오른쪽, 아래, 왼쪽, 위 순서대로 방향 배열 선언해둠 (dr, dc), 왼쪽으.. 2024. 6. 20.
[백준 1620] 나는야 포켓몬 마스터 이다솜! (Swift) https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 제목부터 킹받는 문제다 지하철에서 문제를 열심히 읽었는데 본문 전체가 문제 푸는데에는 영향을 주지 않는 빌드업이었다 ^_^ 문제를 읽기 전에 이 블로그를 먼저 보는 사람은 없겠지만 혹시 운 좋은 어떤 사람이 문제도 보기 전에 이 블로그를 먼저 봤다면 문제 설명 부분에서 오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가.. 2022. 6. 12.
[프로그래머스] 이중우선순위큐(C++) https://programmers.co.kr/learn/courses/30/lessons/42628?language=cpp 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr Heap 큐에 입력받은 숫자를 넣는 명령, 최댓값을 빼는 명령, 최솟값을 빼는 명령 들을 수행한 후에 큐에 남아있는 최댓값과 최솟값을 차례로 출력하는 문제 접근 방법 최대힙과 최소힙을 둘 다 사용해서 풀어야 하는 문제이다. 여기까지는 알겠는데 최대힙에서 top을 제거할 때 최소힙에 남아있는 수는 어떻게 하나..가 문제였다. (반대의 경우도 마찬가지) 손으로 여러번 시뮬레이션 해본 결과 최종적으로 최대힙의 top이 이미 최소힙에서 제거된 원소라면 큐에 남아있는 원소가 없음을 의미한다.는 것을 깨달았다. 따라서 실제로 .. 2022. 4. 30.
[프로그래머스] 디스크 컨트롤러 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42627#qna 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr heap 이지만 정렬로만 풀은 문제.. 시뮬레이션이라고 하는게 더 맞지 않나..싶은 왜 이곳에 heap을 써야하지..싶은..문제였달까 접근 방법 최종 종료 시간을 앞당기는게 문제가 아니라 대기시간+처리시간의 평균을 줄이는게 목적이다. 즉 대기시간을 줄이는게 문제의 목적임 SJF : shortest job first 대로 풀면 될 것 같은 문제이다. .. 2022. 4. 29.
[프로그래머스] 징검다리 (Swift) https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 징검다리~! 각기 다른 간격으로 배치되어 있는 징검다리들 중 n개를 제거했을 때 간격의 최솟값들 중에 가장 큰 값을 반환하는 문제 접근방법 이번에는 이분탐색의 범위까지는 접근했지만 탐색하는 기준을 뭐로 해야할지 모르겠어서 블로그 탐색 후 힌트를 얻었다..ㅎ 모르겠으면 이렇게라도 배워야지..! 이분탐색 범위는 이번에도 역시 결과값의 범위다. 0~간격의.. 2022. 4. 20.
[프로그래머스] 입국심사 (Swift) https://programmers.co.kr/learn/courses/30/lessons/43238?language=swift 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 이분탐색 접근방법 어떤 것을 이분탐색 해야할지 찾아내는 게 어려운 문제였다. 이분탐색은 수들이 정렬되었다는 가정하에 적용할 수 있는 방법이라는 점을 주의해서 풀이하면 조금이나마 빨리 해결방법을 찾을 수 있지 않을까 싶다. 쨌든 도저히 모르겠어서 검색해서 힌트를 얻었다. 이 문제의 핵심은 심사하는데 걸리는 총시간을 기준으로 이분탐색을 진행.. 2022. 4. 19.
[프로그래머스] 카펫 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 완전 탐색 카펫 문양의 규칙은 테두리 한줄은 brown으로 칠하고, 그 안쪽은 모두 yellow로 칠하는 것이다. brown으로 칠해진 칸의 개수와 yellow로 칠해진 칸의 개수가 주어지면 카펫의 가로와 세로 길이를 담아 반환하는 문제 접근방법 처음에는 brown 개수와 yellow 개수를 합한 것이 카펫의 넓이니까 해당 넓이를 만족하는 가로,세로 쌍을 구.. 2022. 4. 15.
[프로그래머스] 가장 큰 수 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42746?language=swift 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 정렬 정수 배열이 주어지면 이들을 적절히 순서를 변경하고 이어 붙여서 만들 수 있는 수 중에 가장 큰 수를 구하는 문제이다. 접근방법 처음에는 큰자리수의 숫자가 큰 것 순으로 정렬하려고 했는데 글자수길이가 상이할 경우 조건을 만족시키는 로직은 찾기 어려웠다. 찾아보니까 그.. 2022. 4. 13.
[프로그래머스] 여행경로 (Swift) https://programmers.co.kr/learn/courses/30/lessons/43164?language=swift 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr BFS/DFS 출발지와 도착지를 담은 비행기티켓들이 2차원 배열로 주어지면 모든 티켓을 한번씩 사용하는 여행 경로를 구하는 문제 (단 여러 경로가 있을시 알파벳이 더 빠른 경로가 우선) 접근방법 DFS로 풀지 BFS로 풀지 고민하다가 BFS로 풀었는데 다들 DFS로 풀었네.. 이 문제는 BFS가 시간 .. 2022. 4. 8.
728x90

티스토리툴바