![]()
문제 풀이 1부터 N까지의 노드가 있고, 1에서 N까지 가는 최단 거리를 찾는 문제와 동일하다. 다익스트라를 사용하여 최단 거리를 구해주었다. 코드 import sys from heapq import heappop, heappush input = sys.stdin.readline INF = 1e9 def dijkstra(graph, n): hq = [(0, 1)] distance = [1e9] * (n + 1) distance[1] = 0 while hq: dist, cur = heappop(hq) if dist > distance[cur]: continue # 예외 처리 for weight, next_node in graph[cur]: next_dist = dist + weight if next_dis..
![]()
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 첫번째 플레이어가 돌을 뒀을때 이겼는지 판별하는 문제이다. 빈 칸에 첫번째 플레이어의 돌(X)을 두고, 가로,세로,오른쪽아래로 향하는 대각선, 왼쪽아래로 향하는 대각선 으로 나눠서 이기는 조건인 XXXXX가 존재한다면 1을 출력하면 될 것이다. 대각선을 생각하는 것이 조금 어려웠는데, 왼쪽아래로 향하는 대각선은 열기준으로 작아지는 방향, 행기준으로는 커지는 방향이다. 그런데 찾는..
![]()
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 ..
beginning 에서 target 으로 가려고 한다. 우선 바꿔져야 하는 곳을 1로 표현해보면 아래와 같이 change_spot을 만들 수 있다. change_spot을 만들어보면 특징을 볼 수 있는데, 행 별로 서로 같거나, 반전된 비트이다. 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 이를 우선적으로 체크해서 만약 같거나 반전되지 않는 경우가 있다면 -1을 return 하고, 그렇지 않다면 된다는 가정 하에 최소 경우의 수를 찾는다. def solution(beginning, target): answer = 0 row = len(beginning[0]); col = len(beginning) #열, 행 change_spot = [['0' for _ in ..
![]()
문제설명 https://www.acmicpc.net/problem/15351 코드 n=int(input()) for i in range(n): m=input() m=list(m) sum=0 for j in m: if j==" ": continue #print(n) else: scores=ord(j)-64 sum+=scores if sum==100: print("PERFECT LIFE") else: print(sum) 문제풀이 1)값을 입력받는다 2)공백은 넘어가면서 대문자를 아스키코드 번호로 변환해주는 반복문을 작성한다 3)이렇게 문자열에있는 문자들의 아스키코드 번호값을 모두 더해준다 4)100점인 경우에는 perfect life 그렇지 않은경우에는 점수를 출력하는 조건문을 작성한다
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제요약 격자에 바이러스가 위치한 좌표, 벽의 좌표가 표시되어있다. 벽을 3개 세워서 바이러스가 퍼지지 않는 곳의 최대넓이를 구하라. 문제해결 시뮬레이션 단계에 따라 각각 그래프 순회를 해야한다. 먼저 주어진 격자의 정보를 입력 받고, 벽을 3개 세울 때는 원본정보가 변하지 않게 다른 격자에다가 복사를 한 뒤 시뮬레이션을 한다. 벽을 시뮬레이션할 때는 DFS를 적용하였다. 벽을 다 세운뒤에는 바이러스 확산을 ..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 유형 그래프 탐색 (DFS(깊이 우선 탐색), BFS(너비 우선 탐색)) 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점..
![]()
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가..
문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..
![]()
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 큐와 스택을 이용해 풀었다. 입력받는 수들을 리스트와 큐에 넣고, 리스트를 정렬하여서 내가 원하는 수(최소값부터 나갈 수 있으니)들을 리스트의 원소들을 설정해놓았다. 이런식으로 풀었는데 결론적으로 문제에 나와있는 그림을 스택과 큐를 이용해 구현했다.
![]()
문제 해설 처음에 모든 경우의 수를 검사하는 코드를 작성했는데, 시간초과가 난 문제이다. 모든 경우의 수를 검사하지 말고 각 의상의 종류에 아무것도 입지 않을 경우 1을 더하고, 각 의상의 종류 가짓수를 곱해주고, 아무것도 입지 않을 경우 1을 빼준다. 코드 import sys input = sys.stdin.readline def main(): for _ in range(int(input().strip())): dic = {} ans = 1 for _ in range(int(input().strip())): _, t = map(str, input().split()) dic[t] = dic[t] + 1 if t in dic else 2 for i in dic: ans *= dic[i] print(ans ..
