교내 동아리에서 진행한 알고리즘 스터디의 마지막 수업으로 다익스트라를 배웠다. 연습 문제 중 이 문제가 개인적으로 막힌 부분이 많았고, 그로부터 배운 것들을 정리하고자 한다. 우선 이 문제를 풀기 위한 아이디어도 떠오르지 않았다. 결국엔 동아리 스터디 내용을 통해 아이디어를 얻고, 아이디어를 구현하여 제출하였다. 아이디어는 다음과 같다. 집에서 갈 수 있는 모든 산의 정상들 학교에서 갈 수 있는 모든 산의 정상들 이 두가지를 따로 구한다음 각각에서 구한 산의 정상의 교집합을 취하여 문제가 원하는 방식대로 계산하면 된다. 만약 교집합이 없다면, 답이 없다는 뜻. 나는 다익스트라를 구현하고, 다익스트라의 결과로 나온 집/학교에서 출발 했을 때 갈 수 있는 모든 산의 정상들 (노드) 번호, 각각의 노드로 가는..

지난 번에는 맥주축제를 제일 먼저 떠올랐던 이분탐색으로 풀어보았다. 이번에는 학습 목적에 맞게 우선순위 큐로 풀어보고자 한다. 우선순위 큐로 풀 때는 다음과 같은 알고리즘을 사용하였다. 1. 맥주를 도수가 낮은 순으로 우선 정렬하고나서 선호도 순으로 정렬한다. 2. 맥주가 있는 리스트를 돌면서 맥주를 하나씩 뽑는다. 2-1. 뽑은 맥주의 도수를 현재 도수로 한다. 2-2. 뽑은 맥주의 선호도를 우선순위 큐에 넣는다. 2-3. 우선순위 큐에 있는 선호도 합과 기준 합을 비교한다. 2-4-1. 기준 합보다 크거나 같다면 find변수를 True로 바꾸고 현재 도수를 출력한다. 2-4-2. 기준합보다 작다면 우선순위 큐에서 선호도가 가장 작은 원소를 pop한다. 3. 2번과정을 반복한다. 4. 만약 find변수..

교내 동아리에서 진행한 알고리즘 스터디에서 '우선순위 큐' 의 연습문제로 주어졌던 문제이다. 우선순위 큐를 사용하기 전에 제일 먼저 떠오른 풀이는 '이분 탐색' 아니나 다를까 문제 알고리즘 분류에도 '이분 탐색'이 있었다. 이분 탐색은 항상 익숙하지 않고 힘들었기에, 오랜만에 연습해보기 좋은 문제라고 생각했다. 내가 떠올린 아이디어는 '맥주의 선호도' 값을 기준으로 정렬하고 설정한 맥주의 도수보다 작은 맥주 중, 선호도가 높은 것들만을 그리디하게 뽑아서 선호도의 합을 구하는 것이다. 그리고 맥주의 도수를 기준으로 이분탐색을 진행하여 가능한 최소 도수를 구하고 최소 도수가 없다면 -1을 출력하도록 하면 된다 def check(mid): global kind, day, sum_taste s = 0 cnt =..

개인적으로 네트워크 관련 내용을 배울 기회를 갖게 되어, 배운 내용을 기반으로 채팅프로그램을 만들어보았습니다. 서버 소스 코드 ''' 서버 예제 각 클라이어언트가 보낸 메세지를 서버에서 클라이언트 정보와 조합하여 각 클라이언트 채팅창에 띄워 보내 주는 역할 ''' import socket from _thread import * from tkinter import * def threaded(client_socket, addr): global chat_log chat_log['state'] = 'normal' chat_log.insert("end", 'Connected by :'+ addr[0] + ':' + str(addr[1]) + '\n') chat_log['state'] = 'disabled' for..

solved.ac 기준 실버2 수준이었던 제게는 매우 어려웠던 스터디 연습 문제 이 문제를 푸는 과정을 적으며, 효율적인 알고리즘에 대한 복기를 해보려고 합니다. [문제] 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. => 각 문자가 어떤 '숫자' 인지 맞추는 퍼즐입니다. 저는 '숫자'와 '수'를 혼동해서 "A = 10 같은 것도 가능할까?" 같은 쓸데없는 고민도 했었습니다. 복면산 문제가 주어질 때, 답이 존재하는지 여부를 출력하시오. 단, 같은 문자는 같은 숫자에 대응되어야 하며, 서로 다른 문자는 서로 다른 숫자를 나타낸다. 또한, 수는 0으로 시작할 수 있다. =>아래 예시 힌트가 없었다면 빼먹고 체크를 안할 수도 있었던..

tkinter를 이제 결합해보려고 합니다. https://076923.github.io/posts/Python-tkinter-19/ Python tkinter 강좌 : 제 19강 - LabelFrame | 076923 LabelFrame(라벨 프레임) 076923.github.io tkinter 와 관련된 강좌글은 이 게시글을 참고하여 작성했습니다. 설명을 정말 친절하면서도, 자세하고, 이해하기 쉽게 잘 해주셨더라구요ㅎㅎ 프로그래밍 과정은 사실 이것보다 더 복잡하게 수많은 디버깅을 거치며 진행했지만, 현재까지의 결과물을 토대로 간단하게 과정을 적어보고자 합니다. cpu_try = list() cpu_num = [0] answer_cmp = set() layout = list() 우선 변수를 선언해주었습니..

교수님께 기존 아이디어에 대해 피드백을 드렸더니 브루트포스 알고리즘은 너무 비효율적이고 재미가 없다고 하셨습니다 그래서 다른 알고리즘을 고민해보다가 한가지를 떠올렸습니다. 기존 아이디어가 가능한 모든 답에서 답이 될 수 없는 것들을 지워나가면서 답을 추론했다면 이번엔 거꾸로 제시된 결과를 토대로 가능한 정답군 집합을 만들어버리는 것입니다. 정답군 리스트에서 랜덤하게 수를 하나 제시하면 다시 결과를 알려줄 것이고 그렇다면 그 결과를 토대로 다시 정답군 집합을 또하나 만듭니다. 그리고 그 둘의 교집합을 구하면 되는 것이죠. 이 알고리즘의 단점은 두번째 정답군을 만드는 과정에서 굳이 필요없는 여집합이 될 요소들까지 카운트하게 된다는 점입니다. 이 부분에 대한 개선은 우선 추후에 고민하기로 하고, 앞서 생각한 ..

팀원분과 한번 만나서 상의를 해보면서 기본적인 프로그램 틀을 짠 것 같습니다. 우선 기본세팅에 대해 대전이 가능한 인공지능을 구현해보았습니다. https://m.blog.naver.com/PostView.nhn?blogId=bluesune&logNo=66599203&proxyReferer=https:%2F%2Fwww.google.com%2F [C 언어] 1인용 인공지능 숫자야구게임 + 알고리즘 인공지능 야구게임 수를 입력하면, 컴퓨터가 맞추는 게임. 알고 있는 거의 모든 인공지능 야구게임중가장 ... blog.naver.com 알고리즘은 이 분의 알고리즘을 그대로 파이썬으로 구현해보았습니다. 보통 4번정도만에 정답을 맞추더라구요 소스코드는 다음과 같이 짜보았습니다. from random import * ..

학교에서 팀플로 프로젝트를 하게 되었습니다. 자유로운 주제로 파이썬을 이용한 프로그램 개발입니다. 1달도 안 되는 짧은 기간 동안의 프로젝트가 될 것 같습니다. 1. 주제 구상 우선 생각한 주제는 인공지능 숫자야구 전에 있던 대학교에서 C언어로 숫자야구 게임을 만들어봤던 기억이 나서 이 주제를 떠올렸습니다. 다만 그때는 컴퓨터가 만든 숫자를 사람이 맞추는 방법이라 그 반대로도 해본다면 어떨까 하는 마음으로 구상했습니다. 사용할 예정인 모듈은 GUI를 위한 tkinter 모듈과 난수 생성을 위한 랜덤 모듈 두 가지입니다. 구체적으로 들어가면 사람 vs 사람 / 사람 vs 컴퓨터 이 두 가지 모드를 고르는 것이 우선입니다. (이렇게 쓰고 보니 컴퓨터 vs 컴퓨터로 해서 누가 이길지로 배팅하는 것도 재밌어 보..