전체 글
[백준] ACM Craft
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상정렬과 DP를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 다음과 같이 건물들을 건설하는 게임을 하는데, 특정 건물을 건설하면 반드시 승리하게 됩니다. 이 때, 건물들 간에는 우선순위(규칙)이 정해져 있습니다. 특정 건물을 짓는데 걸리는 최소 시간을 return 해야 합니다. 위 그림을 통해 간단하게 설명하면, 만약 4번건물을 짓는 최소시간을 구해야 한다면, 1->3&2->4 ..
첫 OPIC
7/9일날 첫 오픽을 보러 갔다. 한 일주일 공부해야지 하다가 책도 사면 또 돈이고 해서 그냥 안하다가 전날 부리나케 유투브에서 모의고사를 하나 풀어보고 갔다. (사실 높은 점수가 필요한 것은 아니기에...) 샤워하면서 모의고사를 들으면서 말하는데 롤플레잉? 이 나왔는데 상대방이 없는데 어떻게 하라는거지? 생각이 들어서 롤플레잉에 대해서 조금 찾아보았다. 마치 상대편의 대답이 들리는 것 처럼 알아서 연기를 하라고 했다. ㅋㅋ 아무튼 이렇게 가서 시험을 보았다. 유투브를 보다가 Survey는 이렇게 찍어야 질문이 쉽게 나온다. 이런 이야기가 있었지만, 사실 그쪽으로 Script를 외운 것도 아니고 해서 그냥 내 마음대로 골랐다. 비지니스 여행에서 당황스러웠던 경험을 말해 보아라 등의 질문은 조금 당황스럽기..
[백준] N과 M (8)
https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net python의 itertools 라이브러리를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 자연수중 중복을 허용해서 M개를 뽑을 때, 이 뽑는 경우들을 사전의 순서에 맞게 출력하면 되는 문제입니다. 단순하게 그냥 sequence를 미리 sorting 해주고, python itertools의 combinations_with_replacement를 사용하여 갯수만큼 뽑아내면,..
[백준] 공항
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 그리디 알고리즘과 분리집합을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 1~G번 게이트가 있는 공항에 비행기 P대가 옵니다. 이 때, 각 비행기는 숫자 gi를 가지는데 이 1
[백준] 외판원 순회
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 다이나믹 프로그래밍과, bit masking을 이용하는 문제입니다. 우선 문제의 핵심부터 간단하게 요약하면, N개의 도시를 임의의 도시에서 출발해서 한번씩 전부 방문하고 원래 있던 도시로 돌아오는 최소 비용을 구해야하는 문제입니다. https://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling sal..
[백준] N과 M (5)
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net Permutation(순열)을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 자연수가 주어질 때, 길이 M인 수열을 만들어 사전순으로 출력해야 하는 것이 문제입니다. 크게 어려운 점 없이 python의 경우 itertools libraray를 사용하여 permutations를 활용하면 됩니다. 이 때, 사전순 정렬을 위해 list를 미리 sorting 해주면 자동적으로 p..