chldkato

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net dfs + dp로 목적지까지 도착할 수 있는지 검사한다 루프를 방지하기 위해 방문 확인 배열 c를 -1로 초기화하고 이동할 때마다 0으..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net n이 1인 경우와 2인 경우를 기본값으로 설정해둔다 3부터는 다음 세가지 경우 중 최대값으로 설정 1. 세번째 포도주를 마시지 않는경..

https://programmers.co.kr/learn/courses/30/lessons/49190 코딩테스트 연습 - 방의 개수 | 프로그래머스 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 1. 방문한 좌표와 이동경로를 key로 하는 dict를 2개 만들고 방문하면 1로 저장한다 2. 왔던 경로를 반대로 돌아가는 경로를 고려하여 경로를 저장하는 dir에 반대방향으로 이동하는 경로도 체크 3. X 자로 교차하여 방을 만드는 경우를 고려하여 한번 이동할때 2칸씩 이동 이렇게 하면 X자로 교차되는 지점의 좌표를 지정할 수 있다 4. 다음 좌표가 이전에 방문한 적이 있고 이동한 적 없는 경로라면 방을 만들게 되므로..

https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 | 프로그래머스 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 1. 로봇이 있는 처음 두 칸의 좌표 [[0, 0], [0, 1]]을 큐에 넣고 bfs를 실행한다 2. 방문했는지 체크하는 배열에도 위와 같은 형식으로 두 개의 좌표를 묶어서 넣어준다 3. 현재 큐의 길이만큼 실행한다. 이렇게해야 현재 좌표에서 가능한 모든 이동, 회전을 하고 cnt를 증가할 수 있다 4. 각 좌표가 dx, dy에 따라 이동할 수 있는지 검증한다. 5. 두 좌..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계 www.acmicpc.net 1. disjoint-set으로 입력의 왼쪽을 부모로 하는 집합을 만들어준다 2. union에서 부모를 설정할 때 네트워크의 크기도..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 플로이드-와샬로 모든 경로를 구해놓고 여행 경로가 가능한지 출력 import sys INF = sys.maxsize input = sy..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 1. 집합 n+1개를 만들고 자기자신을 부모로 설정한다 2. z가 0이면 앞의 숫자를 부모로 하는 disjoint-set 실행 3. ..

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net 처음에는 check 함수에서 이중 반복문을 써서 모든 수와 비교해야한다고 생각했다 다시 생각해보니 check 함수 전에 정렬을 하기 ..