본문 바로가기

Archived(CSE Programming)

 (169)
프로그래머스_등굣길 https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 | 프로그래머스 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매 programmers.co.kr 해당 문제는 DP 문제였다. 목적지 까지 최소 경로의 개수를 구하는데, 바로..
프로그래머스_가장 먼 노드 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 해당 문제는 그래프 내에서 정점 1로부터 가장 멀리 있는 노드들의 개수를 구하는 문제였다. 나는 BFS를 통해 탐색하면서 가장 멀리 있는 노드들의 수를 계산하는 방식으로 처리하였다. 이 때, edge들이 양방향이라는 문제 조건에 맞춰 반대 방향의 edge들도 추가해주었다. 그리고 pair를 활용해 현재 방문중인 index와 1로부터의 거리를 함께 queue에 저장하여 처리하여서 손쉽게 해결할 수 있었다. (해당 문제..
프로그래머스_여행경로 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 | 프로그래머스 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 문제 자체는 dfs로 경로를 탐색하며 전개하면 되는데, 알파벳 정렬 순으로 진행되어야 하기에 정렬이 필요하다. 그런데, 문제 조건에서 애매한 부분이 있는데 ["ICN", "BOO"], ["ICN", "BOO"] 와 같이 동일한 티켓이 두번 주어졌을 경우에 어떻게 처리해야 하는가 이다. 예제 테스트 케이스에서는 동일 티켓을 제외하고 처리하는게 맞다고 처리되는데 실제 채점..
프로그래머스_디스크 컨트롤러 https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 programmers.co.kr 처음 문제를 처리할 때는 작업을 처리하고 작업이 끝나는 시점까지 넣..
프로그래머스_단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 | 프로그래머스 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> programmers.co.kr 해당 문제는 DFS로 해결하였다. 기본적인 DFS였으나 그냥 DFS를 돌..
프로그래머스_ 정수 삼각형 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 | 프로그래머스 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 삼각형을 타고 내려오면서 가장 큰 경로 값을 가져올 경우를 찾는 문제였다. 기본적인 DP로, 이전 경로에서 가장 큰 값에다 현재 경로 중 가장 큰 값을 더해주는 방식으로 경로를 확장해나가면서 해결할 수 있었다. 단, 삼각형의 둘레변 부분에서는 무조건 둘레변에서만 내려올 수 있으므로 이 부분들은 예외적으로 따로 처리해줬다. #include #include #include using namespace std; int solu..
프로그래머스_단속카메라 https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 | 프로그래머스 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 처음 풀이를 생각했을 때는 3 가지 경우를 생각했었다. 범위 내에 감싸고 있을 경우, 최소 지점과 만날 경우, 최대 지점과 만날 경우 저런 식으로 3 가지 경우를 생각하여 코드를 구현하였는데 계속 틀렸었다. 생각해보니, 저런식으로 bound를 줄여나가면 예전에 줄였던 경우에서 커버가 가능한 경우가 있을 수 있었다(말이 굉장히 어색하고 어려운데, 어쨋든 Routes간의 순서에 따라 값이 달라져버리게 될 수 있었다는 뜻이다). 밑의 코드는 처음 생각했던 ..
프로그래머스_타일 장식물 https://programmers.co.kr/learn/courses/30/lessons/43104 코딩테스트 연습 - 타일 장식물 | 프로그래머스 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다. 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1 programmers.co.kr 간단한 DP 문제였다. 다음 타일의 크기를 구하는 과정은 피보나치 수열..

티스토리툴바