๋ฐฐ๊ฒฝ ํ
์ปค ๋ถํธ์บ ํ์์ ํํ๋ก์ ํธ๋ฅผ ์งํ ์ค์ด๋ค. ์ฐ๋ฆฌ ํ์ ์ฃผ์ ๋ ํน์ ์ธ๋ฌผ์๊ฒ ์๋ด์ ๋ฐ๋ ๊ฒ ๊ฐ์ ๋ํ๋ฅผ ํ ์ ์๋ ์ฑ๋ด์ ๋ง๋๋ ๊ฒ์ด๋ค. ์ด๋ฅผ ์ํด ํน์ ์ธ๋ฌผ์ด ํ๋ ๋ง์ ๋ชจ์ ๋ฐ์ดํฐ์
์ผ๋ก ๋ง๋ค๊ณ ์ด๋ฅผ RAG ๋ชจ๋ธ์ ์ ์ฉ์ํค๋ ค๊ณ ํ๋ค. ์์ ์ผ๋ก ๋จธ์คํฌ๊ฐ TED์์ ํ ์ธํฐ๋ทฐ๋ฅผ ํ
์คํธ๋ก ๊ฐ์ ธ์จ๋ค. OpenSearch ๋์ปค ์ปจํ
์ด๋๋ฅผ ์คํํ๋ค. ํ
์คํธ ๋ฐ์ดํฐ๋ฅผ ์๋ฒ ๋ฉํด์ OpenSearch์ ์ ์ฅํ๋ค. RAG ๋ชจ๋ธ์ด OpenSearch๋ฅผ ์ฟผ๋ฆฌํ์ฌ ๋๋ต์ ์์ฑํ๋ค. 1. ์ผ๋ก ๋จธ์คํฌ ์ธํฐ๋ทฐ ํ
์คํธ ๊ฐ์ ธ์ค๊ธฐ ์ ํ๋ธ์์ “์คํฌ๋ฆฝํธ ๋ณด๊ธฐ"๋ฅผ ํตํด ์ธํฐ๋ทฐ ์๋ง์ ๊ฐ์ ธ์จ๋ค.
122:03 2EM: ์ด ํฐ ํธ๋ญ์ ๋ชฐ๋ฉด์ ๋ง๋ ์๋๋ ์์ง์์ ๋ณด์์ฃ . 3CA: ์์ฃผ ๋ฉ์ง๋ค์. ์, ๊ทธ๋ผ ์ ๋ง ๊ต์ฅํ ์ฌ์ง์์ 422:09 5์กฐ๊ธ์ ๋ ๊ต์ฅํ ์ฌ์ง์ ๋ณด์ฃ . "์๊ธฐ์ ์ฃผ๋ถ๋ค"์ธ๊ฐ์์ ๋์ค๋ ๊ท์ฌ์ด ์ง ์ฌ์ง์ธ๋ฐ์. 622:15 7์ด๊ฒ ๊ฐ์๊ธฐ ์ ๋์จ๊ฑฐ์ฃ ? 8... ์ผ๋ก ๋จธ์คํฌ๊ฐ ํ ๋ง๋ง ์์ ์ ๋ฆฌํ๋ค.
1๋ค. ์ ์ค์ค๋ก๋ ๊ทธ ์ง๋ฌธ์ ์์ฃผ ํ๋ ํธ์
๋๋ค. 2์ ํฌ๋ LA์ ์งํ์ ๊ตฌ๋ฉ์ ๋ด๋ ค๊ณ ํ๋๋ฐ์. ์ด๋ ๊ตํต ์ฒด์ฆ์ ์ํ์ํค๊ธฐ ์ํ 33์ฐจ์ ๋คํธ์ํฌ์ ํฐ๋์ด ๋ ์๋ ์๋ ์๋ฐ์ ์ ๋ง๋ค๊ธฐ ์ํจ์
๋๋ค. 4๊ตํต ์ฒด์ฆ์ ์ค๋๋ ์ฐ๋ฆฌ์ ์ํผ์ ํํ ํฐ๋ ๋ฌธ์ ์ค์ ํ๋์
๋๋ค. 5์ธ๊ณ ๋ชจ๋ ์ฌ๋๋ค์๊ฒ ์ํฅ์ ๋ผ์น๊ณ ์์ฃ . ์ธ์์์ ๋๋ฌด๋ ๋ง์ ๋ถ๋ถ์ ๊ฐ์ ธ๊ฐ๋๋ค. 6... 2. OpenSearch ๋์ปค ์ปจํ
์ด๋ ์คํ 1docker create -it -p 9200:9200 -p 9600:9600 -e OPENSEARCH_INITIAL_ADMIN_PASSWORD={password} -e "discovery.type=single-node" -v opensearch_vol:/usr/share/opensearch/data --name opensearch opensearchproject/opensearch ์ค๋ช
-p 9200:9200 : OpenSearch HTTP ํฌํธ -p 9600:9600 : OpenSearch ๋ชจ๋ํฐ๋ง ํฌํธ -e OPENSEARCH_INITIAL_ADMIN_PASSWORD={password} : ์ด๊ธฐ ๋น๋ฐ๋ฒํธ ์ค์ -e “discovery.type=single-node” : ๋จ์ผ ๋
ธ๋๋ก ์คํ -v opensearch_vol:/usr/share/opensearch/data : ๋ฐ์ดํฐ ๋ณผ๋ฅจ ๋ง์ดํธ SSL ์ค๋ฅ ๋ฐ์๊ณผ ํด๊ฒฐ ํ์ง๋ง ์ ๋ช
๋ น์ด๋ก ์คํํ๋ฉด ์ปจํ
์ด๋ ๋ด๋ถ์์ ์ค๋ฅ๊ฐ ๋ฐ์ํ๋ค
12024-07-05 22:15:12 Caused by: io.netty.handler.ssl.NotSslRecordException: not an SSL/TLS record: ... 22024-07-05 22:15:12 at io.netty.handler.ssl.SslHandler.decodeJdkCompatible(SslHandler.java:1314) ~[netty-handler-4.1.110.Final.jar:4.1.110.Final] 32024-07-05 22:15:12 at io.netty.handler.ssl.SslHandler.decode(SslHandler.java:1387) ~[netty-handler-4.1.110.Final.jar:4.1.110.Final] 42024-07-05 22:15:12 at io.netty.handler.codec.ByteToMessageDecoder.decodeRemovalReentryProtection(ByteToMessageDecoder.java:530) ~[netty-codec-4.1.110.Final.jar:4.1.110.Final] 52024-07-05 22:15:12 at io.netty.handler.codec.ByteToMessageDecoder.callDecode(ByteToMessageDecoder.java:469) ~[netty-codec-4.1.110.Final.jar:4.1.110.Final] 62024-07-05 22:15:12 ... 16 more ํ๋ก์ ํธ ๊ธฐ๊ฐ์ด ๊ธธ์ง ์๊ณ , ํด๋น ํฌํธ๋ ์ธ๋ถ์ ๋
ธ์ถํ ํ์๊ฐ ์์ผ๋ฏ๋ก SSL์ ๋๊ณ ์คํํ๋ ๊ฒ์ผ๋ก ํด๊ฒฐํ์๋ค.
1/usr/share/opensearch/config/opensearch.yml 2# ๋ณ๊ฒฝ ์ 3plugins.security.ssl.http.enabled: true 4# ๋ณ๊ฒฝ ํ 5plugins.security.ssl.http.enabled: false 3. ํ
์คํธ ๋ฐ์ดํฐ ์๋ฒ ๋ฉ ๋ฐ OpenSearch์ ์ ์ฅ RAG ์ธ์
์ ํด์ฃผ์ ๋ฉํ ๋์ด ์ง์ค ์ฝ๋๋ฅผ ์ ๊ทน! ์ฐธ๊ณ ํ์ฌ ์์ฑํ์๋ค.
OpenSearch ์ธ๋ฑ์ค ์์ฑ 1from opensearchpy import OpenSearch 2import torch 3from transformers import AutoTokenizer, AutoModel 4from langchain.text_splitter import RecursiveCharacterTextSplitter 5from langchain_community.document_loaders import TextLoader 6from langchain_community.vectorstores import OpenSearchVectorSearch 7 8INDEX_NAME = "elon_musk" 9FILE_NAME = "ted_elon_musk_script.txt" 10 11## OpenSearch ์ฐ๊ฒฐ ์ค์ 12client = OpenSearch( 13 hosts=[{"host": "localhost", "port": 9200}], http_auth=("admin", {password}) 14) 15 16## ํ
์คํธ ๋ฐ์ดํฐ ๋ถ๋ฌ์ค๊ธฐ 17loader = TextLoader(file_path=FILE_NAME, encoding="utf-8") 18docs = loader.load() 19 20text_splitter = RecursiveCharacterTextSplitter( 21 chunk_size=100, 22 chunk_overlap=0, 23 separators=["\n"], 24 length_function=len, 25) 26 27documents = text_splitter.split_documents(docs) 28 29# print(documents) 30 31## Embedding ๋ชจ๋ธ ์ ์ 32class MyEmbeddingModel: 33 def __init__(self, model_name): 34 self.tokenizer = AutoTokenizer.from_pretrained(model_name) 35 self.model = AutoModel.from_pretrained(model_name) 36 37 def embed_documents(self, doc): 38 inputs = self.tokenizer( 39 doc, return_tensors="pt", padding=True, truncation=True, max_length=512 40 ) 41 42 with torch.no_grad(): 43 outputs = self.model(**inputs) 44 embeddings = outputs.last_hidden_state.mean(dim=1).tolist() 45 46 return embeddings 47 48 def embed_query(self, text): 49 inputs = self.tokenizer( 50 [text], padding=True, truncation=True, return_tensors="pt", max_length=512 51 ) 52 with torch.no_grad(): 53 outputs = self.model(**inputs) 54 embeddings = outputs.last_hidden_state.mean(dim=1).tolist() 55 return embeddings 56 57 58## index ๊ตฌ์กฐ ์ ์ 59index_body = { 60 "settings": { 61 "analysis": { 62 "tokenizer": { 63 "nori_user_dict": { 64 "type": "nori_tokenizer", 65 "decompound_mode": "mixed", 66 "user_dictionary": "user_dic.txt", 67 } 68 }, 69 "analyzer": { 70 "korean_anlyzer": { 71 "filter": [ 72 "synonym", "lowercase", 73 ], 74 "tokenizer": "nori_user_dict", 75 } 76 }, 77 "filter": { 78 "synonym" :{ 79 "type": "synonym_graph", 80 "synonyms_path" : "synonyms.txt" 81 } 82 } 83 } 84 } 85} 86 87## Embedding ๋ชจ๋ธ ์์ฑ 88my_embedding = MyEmbeddingModel("monologg/kobert") 89 90## OpenSearch์ ๋ฐ์ดํฐ ์ฝ์
91vector_db = OpenSearchVectorSearch.from_documents( 92 index_name=INDEX_NAME, 93 body=index_body, 94 documents=documents, 95 embedding=my_embedding, 96 op_type="create", 97 opensearch_url="http://localhost:9200", 98 http_auth=("admin", {password}), 99 use_ssl=False, 100 verify_certs=False, 101 ssl_assert_hostname=False, 102 ssl_show_warn=False, 103 bulk_size=1000000, 104 timeout=360000, 105) 106 107result = vector_db.add_documents(documents, bulk_size=1000000) tokenizer๋ ํ๊ตญ์ด๋ฅผ ์ง์ํ๋ “nori_tokenizer"๋ฅผ ์ฌ์ฉํ์๋ค. embedding ๋ชจ๋ธ์ ์ ๊ฑฐ ๋ง๊ณ ๋ ์ฌ๋ฌ๊ฐ์ง๊ฐ ์กด์ฌํ๋๋ฐ, ์ด๋ค ๋ชจ๋ธ์ด ํ๋ก์ ํธ์ ๊ฐ์ฅ ๋ถํฉํ๋ ๋ชจ๋ธ์ธ์ง๋ ์คํ์ ํด๋ณผ ๊ฒ์ด๋ค. curl์ ํตํด localhost:9200/elon_musk/_search๋ก ์์ฒญ์ ๋ณด๋ด ์๋ฒ ๋ฉํ ๋ฐ์ดํฐ๊ฐ ์ ๋ค์ด๊ฐ๋์ง ํ์ธํ ์ ์๋ค. 4. RAG ๋ชจ๋ธ์ด OpenSearch๋ฅผ ์ฟผ๋ฆฌํ์ฌ ๋๋ต ์์ฑ 1from langchain.prompts import PromptTemplate 2from langchain.chains import LLMChain 3from langchain_openai import ChatOpenAI 4from opensearchpy import OpenSearch 5import os 6 7INDEX_NAME = "elon_musk" 8 9# ํ๊ฒฝ๋ณ์ ์ค์ 10os.environ["OPENAI_API_KEY"] = {api_key} 11 12llm = ChatOpenAI( 13 model_name="gpt-3.5-turbo", 14) 15 16prompt_template = PromptTemplate( 17 input_variables=["context", "question"], 18 template=""" 19Imagine you are {character_name}, 20a wise and experienced advisor. Given the context: "{context}", 21how would you respond to this inquiry: "{question}"?', 22(in korean) 23""", 24) 25 26 27llm_chain = LLMChain(llm=llm, prompt=prompt_template) 28 29client = OpenSearch( 30 hosts=["http://localhost:9200"], 31 http_auth=("admin", {password}), 32 use_ssl=False, 33 verify_certs=False, 34 ssl_assert_hostname=False, 35 ssl_show_warn=False, 36) 37 38def search_documents(query): 39 search_body = {"query": {"match": {"text": query}}} 40 response = client.search(index=INDEX_NAME, body=search_body) 41 hits = response["`its"]["hits"] 42 return [hit["_source"]["text"] for hit in hits] 43 44if __name__ == "__main__": 45 question = input("Enter your question\n") 46 search_results = search_documents(question) 47 48 print(search_results) 49 50 # context = " ".join(search_results) 51 context = "" 52 53 response = llm_chain.invoke({"character_name": INDEX_NAME, "context": context, "question": question}) 54 55 print (response["text"]) OpenSearch์ ์ ์ฅ๋ ๋ฐ์ดํฐ๋ฅผ ์ฟผ๋ฆฌํ์ฌ RAG ๋ชจ๋ธ์ ๋ฃ์ด ๋๋ต์ ์์ฑํ๋ค. search_documents ํจ์๋ฅผ ํตํด OpenSearch์ ์ฟผ๋ฆฌ๋ฅผ ๋ณด๋ด๊ณ , ๊ทธ ๊ฒฐ๊ณผ๋ฅผ context๋ก ์ฌ์ฉํ๋ค. ๊ฒฐ๊ณผ ์ง๋ฌธ ํ
์ฌ๋ผ์ ๋ํด์ ์ด๋ป๊ฒ ์๊ฐํด?
RAG๋ฅผ ์ฌ์ฉํ์ง ์์์ ๋์ ๋๋ต ํ
์ฌ๋ผ๋ ํ์ ์ ์ธ ๊ธฐ์
์ผ๋ก์ ๋ฏธ๋๋ฅผ ํฅํ ๋น์ ์ ๊ฐ์ง๊ณ ์์ต๋๋ค. ๊ทธ๋ค์ ์ ๊ธฐ ์๋์ฐจ ๊ธฐ์ ๊ณผ ์๋์ง ์๋ฃจ์
์ ์ ์ธ๊ณ์ ์ผ๋ก ์ฃผ๋ชฉ๋ฐ๊ณ ์์ต๋๋ค. ํ
์ฌ๋ผ์ ํ์ ์ ์ธ ์ ๊ทผ ๋ฐฉ์๊ณผ ์ง์ ๊ฐ๋ฅํ ๋น์ฆ๋์ค ๋ชจ๋ธ์ ๋ํด ๋งค์ฐ ๊ธ์ ์ ์ผ๋ก ์๊ฐํ๊ณ ์์ต๋๋ค.
RAG๋ฅผ ์ฌ์ฉํ ๋ ์ ์ฉ๋ context [‘๊ธธ๊ฒ ๊ฐ ๊ฒ ๊ฐ์ง๋ ์์์.\n๊ทธ๋ฌ๋ค์. ์ ๋ ์ต๋ํ ์ค๋ซ๋์ ํ
์ฌ๋ผ์ ๋จธ๋ฌผ ์๊ฐ์ด์์.\n๊ทธ๋ฆฌ๊ณ ์ค๋น ์ค์ ์๋ ํฅ๋ฏธ๋ก์ด ์ผ๋ ๋ง๊ณ ์. ์์๋ค์ํผ, ๋ชจ๋ธ 3์ด ์ถ์ ์์ ์ด๊ณ ์.’, ‘์ฌํด ๋ง๊น์ง LA์์ ๋ด์๊น์ง\n์์ ์์จ ์ฃผํ์ผ๋ก ํก๋จํ๋ ๊ณํ์ ๋ง์ถฐ์ ์งํ ์ค์ด์์.\n์ฌ๋์ด ํ
์ฌ๋ผ์ ํ์ ์ด์ ๋๋ฅผ ์ก์ง ์๊ณ “๋ด์"์ ์ฐ์ผ๋ฉด ๊ทธ๋ฆฌ๋ก ๊ฐ๋ค๋ ๋ง์ด๋ค์.’, ‘๊ธธ๊ฒ ๊ฐ ๊ฒ ๊ฐ์ง๋ ์์์.\n๊ทธ๋ฌ๋ค์. ์ ๋ ์ต๋ํ ์ค๋ซ๋์ ํ
์ฌ๋ผ์ ๋จธ๋ฌผ ์๊ฐ์ด์์.\n๊ทธ๋ฆฌ๊ณ ์ค๋น ์ค์ ์๋ ํฅ๋ฏธ๋ก์ด ์ผ๋ ๋ง๊ณ ์. ์์๋ค์ํผ, ๋ชจ๋ธ 3์ด ์ถ์ ์์ ์ด๊ณ ์.’, ‘์ฌํด ๋ง๊น์ง LA์์ ๋ด์๊น์ง\n์์ ์์จ ์ฃผํ์ผ๋ก ํก๋จํ๋ ๊ณํ์ ๋ง์ถฐ์ ์งํ ์ค์ด์์.\n์ฌ๋์ด ํ
์ฌ๋ผ์ ํ์ ์ด์ ๋๋ฅผ ์ก์ง ์๊ณ “๋ด์"์ ์ฐ์ผ๋ฉด ๊ทธ๋ฆฌ๋ก ๊ฐ๋ค๋ ๋ง์ด๋ค์.’]
RAG๋ฅผ ์ฌ์ฉํ ๋์ ๋๋ต ์ ๋ ํ
์ฌ๋ผ๋ฅผ ๋งค์ฐ ๊ธ์ ์ ์ผ๋ก ์๊ฐํฉ๋๋ค. ํ
์ฌ๋ผ๋ ํ์ ์ ์ธ ๊ธฐ์ ๊ณผ ์ง์ ๊ฐ๋ฅํ ๋ฏธ๋๋ฅผ ์ํ ๋น์ ์ ๊ฐ์ถ ๊ธฐ์
์ผ๋ก์, ์์จ ์ฃผํ ๊ธฐ์ ์ ํตํด ์ฐ๋ฆฌ์ ์ถ์ ํ์ ํ๊ณ ์์ต๋๋ค. ๋ํ, ์ ๊ธฐ์ฐจ ์์ฅ์ ์ ๋ํ๊ณ ํ๊ฒฝ์ ์นํ์ ์ธ ์ฐจ๋์ ์ ๊ณตํ๋ ๋ฉ์ง ๊ธฐ์
์ด๋ผ๊ณ ์๊ฐํฉ๋๋ค. ํ
์ฌ๋ผ์ ๋ฏธ๋๊ฐ ๋ฐ๊ณ ํฅ๋ฏธ๋ก์ด ์ผ๋ค์ด ๊ณ์ํด์ ์ผ์ด๋ ๊ฒ์ด๋ผ๊ณ ๋ฏฟ์ต๋๋ค.
๊ณ ์ฐฐ ํ์คํ RAG๋ฅผ ์ฌ์ฉํ์ง ์์์ ๋๋ ๊ฐ๊ด์ ์ด๊ณ ์ผ๋ฐ์ ์ธ ๋๋ต์ ํ๋ ๋ฐ๋ฉด, RAG๋ฅผ ์ฌ์ฉํ ๋๋ ํ
์ฌ๋ผ์ ๋ํด ๊ธ์ ์ ์ธ ์ผ๋ก ๋จธ์คํฌ์ ๋๋ต๊ณผ, ์์จ์ฃผํ ๊ธฐ์ ์ ์ธ๊ธํ๋ค๋ ๊ฒ์ ๋ฐ์ํ์ฌ ๋๋ต์ ์์ฑํ์๋ค. ๊ฐ์ ์ปดํจํฐ์ ์ธ๊ฐ์ด ์ํตํ๋ ๋ฐฉ๋ฒ ์ด์
๋ธ๋ฆฌ์ด ์ด์
๋ธ๋ฆฌ์ด์ ๋ฒ์ญ๊ธฐ๋ ์ด์
๋ธ๋ฌ(Assembler)๋ผ๊ณ ํ๋ค cpu์นฉ์
์ด ๋ฐ๋๋๋ง๋ค ์ด์
๋ธ๋ฆฌ์ด๊ฐ ๋ฐ๋๋ค ๊ณ ๊ธ์ธ์ด ๊ณ ๊ธ์ธ์ด์ ๋ฒ์ญ๊ธฐ๋ ์ปดํ์ผ๋ฌ(Compiler)๋ผ๊ณ ํ๋ค ์ปดํ์ผ๋ฌ์ ์ ํํ ์ ์ ์ด๋ค ์ธ์ด๋ก ์ฐ์ฌ์ง ํ๋ก๊ทธ๋จ์ ๊ฐ์ ์ญํ ์ ๋ค๋ฅธ ์ธ์ด๋ก ๋ฐ๊ฟ์ฃผ๋ ํ๋ก๊ทธ๋จ
1952๋
๊ทธ๋ ์ด์ค ํธํผ(Grace Hopper)๊ฐ UNIVAC์ฉ ํ๋ก๊ทธ๋๋ฐ์ธ์ด A-0 ์ปดํ์ผ๋ฌ๋ฅผ ์ ์ ์ปดํ์ผ๋ฌ vs ์ธํฐํ๋ฆฌํฐ ํ๋ก๊ทธ๋จ ์ฒ๋ฆฌ๊ณผ์ ์ปดํ์ผ๋ฌ์ ์ฒ๋ฆฌ ๊ณผ์ Lexical analysis (์ดํ ๋ถ์) token์ ์์ฑํ๋์ผ, token์ ์ดํ์ ์ต์ ๋จ์ Syntax analysis (๊ตฌ๋ฌธ ๋ถ์) token์ ์ฝ์ด์ ์ค๋ฅ๋ฅผ ๊ฒ์, ๊ตฌ๋ฌธ ๊ตฌ์กฐ๋ฅผ ๋ง๋ ๋ค (์ฃผ๋ก ํธ๋ฆฌํํ) Semantic analysis (์๋ฏธ ๋ถ์) type checking Intermediate code generation (์ค๊ฐ ์ฝ๋ ์์ฑ) ์ค๊ฐ ์ฝ๋๋ก ๋ณํ Code optimization (์ฝ๋ ์ต์ ํ) ์ค๊ฐ ์ฝ๋๋ฅผ ๋ ํจ์จ์ ์ผ๋ก ๋ณํ Code generation (์ฝ๋ ์์ฑ) ๋ชฉ์ ์ฝ๋ ์์ฑ Lexical analysis (์ดํ ๋ถ์) token : ๋ฌธ๋ฒ์ ์ผ๋ก ์๋ฏธ์๋ ์ต์ ๋จ์ FSA (Finite State Automata, ์ ํ ์ํ ์คํ ๋งํ) token์ ์ธ์ํ๋ ๋ฐฉ๋ฒ ์์ ์ํ ํ ๊ฐ์ ๋ ์ํ ์ฌ๋ฌ ๊ฐ๋ฅผ ๊ฐ์ง DFA (Deterministic Finite Automata) FSA์ ํ ์ข
๋ฅ ๊ฐ ์ํ์์ ๋ป์ด๋๊ฐ๋ edge๊ฐ ํ๋์ฉ๋ง ์กด์ฌ ฮต๊ฐ ๋ถ์ edge ์์ ๋ถ์ํ ํ ํฐ์ ํํํ๋ ๋ฐฉ๋ฒ Lexeme = <ํ ํฐ๋ฒํธ, ํ ํฐ ๊ฐ>
์์ if X < Y … (29, 0) (1, X) (18, 0) (1, Y) … ์๋ณ์์ ํ ํฐ๋ฒํธ๋ 1๋ฒ, ์์๋ 2๋ฒ ๋ฑ์ผ๋ก ๊ณ ์ Syntax analysis (๊ตฌ๋ฌธ ๋ถ์) token์ ์ฝ์ด์ ์ค๋ฅ๋ฅผ ๊ฒ์, parse tree๋ฅผ ๋ง๋ ๋ค CFG (Context Free Grammer) ๊ตฌ๋ฌธ์ ํํํ๋ ๋ฐฉ๋ฒ G = (N, T, P, S) N = nonterminal symbol ์ํ๋ฒณ ๋๋ฌธ์๋ก ํํ T = terminal symbol (token) ์ํ๋ฒณ ์๋ฌธ์+์ซ์, ์ฐ์ฐ์, ๊ตฌ๋ถ์, ํค์๋ ๋ฑ P = production rule ์) S -> T+T, T -> ‘0’|‘1’|‘2’ S = start symbol L(G) : ์ด ๋ฌธ๋ฒ์ผ๋ก ์์ฑ๋๋ ์ธ์ด ์ฌ๋ฌ๊ฐ์ง CFG ํํ๋ฒ BNF (Backus-Naur Form) EBNF (Extended BNF) ์ ๋ (derivation) ์์ฑ ๊ท์น๋ฅผ ์ ์ฉํ์ฌ ๋ฌธ์ฅ์ ์์ฑํ๋ ๊ณผ์ ์ ๋๋ฅผ ํ๋ ๊ณผ์ ์์ ํ๋์ฉ ๊ณจ๋ผ์ ๋ฐ๊ฟ ์ ๋ ํธ๋ฆฌ : ์ ๋ ๊ฒฝ๋ก๋ฅผ ์ถ์ํ ์์ผ ํํํ ๊ฒ ์ข์ธก ์ ๋(leftmost derivation) ๊ฐ์ฅ ์ผ์ชฝ์ ์๋ nonterminal์ ๋จผ์ ๋์น ์ฐ์ธก ์ ๋(rightmost derivation) ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ ์๋ nonterminal์ ๋จผ์ ๋์น ๋ชจํธ์ฑ (ambiguity) ๋ฌธ๋ฒ G์ ์ํด ์์ฑ๋๋ ์ด๋ค ๋ฌธ์ฅ์ด ๋๊ฐ ์ด์์ ์ ๋ํธ๋ฆฌ๋ฅผ ๊ฐ๋๋ค๋ฉด ๋ฌธ๋ฒ G๋ ๋ชจํธํ๋ค๊ณ ํ๋ค ๋ชจํธํ์ง ์์ ๋ฌธ๋ฒ์ ์ข์ธก ์ ๋์ ์ฐ์ธก ์ ๋๊ฐ ๊ฐ๋ค ๋ชจํธ์ฑ ํด๊ฒฐ ์ฐ์ฐ์ ์ฐ์ ์์ ๋์
๊ฒฐํฉ ๋ฒ์น ๋์
Left Recursion์ ์ข์ธก ๊ฒฐํฉ์ ์ฌ์ฉ ex) A -> A+a | a Right Recursion์ ์ฐ์ธก ๊ฒฐํฉ์ ์ฌ์ฉ ex) A -> a+A | a ๊ตฌ๋ฌธ ๋ถ์์ 2๊ฐ์ง ๋ฐฉ์ top-down, bottom-up Top-down parsing Top-down ๋ฐฉ์ ์ข์ธก ์ ๋์ ๊ฐ์ ์์ ์ ์์ฑ ๊ท์น ์ ์ฉ backtracking : ์ ๋๋ ๋ฌธ์์ด๊ณผ ์
๋ ฅ ๋ฌธ์์ด์ด ๊ฐ์ง ์์ผ๋ฉด ๋ค๋ฅธ ์์ฑ๊ท์น ์ ์ฉ Bottom-up ๋ฐฉ์ ์ฐ์ธก ์ ๋์ ์ญ์์ ์์ฑ ๊ท์น ์ ์ฉ LL ํ์ฑ ์ผ์ชฝ->์ค๋ฅธ์ชฝ์ผ๋ก ์ฝ์ด์ ์ขํ์ค ์์ฑ backtracking X, ๋น ๋ฅด๋ค ๊ฒฐ์ ์ ์ผ๋ก ํ์ฑ ์ฌ์ฉ๋ ์ ์ ฮต-์์ฑ๊ท์น
Nonterminal A๊ฐ ฮต๋ฅผ ์ ๋ํ ์ ์์ผ๋ฉด A๋ฅผ nullableํ๋ค๊ณ ๋ถ๋ฅธ๋ค lhs, rhs
A->XXX์์ lhs๋ A, rhs๋ XXX โ (Ring Sum)
A์ ฮต๊ฐ ์์ผ๋ฉด, AโB = (A์์ ฮต๋นผ๊ณ A ํฉ์งํฉ B) A์ ฮต๊ฐ ์์ผ๋ฉด, AโB = A First nonterminal A๋ก ๋ถํฐ ์ ๋๋์ด ์ฒซ๋ฒ์งธ๋ก ๋ํ๋ ์ ์๋ terminal์ ์งํฉ X->Y1Y2Y3์ผ๋, FIRST(X) = FIRST(X) U FIRST(Y1) โ FIRST(Y2) โ FIRST(Y3)
Follow A ๋ค์์ ๋์ค๋ terminal์ ์งํฉ A->ฮฑBฮฒ, ฮฒ != ฮต ์ผ๋, FOLLOW(B) = FOLLOW(B) U (FIRST(ฮฒ)-{ฮต})
A->ฮฑB ๋๋ A->ฮฑBฮฒ, FIRST(ฮฒ)์ ฮต๊ฐ ์ํ ๋, FOLLOW(B) = FOLLOW(B) U FOLLOW(A)
LL์กฐ๊ฑด FIRST(ฮฑ)์ FIRST(ฮฒ)๊ฐ ๊ฒน์น๋ฉด ์๋๋ค FIRST(ฮฑ)์ ฮต๊ฐ ์์ผ๋ฉด, FOLLOW(ฮฑ)์ FIRST(ฮฒ)๊ฐ ๊ฒน์น๋ฉด ์๋๋ค LL ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๋ฌธ๋ฒ = LL ํ์ฑ ๋๋ ๋ฌธ๋ฒ LL(1) ๋ฌธ๋ฒ ์์์ ๋ฌธ๋ฒ์ ๋ํ์ฌ LL ์กฐ๊ฑด์ ๋ง์กฑํ๋ CFG 1 : LOOKAHEAD๊ฐ 1๊ฐ๋ผ๋ ์๋ฏธ ๋ค์๊ณผ ๊ฐ์ ๊ฒฝ์ฐ LL(1)๋ฌธ๋ฒ์ด ๋์ง ์๋๋ค ๋ชจํธํ ๋ฌธ๋ฒ ์ฐ์ ์์ ์ฃผ๊ธฐ, ๊ฒฐํฉ๋ฒ์น ๋ฐ์์ผ๋ก ํด๊ฒฐ left-factoring์ด ๋๋ ๊ฒฝ์ฐ ๊ณตํต ์๋ถ๋ถ์ ์๋ก์ด nonterminal๋ก ๋ง๋ค์ด ํด๊ฒฐ left-recursiveํ ๊ฒฝ์ฐ ์ง์ recursion : A -> Aฮต ์ธ๊ฒฝ์ฐ ๊ฐ์ recursion : A -> B, B -> A ์ธ๊ฒฝ์ฐ LOOKAHEAD ์ด๋ค ๊ท์น์ด ์ ์ฉ๋์์๋ ๋งจ ์ฒ์ ๋์ฌ ์ ์๋ terminal ์งํฉ A->X1X2X3์ผ๋, LOOKAHEAD(A) = FIRST(X1) โ FIRST(X2) … โ FOLLOW(A)
Strong LL(1) LL(1)๊ณผ ํญ์ ๋์ผ (1์ด ์๋๋๋ ๋ค๋ฆ) LOOKAHEAD(A->ฮฑ)์ LOOKAHEAD(A->ฮฒ)๊ฐ ๊ฒน์น์ง ์๋ ๋ฌธ๋ฒ LL(1) ํ์ ๊ตฌํ ๋ฐฉ๋ฒ Recursive descent parser ์ฅ์ : ์ง๊ด์ ์ฝ๋ค ๋จ์ : ์์ฑ ๊ท์น์ด ๋ฐ๋๋ฉด ๊ตฌ๋ฌธ ๋ถ์๊ธฐ๋ฅผ ๊ณ ์ณ์ผ ํ๋ค Predictive parser PDA(PushDown Automata)์ ๊ธฐ๋ฐ
์์ฑ ๊ท์น์ด ๋ฐ๋๋ฉด ํ์ฑ ํ
์ด๋ธ๋ง ์์
ํ์ฑํ
์ด๋ธ ์์ (?์๋ ๊ท์น๋ฒํธ๊ฐ ๋ค์ด๊ฐ๋ค)
a b S ? ? A ? ? ํ์ฑํ
์ด๋ธ์ ๋๊ฐ ์ด์์ ์์ฑ ๊ท์น์ด ๋ค์ด๊ฐ๋ ๊ฒฝ์ฐ -> NOT LL(1)
Stack์ ์์ Bottom-up parsing left-recursive ๋ฌธ๋ฒ๋ ํ์ฑ ๊ฐ๋ฅ LL(k) ์ข์ธก์ ๋ ๊ธฐ๋ฐ k๊ฐ์ symbol์ lookahead Top-down parsing, recursive descent parsing, predictive parsing, LL parser ํ์คํธ๋ฆฌ๋ฅผ pre-roder๋ก ์ํ ๋ฐ ์์ฑ LR(k) ์ฐ์ธก์ ๋ ๊ธฐ๋ฐ k๊ฐ์ symbol์ lookahead Bottom-up parsing, shift-reduce parsing, LR parser ํ์คํธ๋ฆฌ๋ฅผ post-order๋ก ์ํ ๋ฐ ์์ฑ Reduce S=>ฮฑฮฒฯ์ด๊ณ A->ฮฒ์ด๋ฉด ฮฒ๋ฅผ A๋ก ๋์นํ๋ ๊ฒ : S=>ฮฑAฯ ์์ symbol์ด ๋์ฌ ๋๊น์ง reduce ํ๋ค Handle S=>ฮฑฮฒฯ์ด๊ณ A->ฮฒ์ด๋ฉด ฮฒ๋ฅผ ฮฑฮฒฯ์ handle์ด๋ผ๊ณ ํ๋ค ๋ ๊ฐ ์ด์์ handle์ด ์กด์ฌํ ๋ -> ๋ชจํธํ๋ค Shift์ Reduce๋ก Parsing ํ๊ธฐ Stack์ ์์ Issue Shift์ Reduce ์ค ์ด๋ ๊ฒ์ ํ ๊น? Stack์ top์์ ์ผ๋ง๋งํผ์ handle๋ก ๋ณผ ๊ฒ์ธ๊ฐ? ํด๊ฒฐ๋ฐฉ๋ฒ: LR Parsing Table YACC LALR ํ์ ์์ฑ๊ธฐ foo.y –(yacc)–> y.tab.c –(gcc)–> a.out *.y ํ์ผ ๊ตฌ์กฐ 1<์ ์ธ๋ถ> 2... 3%% 4... 5exp : exp '+' term; 6factor : ident; 7... 8%% 9<์ฌ๋ฌ ํจ์> ๋ชจํธํ ๋ฌธ๋ฒ์ผ๋ก LR Conflict ๋ฐ์ ์ ์ ์ธ๋ถ์์ ์ฐ์ ์์ ์ง์ ํ์ฌ ํด๊ฒฐ LR Parsing Table Action table : Action + Parser ์ํ Goto table : Parser ์ํ LR(0) ํ์ฑ ํ
์ด๋ธ ๋ง๋ค๊ธฐ LR(0) ์์ดํ
rhs์ ์ (’.’) symbol์ ๊ฐ์ง ์์ฑ ๊ท์น ex) A->ฮฑ.ฮฒ, A->. closure ์ (’.’)๋ค์ non-terminal์ด ์ค๋ฉด ์ฌ๊ท์ ์ผ๋ก ์ถ๊ฐ S’ -> S, S -> (L)|id, L -> S | L,S closure({[S’->.S]}) = {[S’->.S], [S->.(L)], [S->.id]} goto goto(I, X)์ด๋ฉด ์ ์ X๋ค๋ก ์ฎ๊ธฐ๊ณ closure๋ฅผ ์ทจํ๋ค X๊ฐ ์์ผ๋ฉด ๋ฃ์ง ์๋๋ค I={[G->E=E], [E->E.+T]} ์ผ๋, goto(I, +) = closure({E->E+.T}) : ์ ์ +๋ค๋ก ์ฎ๊น C0 ์์ฑ๊ท์น S’->S์์๋ถํฐ ์ฐจ๋ก๋ก closure์ goto๋ฅผ ์ ์ฉํ์ฌ ์ป์ ๋ชจ๋ ํ๋นํ LR(0)์ ์์ดํ
์งํฉ๋ค
Item์ ์ข
๋ฅ
[A->X.Y] : X!=ฮต์ผ๋ kernel item [A->.X] : closure item [A->X.] : reduce item SLR ํ์ฑ ํ
์ด๋ธ ๋ง๋ค๊ธฐ reduce Item์ด [X->ฮฑ.]์ผ๋, FOLLOW(X)์ ๋ชจ๋ terminal์๋ง reduce action์ ๋ฃ๋๋ค ๋๋จธ์ง๋ LR(0)๊ณผ ๋๊ฐ๋ค LR(0)๋ณด๋ค conflict๊ฐ ์ ์ด, ๋ ์ ๊ตํ๋ค๊ณ ํ ์ ์๋ค. LALR Parsing ์ ๊ตํ ์์ LR(0) < SLR < LALR(1) < LR(1)
ํ์ ์ํ์ ๊ฐ์ SLR = LALR « LR(1)
SDD, AST SDD (Syntax Directed Definition) SDD : semnatic action์ ์ ์ํ๋ ์ถ์์ ์ธ ๋ช
์ธ์ Semnatic Actions : ๊ท์น์ ๋ํ Action Yacc/Bison : $$, $1, $2, ... ์ฌ์ฉ ANTLR : $<name> ์ฌ์ฉ Type declaration Attribute ์ข
๋ฅ synthesized attr. : children์ ์ํด ๊ณ์ฐ (terminal) inherited attr. : parent, sibling์ ์ํด ๊ณ์ฐ AST (Abstract Syntax Tree) ํ์คํธ๋ฆฌ์์ ๋ถํ์ํ ์ ๋ณด๋ฅผ ์ ๊ฑฐํ ํํ AST๋ฅผ ๋ง๋๋ ๋ฐฉ๋ฒ ํ์ฑ๋จ๊ณ์์ ๋ง๋ค๊ธฐ : LL, LR ํ์คํธ๋ฆฌ๋ฅผ ์ํํ๋ฉด์ ๋ง๋ค๊ธฐ : SDD ์ฌ์ฉ (Yacc etc.) evaluation : ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ฉด์ ์์
ํ๋ ํ์ On-the-fly evaluation S-attributed SDD: synthesized attribute๋ง ๊ฐ์ง๊ณ ์๋ SDD L-attributed SDD: synthesized attribute๋ง ๊ฐ์ง๋ ๊ฒฝ์ฐ + ๊ฐ์ด ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ํ๋ฌ ๊ณ์ฐ์ด ์ด๋ฃจ์ด์ง๋ ๊ฒฝ์ฐ IR (Intermediate Representation) IR์ด๋? Tree๋ Instruction list ํํ instruction(node)๊ฐ ์ ์ด์ผ ์ต์ ํ/๋ฒ์ญ์ ์ข์ High Level IR High์ Low๋ ์๋์ ์ธ ๊ฐ๋
High level IR: ์ฌ๊ธฐ์๋ AST์ ๋ณํ๋ง ์๊ฐ ์ข
๋ฅ : AST, TCOL Low Level IR ๋จ์ํ instruction์ผ๋ก ๊ตฌ์ฑ ๊ฐ์๊ธฐ๊ณ(์ฃผ๋ก RISC)๋ฅผ emulate N-tuple ํ๊ธฐ๋ฒ (3-address code) a = b OP c
์ผ๋ฐ์ ์ผ๋ก ๊ธฐ๊ณ์ด๊ฐ ๊ฐ์ง๋ ํผ์ฐ์ฐ์ ๊ฐ์ <= 3 quadruple : (์ฐ์ฐ์, ํผ์ฐ์ฐ์1, ํผ์ฐ์ฐ์2, ๊ฒฐ๊ณผ) Stack machine code Java byte code, U-code : AST๋ก๋ถํฐ ์์ฑ์ด ์ฉ์ด Tree ํํ ๊ธฐ๊ณ์ด ์์ฑ ์ฉ์ด IR ์์ GCC - GIMPLE (3-address code) GCC์ ์ค๊ฐ์ฝ๋ : GENERIC -> GIMPLE -> RTL 1D.1954 = x*10 // D.1954๋ ์์๋ณ์ 2gimple_assign <mult_exprt, D.1954, x, 10> LLVM - bit (3-address code) LLVM IR : ์ธ์ด์ ๋จธ์ ์ ๋
๋ฆฝ์ 1@var = global i32 14 ; ์ ์ญ๋ณ์ var์ 14 ๋์
2define i32 @main() nounwind { ; i32(int) ๋ฐํํ 3 entry: 4 %a = alloca i32, align 4 ; ์ง์ญ๋ณ์ a ์ ์ธ, int ํ ๋น 5 %1 = load i32 * @var ; %1 ์์๋ณ์์ var๊ฐ ๋์
6 ret i32 %1 ; ์์๋ณ์ ๊ฐ ๋ฐํ 7} JVM - byte code (stack machine code) ๊ฐ์ ๊ธฐ๊ณ ์ฝ๋ (Bytecode, MSIL) ๊ฐ์ ๊ธฐ๊ณ์์ ๋์ํ๋๋ก ํจ ์ด์์ฑ, ํธํ์ฑ์ด ๋ชฉ์ : java bytecode๋ machine ํธํ์ฑ, c# msil์ language ํธํ์ฑ 1public Employee(String strName, int num) 2{name = strName; idNumber = num; storeData(strName, num);} 3Method Employee(java.lang.String, int) 4 50 aload_0 ; 0๋ฒ์งธ ๋ก์ปฌ๋ณ์(this)๋ฅผ ์คํ์ push 61 invokespecial #3 <Method java.lang.Object()> ; ํจ์ ํธ์ถ 7--- 84 aload_0 95 aload_1 ; strName์ ์คํ์ push 106 putfield #5 <Field java.lang.String name> ; name์ strName ๋์
11--- 129 aload_0 1310 iload_2 ; num์ ์คํ์ push 1411 putfield #7 <Field int idNumber> ; idNumber์ num ๋์
15--- 1614 aload_0 1715 aload_1 ; strName์ ์คํ์ push 1816 iload_2 ; num์ ์คํ์ push 1917 invokespecial #9 <Method void storeData(java.lang.String, int)> ; ํจ์ ํธ์ถ 2020 return line number : ๋ช
๋ น์ด ์์ํ๋ ๋ฐ์ดํธ ์ฃผ์ aload : ๊ฐ์ฒด๋ฅผ push, iload : ์ ์๋ฅผ push ์๋๋ aload๊ฐ ๋ช
๋ น, ์์ฃผ ์ฐ๋ ๋ช
๋ น aload 0์ ๋ฌถ์ด์ bind -> aload_0 CIL (Common Intermediate Language) (stack machine code) C#, VB.NET, J# ๋ฑ์์ ์ฌ์ฉ MSIL์ ์๋ ์ด๋ฆ 1.assembly Hello {} ; .assembly: ์ด์
๋ธ๋ฆฌ ์ ์ธ 2.assembly extern mscorlib {} 3.method static void Main() { 4 .entrypoint 5 .maxstack 1 6 ldstr "Hello, world!" ; stack์ ์ ์ฅ 7 call void [mscorlib]System.Console::WriteLine(string) 8 ret 9} GCC RTL(Register Transfer Language) (Tree๊ตฌ์กฐ ์ฝ๋) Lisp S-expression ์ฌ์ฉ 1(set (reg:SI 140) 2 (plus:SI (reg:SI 138) 3 (reg:SI 139))) => reg140 = reg138+reg139 IR generation 3-address Translation ๊ท์น Binary operations: t = [[el OP e2]] Unary operations: t = [[OP el]] Array access: t = [[ v[e] ]] Structure access: t = [[ v.f ]] Short-circuit OR: t = [[ el SC-OR e2]] Statement sequence: [[s1; s2; ...; sN]] Variable assignment: [[ v = e ]] Array assignment: [[ v[e1] = e2 ]] If: [[ if(e) then s ]], [[ if(e) then s1 else s2]] While: [[ while (e) s ]] Switch: [[ switch (e) case v1:s1, ..., case vN:sN ]] Function Call: [[ call f(e1, e2, ..., eN) ]] Fucntion Return: [[ return e ]] Statement Expression Statement๋ expression ์ฒ๋ผ ๊ฐ์ ๊ฐ์ง๋๋ก ํ์ฅ t = [[ S ]]๋ฅผ ์ถ๊ฐํ์ฌ ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ์ Nested Expressions t = [[ (a - b) * (c + d) ]] t = [[ if c then if d then a = b ]] ๊ฐ์ฅ ํฐ ๋ฉ์ด๋ฆฌ๋ถํฐ ๋ฐ๊พผ๋ค Storage Management 2๊ฐ์ง Storage Register : ๋น ๋ฅธ ์ ๊ทผ, ๊ฐ์ ์ ๊ทผ ๋ถ๊ฐ Memory : ์๋์ ์ผ๋ก ๋๋ฆฐ ์ ๊ทผ, ๊ฐ์ ์ ๊ทผ ๊ฐ๋ฅ 2๊ฐ์ง ์ ๊ทผ ๋ฐฉ์ All memory approach ๋ชจ๋ ๋ณ์๋ฅผ memory์ ์ ์ฅ, ๊ฐ๋ฅํ๊ฒ๋ง register Standard approach Global, Statics, Local(composite)๋ memory์ ์ ์ฅ Local(scalar)๋ memory ๋๋ virtual register์ ์ ์ฅ Memory์ 4๋ ์์ญ Code space : ๋ช
๋ น์ด๋ฅผ ์ ์ฅ read-only์ผ๋ ๋น ๋ฆ Static data : ํ๋ก๊ทธ๋จ๊ณผ lifetime์ ํจ๊ปํ๋ ๋ฐ์ดํฐ Stack : Local ๋ณ์๋ค Heap : ๋์ ์ผ๋ก ํ ๋น๋๋ ๋ฐ์ดํฐ File Format Windows : PE (Portable Executable) Unix : ELF (Executable and Linkable Format) ๋ณ์ ๋ฐ์ธ๋ฉ environment : <๋ณ์, storage location> ์ ๋ณด state: <๋ณ์, ๊ฐ> ์ ๋ณด ์ด๋ค ๋ณ์ N์ด storage location S์ ์ง์ ๋๋ฉด ๋ฐ์ธ๋ฉ ๋๋ค๊ณ ํ๋ค Static Allocation ํ๋ก๊ทธ๋จ ์ํํ๋ ๋์ ๋ณํ์ง ์๋ location์ผ๋ก ๋ฐ์ธ๋ฉ Heap Allocation ์ฐ์์ ์ธ global ์์ญ์ ์ผ๋ถ๋ฅผ OS๋ก๋ถํฐ ๋ฐ์ ๊ฒ ํ๋ก๊ทธ๋จ ์ํ ์ค ์์ฒญ๊ณผ ๋ฐํ Stack Management Run-time stack : ํ ํจ์ call๋ง๋ค ํ๋์ฉ๋๋ frames Activation record : ํจ์ ์ํ์ ์ํ execution env(local var, parameter, return address, etc.) Top frame : ํ์ฌ ์ํ์ค์ธ ํจ์์ frame Stack pointers SP : Frame top FP : Frame base ๋ ๊ฐ๋ฅผ ์ฐ๋ ์ด์ ๊ฐ๊น์ด ๊ฑฐ ๊ธฐ์ค์ผ๋ก offset ๊ณ์ฐ -> small offset ์ ์ง ์ํ ์ค top frame์ ์์น๋ฅผ ์ ์ ์์ Semantic Analysis - Symbol Tables Scope Identifier: ์๋ณ์ Lexical Scope: ํน์ ๋ฒ์ ์๋ณ์์ Scope: ๊ทธ ์๋ณ์์ ์ ์ธ์ด ์ฐธ์กฐ๋๋ lexical scope Symbol Table Name Kind Type Attribute foo func int, int -> int extern m arg int tmp var char const ํ๋์ lexical๋ง๋ค ํ๋์ symbol table symbol table์ ๊ณ์ธต์ ์ด๋ค ํ์ฌ scope์ ์์ผ๋ฉด ์์ scope๋ก ์ฌ๋ผ๊ฐ๋ฉด์ ์ฐพ๋๋ค Symbol Table Implementation AST๊ฐ ๋ง๋ค์ด์ ธ์ผ ๊ฐ๋ฅ Local Table์ hash table ์ฌ์ฉ Global Table์ N-array tree ๊ตฌ์กฐ ์ฌ์ฉ ์ฝ๋๋ฅผ ์์ฐจ๋๋ก ์ฝ์ผ๋ฉด์ ๋ง๋ฌ (scope ์คํ์ ์ฌ์ฉ) Type Checking Type Expressions Array types: T[], T[10] Structure types : {id1: T1, id2: T2 …} Pointer types: T* Function types: T1 X T2 X … X Tn -> T_return Type Judgement A โ E : T A ์ํฉ์์ E๋ Tํ์
์ ๋ง์กฑํ๋ค
A โ if(E) S1 else S2 : T ์ ์กฐ๊ฑด์ ๋ชจ๋ E, S1, S2, A, T์ ๋ํ ๊ฐ์ ์ด ์ฑ๋ฆฝํ ๋ ๊ฒฐ๋ก T๊ฐ ์ฑ๋ฆฝํ๋ค
Proof Tree (ํ์
์ ๋ ํธ๋ฆฌ) ์ญ์ผ๊ฐํ ๋ชจ์ ๋ง์กฑํ๋ proof tree๊ฐ ์๋ค -> ํ์
์ค๋ฅ๊ฐ ์๋ค ๊ทธ ์ธ Semantic Analyses break, continue, goto ๋ฌธ์ด ์ฌ๋ฐ๋ฅธ ์์น์ ์๋ ์ง ๋ฑ ์ปดํ์ผ๋ฌ ํ๋ฐ๋ถ (๋น ๋ฅด๊ณ , ์ค์ ๋์๊ฐ๋ ์ฝ๋๋ก ๋ฐ๊พธ๊ธฐ) Instruction Selection Tree ๊ธฐ๋ฐ Intermediate Representation MEM(e) : ์ฃผ์ e๋ก ์์ํ๋ ๋ฉ๋ชจ๋ฆฌ ํ word์ ๋ด์ฉ TEMP(t) : ๋ ์ง์คํฐ t SEQ(s1, s2): ๋ฌธ์ฅ s1 ์ํ ํ s2 ์ํ ESEQ(s, e): ๋ฌธ์ฅ s ์ํ ํ (๊ฒฐ๊ณผ ์์) e๊ฐ ์ถ๊ฐ ์ํ BINOP(o, e1, e2) : ์ฐ์ฐ์ o, ํผ์ฐ์ฐ์ e1, e2, ๊ฒฐ๊ณผ ์ ์ฅ๋ ์ฃผ์ ๋ฐํ const(i): ์ ์ ์์ i Register Allocation ์ต์ ํ ํ๊ธฐ ์ํด ์ต๋ํ ์์ฃผ ์ฌ์ฉ๋๋ ๊ฒ์ Register์ ์ ์ฅ Interference ์๋ก ๋ค๋ฅธ ๋ definition์ด live range ์์ ๊ณตํต operation์ ๊ฐ์ง๊ณ ์๋ ๊ฒฝ์ฐ
Interference Graph : ์๋ก interfere ํ๋ฉด ์ฐ๊ฒฐํ๋ ๊ทธ๋ํ Graph coloring : ์ฐ๊ฒฐ๋ ๋
ธ๋๋ ๋ค๋ฅธ ์์ผ๋ก ์น ํ๊ธฐ Instruction Scheduling instruction์ ์์๋ฅผ ๋ฐ๊พธ์ด stall ๊ฐ์ ๋ฑ์ ์ค์ฌ์ ์ํ์๋๋ฅผ ๋์ด๋ ๊ฒ
stall : ๋ค๋ฅธ ๋ช
๋ น์ด ์ํ์ ๊ธฐ๋ค๋ฆฌ๋๋ผ CPU๋ฅผ ๋ญ๋นํ๋ ๊ฒ ๋ชฉํ Wasting time์ ์ค์ธ๋ค ๋์ผํ ์ฝ๋๊ฐ ๋์์ผํ๋ค register spilling์ ํผํด์ผํ๋ค Static scheduling ๋จ๊ณ Local basic scheduling, Loop scheduling, global scheduling Local basic scheduling List scheduling : greedy, heuristic, local technique ์ฌ์ฉ precedence graph๋ฅผ ๋ง๋ ๋ค ๊ฐ ๋
ธ๋์ priority function์ ์ ์ฉํ๋ค “ready-operation queue"๋ฅผ ์์ ready operation์ ํ๋ ์ ํ ํ scheduling, ready operation queue๋ฅผ ์
๋ฐ์ดํธํ๋ค. Longest latency-weighted path๋ฅผ ์ด์ฉํด์ ์ฐ์ ์์๋ฅผ ์ ํ๋ค ๊ธฐํ Optimization ๋ฐฉ๋ฒ addr r1 1 -> inc r1 ํน์ ์ฑ์ง์ ๋ ์ง์คํฐ ํ์ฉ ํน์ ๋ชฉ์ ์ ๋ช
๋ น์ด ํ์ฉ Register ๊ฐ mov ์ ๊ฑฐ ์ค๋ณต๋ load ์ ๊ฑฐ Control Flow Optimizations(์ต์ ํ) ์ฃผ์ด์ง ์
๋ ฅ ํ๋ก๊ทธ๋จ์ ์ข ๋ ํจ์จ์ ์ธ ์ฝ๋๋ก ๋ฐ๊พธ๋ ๊ฒ
์ฌ๋ฌ๊ฐ์ง ๋ถ๋ฅ ๋ฐฉ๋ฒ ๋ถ์ : Control Flow Analysis vs Data Flow Analysis ์ต์ ํ Inner basic block(local) vs Inter basic block(global) Cyclic code opt vs Acyclic code opt Control Flow Analysis Control Flow ํ๋ก๊ทธ๋จ์ ๊ฐ๋ฅํ ์ํ์์ (๋ถ๊ธฐ)
Branch Execution -> dynamic control flow : ์คํ ํด๋ด์ผ ํ์ธ ๊ฐ๋ฅ Compiler -> static control flow : ์ปดํ์ผ๋ฌ๊ฐ ๋ถ์ํด์ ์ ์ ์์ Analysis ์ ์ ์ฑ์ง (static property): ํ๋ก๊ทธ๋จ ์ํ ์์ด ๋์ถ ๋๋ ์ฑ์ง CFA(Control Flow Analysis) : ์ฝ๋์ ๋ถ๊ธฐ ๊ตฌ์กฐ๋ฅผ CFG ํํ๋ก ํํ Basic Block ๋์ผํ execution condition์ ์ ์ฉ๋ฐ๋ instruction ๋ฌถ์
instruction ์ธ์๋ branch๊ฐ ์์ Maximal basic block ๊ตฌํ๊ธฐ BB์ leader(์ฒซ๋ฒ์งธ instruction)๋ฅผ ์ฐพ๋๋ค ๋ค์ leader ์ด์ ๊น์ง์ instruction์ ๊ตฌํ๋ค Weighted CFG Profiling: ๋ฐ๋ณตํด์ ์ํํด๋ณด๋ฉด์ ์คํํ์๋ฅผ ์ป์ ์ป์ weight๋ฅผ edge์ ํ์ Control Flow Optimization Acyclic Code Loop๊ฐ ์๋ ์ฝ๋
๋ถ์ ๋ฐ ์ต์ ํ๊ฐ ์๋์ ์ผ๋ก ์ฌ์
์ข
๋ฅ
Inner basic block opt. = Intra opt. = Local opt. Inter basic block opt. = Global opt. Inner Basic Block Optimization Commn subexpression elimination ๊ณตํต๋ ๋ถ๋ถ์ด ์์ผ๋ฉด ํ๋ฒ๋ง ๊ณ์ฐ Algebraic simplification ๋์๋ฒ์น์ ์ด์ฉํ์ฌ ์์ ๊ฐ์ํ ex) x=1*y; -> x=y; Strength reduction ์ฐ์ฐ์์ ๋น์ฉ์ด ์ ์ ๊ฒ์ผ๋ก ๋ฐ๊พธ๊ธฐ ex) x=x*2; -> x=x+x; ex) y=a/4; -> y=a>>2; Constant folding / propagation folding: ์ปดํ์ผ ์๊ฐ์ ์์์์ ์ง์ ์๊ฐ propagation : ๊ณ ์ ๋ ๊ฐ์ ๊ฐ์ง๋ ๋ณ์๋ฅผ ์์๋ก ๋์ฒด Inter Basic Block Optimization Global application of inner basic block optimization
Global common subexpression elimination basic block ๊ฐ์ ๊ณตํต ๋ถ๋ถ์์ ๋ํด ํ๋ฒ๋ง ๊ณ์ฐ Global constant folding / propagation basic block ๊ฐ์ ์์๋ฅผ ์ธ์ํ์ฌ ํ๋ฒ๋ง ๊ณ์ฐ Other transformation
Branch to unconditional branch ๋ถํ์ํ ๋ถ๊ธฐ ์ ๊ฑฐ Unconditional branch to branch ๋ถ๊ธฐ ํ ๋ฐ๋ก ๋ถ๊ธฐ -> ๋ถ๊ธฐ ํ๋ฒ์ผ๋ก ๋ณ๊ฒฝ Branch to next basic block (next instr) ๋ถ๊ธฐ ํ ๋ฐ๋ก ๋ค์ basic block์ผ๋ก ๋ถ๊ธฐ ์ ๊ฑฐ Basic block merging ๋ basic block์ ํฉ์นจ Branch to same target ๊ฐ์ basic block์ผ๋ก ๋ถ๊ธฐํ๋ ๊ฒ์ ์ ๊ฑฐ Branch target expansion ๋ถ๊ธฐ ๋์์ด ๋๋ basic block์ ํฉ์นจ Unreachable code elimination Entry์์ ๋๋ฌํ ์ ์๋ ‘unreachable’ block ์ ๊ฑฐ Loop Optimization Loop๋ ํ๋ฒ optimizeํ๋ฉด ํจ๊ณผ๊ฐ ํฌ๋ค Loop unrolling : ๋ฐ๋ณต๋ฌธ์ ํ์ด์ ๋ฐ๋ณต ํ์๋ฅผ ์ค์ Loop invarient : ๋งค๋ฒ ๋์ผํ ๊ฐ์ ๋ด๋ ๋ฌธ์ฅ์ ๋ฐ๋ณต๋ฌธ ๋ฐ์ผ๋ก ๋นผ๋ Count up to zero : i๋ฅผ ๊ฐ์ํ๋ ๋ฐ๋ณต๋ฌธ์ผ๋ก ๋ณ๊ฒฝ (i๋ฅผ 0๊ณผ ๋น๊ตํ๋ ๊ฒ์ด n๊ณผ ๋น๊ตํ๋ ๊ฒ๋ณด๋ค ๋น ๋ฆ) Dataflow Analysis + Optimization Dataflow Analysis ํ๋ก๊ทธ๋จ ๋ด์ ๊ฐ data ๊ฐ๋ค์ด ์์ฑ/์๋ฉธ๋๋ ์ ๋ณด๋ฅผ ๋ชจ์ผ๋ ๊ฒ Reaching Definition Analysis definition : ํด๋น ๋ณ์๊ฐ assign๋๋ ๊ฒ reach : definition d๊ฐ ํน์ ์์น p์ ๋๋ฌํ๋ค kill : definition d์ ๋๊ฐ์ ํฌ์ธํธ์ฌ์ด์์ ๋ค๋ฅธ definition์ด ์กด์ฌํ๋ค GEN/KILL GEN: ๋ธ๋ก ๋ด์์ ์์ฑ๋ definition KILL: ๋ธ๋ก ๋ด์์ ์๋ฉธ๋ definition IN/OUT IN : ์ด์ ๋ธ๋ก์ OUT์ ํฉ์งํฉ OUT : IN์์ GEN์ ๋ํ๊ณ KILL์ ๋บ ๊ฒ django์์ swagger ๋ฌธ์ํ ๊ตฌํํ๊ธฐ ๊ฐ์ ์ฅ๊ณ ํ๋ ์์ํฌ๋ฅผ ์ฌ์ฉํ์ฌ ๊ธฐ๋ณธ์ ์ธ CRUD ๊ธฐ๋ฅ๊ณผ, REST API๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์์๋ณด์.
ํ๋ก์ ํธ ๊ตฌ์กฐ 1. 2โโโ db.sqlite3 3โโโ djtest (๋ฉ์ธ ์ฑ) 4โ โโโ __init__.py 5โ โโโ asgi.py 6โ โโโ settings.py 7โ โโโ urls.py 8โ โโโ views.py 9โ โโโ wsgi.py 10โโโ manage.py 11โโโ paste (์์ฑํ ์ฑ) 12โ โโโ __init__.py 13โ โโโ admin.py 14โ โโโ apps.py 15โ โโโ migrations 16โ โโโ models.py 17โ โโโ serializers.py 18โ โโโ tests.py 19โ โโโ urls.py 20โ โโโ views.py 21โโโ requirements.txt ์์ฃผ ์ฌ์ฉํ๋ Django ๋ช
๋ น์ 1# ์๋ก์ด Django ํ๋ก์ ํธ๋ฅผ ์์ฑ 2python manage.py startproject 3# ์๋ก์ด Django ์ฑ์ ์์ฑ 4python manage.py startapp 5# ๋ฐ์ดํฐ๋ฒ ์ด์ค์ ์ ์ฉํ ๋ง์ด๊ทธ๋ ์ด์
ํ์ผ์ ์์ฑ 6python manage.py makemigrations 7# ๋ง์ด๊ทธ๋ ์ด์
ํ์ผ์ ์ค์ ๋ฐ์ดํฐ๋ฒ ์ด์ค์ ์ ์ฉ 8python manage.py migrate 9# ๊ด๋ฆฌ์(superuser) ๊ณ์ ์ ์์ฑ 10python manage.py createsuperuser 11# ํ๋ก์ ํธ์ ํ
์คํธ ์ผ์ด์ค๋ฅผ ์คํ 12python manage.py test 13# ํ
์คํธ์ฉ ์๋ฒ๋ฅผ ํน์ ์ค์ ์ผ๋ก ์คํ 14python manage.py testserver CRUD ๊ตฌํ Paste ๋ชจ๋ธ ์ ์ 1from django.db import models 2 3class Paste(models.Model): 4 title = models.CharField(max_length=100) 5 content = models.TextField() 6 # auto_now_add : ๊ฐ์ฒด๊ฐ ์ฒ์ ์์ฑ๋ ๋๋ง ํ์ฌ ๋ ์ง์ ์๊ฐ์ ์๋์ผ๋ก ์ค์ 7 created_at = models.DateTimeField(auto_now_add=True) 8 # auto_now : ๊ฐ์ฒด๊ฐ ์ ์ฅ๋ ๋๋ง๋ค ํ์ฌ ๋ ์ง์ ์๊ฐ์ ์๋์ผ๋ก ์ค์ 9 updated_at = models.DateTimeField(auto_now=True) 10 class Meta: 11 ordering = ['-created_at'] 12 def __str__(self): 13 return self.title Serializer ์ ์ 1from rest_framework import serializers 2from .models import Paste 3 4class PasteSerializer(serializers.ModelSerializer): 5 class Meta: 6 model = Paste 7 fields = '__all__' 8 # ์ง์ ์ง์ ํ๋ ๋ฐฉ๋ฒ 9 # fields = ['title', 'content'] View ๊ตฌํ PasteView
1class PasteView(APIView): 2 def get(self, _): 3 pastes = Paste.objects.all() 4 serializer = PasteSerializer(pastes, many=True) 5 return Response(serializer.data, status=status.HTTP_200_OK) 6 7 def post(self, request): 8 serializer = PasteSerializer(data=request.data) 9 if serializer.is_valid(): 10 serializer.save(user=request.user) 11 return Response(serializer.data, status=status.HTTP_201_CREATED) 12 return Response(serializer.errors, status=status.HTTP_400_BAD_REQUEST) PasteDetailView
1class PasteDetailView(APIView): 2 def get(self, _, pk): 3 try: 4 paste = Paste.objects.get(pk=pk) 5 serializer = PasteSerializer(paste) 6 return Response(serializer.data, status=status.HTTP_200_OK) 7 except Paste.DoesNotExist: 8 return Response(status=status.HTTP_404_NOT_FOUND) 9 10 def put(self, request, pk): 11 try: 12 paste = Paste.objects.get(pk=pk) 13 except Paste.DoesNotExist: 14 return Response(status=status.HTTP_404_NOT_FOUND) 15 16 if paste.user != request.user: 17 return Response(status=status.HTTP_403_FORBIDDEN) 18 19 serializer = PasteSerializer(paste, data=request.data) 20 if serializer.is_valid(): 21 serializer.save() 22 return Response(serializer.data, status=status.HTTP_200_OK) 23 return Response(serializer.errors, status=status.HTTP_400_BAD_REQUEST) 24 25 def delete(self, request, pk): 26 try: 27 paste = Paste.objects.get(pk=pk) 28 except Paste.DoesNotExist: 29 return Response(status=status.HTTP_404_NOT_FOUND) 30 31 paste.delete() 32 return Response(status=status.HTTP_204_NO_CONTENT) urls.py 1from django.urls import path 2from paste.views import * 3 4urlpatterns = [ 5 path('', PasteView.as_view(), name='paste_list_create'), 6 path('<int:pk>', PasteDetailView.as_view(), name='paste_get_update_delete'), 7] Swagger ์ ์ฉ PasteView PasteView
1class PasteView(APIView): 2 @swagger_auto_schema( 3 operation_description="Get list of pastes", 4 operation_summary="Get list of pastes", 5 responses={200: PasteSerializer(many=True)}, 6 ) 7 def get(self, _): 8 ... 9 10 @swagger_auto_schema( 11 operation_description="Create a new paste", 12 operation_summary="Create a new paste", 13 request_body=PasteSerializer, 14 responses={201: PasteSerializer, 400: "Bad Request"}, 15 ) 16 def post(self, request): 17 ... PasteDetailView
1class PasteDetailView(APIView): 2 @swagger_auto_schema( 3 operation_description="Get a paste by ID", 4 operation_summary="Get a paste by ID", 5 responses={200: PasteSerializer, 404: "Not Found"}, 6 ) 7 def get(self, _, pk): 8 ... 9 10 @swagger_auto_schema( 11 operation_description="Update a paste by ID", 12 operation_summary="Update a paste by ID", 13 request_body=PasteSerializer, 14 responses={ 15 200: PasteSerializer, 16 400: "Bad Request", 17 403: "Forbidden", 18 404: "Not Found", 19 }, 20 ) 21 def put(self, request, pk): 22 ... 23 24 @swagger_auto_schema( 25 operation_description="Delete a paste by ID", 26 operation_summary="Delete a paste by ID", 27 responses={204: "No Content", 404: "Not Found"}, 28 ) 29 def delete(self, request, pk): 30 ... swagger ์ ์ฉ ๊ฒฐ๊ณผ django์์ JWT ์ธ์ฆ ๊ตฌํํ๊ธฐ ์ฅ๊ณ ์์๋ djangorestframework-simplejwt ํจํค์ง๋ฅผ ์ฌ์ฉํ์ฌ JWT ์ธ์ฆ์ ๊ตฌํํ ์ ์๋ค.
requirements 1pip install djangorestframework-simplejwt settings.py 1INSTALLED_APPS = [ 2 ... 3 'rest_framework', 4 'rest_framework_simplejwt', 5] 1REST_FRAMEWORK = { 2 # ๊ธฐ๋ณธ ์ธ์ฆ ํด๋์ค๋ฅผ ์ค์ 3 'DEFAULT_AUTHENTICATION_CLASSES': ( 4 'rest_framework_simplejwt.authentication.JWTAuthentication', 5 ), 6 # ๊ธฐ๋ณธ ์คํค๋ง ํด๋์ค๋ฅผ ์ค์ , CoreAPI๋ฅผ ์ฌ์ฉํ์ฌ ์๋์ผ๋ก API ๋ฌธ์ํ๋ฅผ ์์ฑ 7 'DEFAULT_SCHEMA_CLASS': 'rest_framework.schemas.coreapi.AutoSchema', 8 # ๊ธฐ๋ณธ ๊ถํ ํด๋์ค๋ฅผ ์ค์ , AllowAny๋ฅผ ์ฌ์ฉํ์ฌ ๋ชจ๋ ์์ฒญ์ ํ์ฉ 9 'DEFAULT_PERMISSION_CLASSES': ( 10 'rest_framework.permissions.AllowAny', 11 ), 12} 1from datetime import timedelta 2 3SIMPLE_JWT = { 4 # ์ก์ธ์ค ํ ํฐ์ ์ ํจ ๊ธฐ๊ฐ์ ์ค์ 5 'ACCESS_TOKEN_LIFETIME': timedelta(minutes=30), 6 # ๋ฆฌํ๋ ์ ํ ํฐ์ ์ ํจ ๊ธฐ๊ฐ์ ์ค์ 7 'REFRESH_TOKEN_LIFETIME': timedelta(days=1), 8 # ๋ฆฌํ๋ ์ ํ ํฐ์ด ๊ฐฑ์ ๋ ๋๋ง๋ค ์๋ก์ด ๋ฆฌํ๋ ์ ํ ํฐ์ ๋ฐ๊ธํ ์ง ์ฌ๋ถ๋ฅผ ์ค์ 9 'ROTATE_REFRESH_TOKENS': False, 10 # ๋ฆฌํ๋ ์ ํ ํฐ์ด ๊ฐฑ์ ๋ ํ ์ด์ ํ ํฐ์ ๋ธ๋๋ฆฌ์คํธ์ ์ถ๊ฐํ ์ง ์ฌ๋ถ๋ฅผ ์ค์ 11 'BLACKLIST_AFTER_ROTATION': True, 12 13 # JWT ํ ํฐ์ ์ํธํ ์๊ณ ๋ฆฌ์ฆ์ ์ค์ 14 'ALGORITHM': 'HS256', 15 # JWT ํ ํฐ์ ์๋ช
ํ ๋ ์ฌ์ฉํ ํค๋ฅผ ์ค์ 16 'SIGNING_KEY': SECRET_KEY, 17 # ํ ํฐ ๊ฒ์ฆ์ ์ฌ์ฉํ ๊ณต๊ฐ ํค๋ฅผ ์ค์ 18 'VERIFYING_KEY': None, 19 # ํ ํฐ์ ๋์์(aud) ํด๋ ์์ ์ค์ 20 'AUDIENCE': None, 21 # ํ ํฐ์ ๋ฐ๊ธ์(iss) ํด๋ ์์ ์ค์ 22 'ISSUER': None, 23 24 # ์ธ์ฆ ํค๋ ํ์
์ ์ค์ 25 'AUTH_HEADER_TYPES': ('Bearer',), 26 # ์ธ์ฆ ํค๋์ ์ด๋ฆ์ ์ค์ 27 'AUTH_HEADER_NAME': 'HTTP_AUTHORIZATION', 28 # ์ฌ์ฉ์ ๋ชจ๋ธ์์ ์ฌ์ฉ์ ID ํ๋๋ฅผ ์ค์ 29 'USER_ID_FIELD': 'id', 30 # JWT ํ ํฐ์์ ์ฌ์ฉ์ ID๋ฅผ ์ ์ฅํ ํด๋ ์์ ์ค์ 31 'USER_ID_CLAIM': 'user_id', 32 33 # ์ธ์ฆ์ ์ฌ์ฉํ ํ ํฐ ํด๋์ค๋ค์ ์ค์ 34 'AUTH_TOKEN_CLASSES': ('rest_framework_simplejwt.tokens.AccessToken',), 35 # ํ ํฐ์ ์ ํ์ ์ ์ฅํ ํด๋ ์์ ์ค์ 36 'TOKEN_TYPE_CLAIM': 'token_type', 37} urls.py 1from django.urls import path 2from rest_framework_simplejwt.views import TokenObtainPairView, TokenRefreshView 3from rest_framework_simplejwt.authentication import JWTAuthentication 4 5urlpatterns = [ 6 # JWT ํ ํฐ์ ๋ฐ๊ธํ๋ ๋ทฐ 7 path("token/", TokenObtainPairView.as_view(), name="token_obtain_pair"), 8 # JWT ํ ํฐ์ ๊ฐฑ์ ํ๋ ๋ทฐ 9 path("token/refresh/", TokenRefreshView.as_view(), name="token_refresh"), 10] views.py 1from rest_framework import permissions 2from rest_framework_simplejwt.authentication import JWTAuthentication 3from drf_yasg.utils import swagger_auto_schema 4 5 6class PasteView(APIView): 7 8 def get(self, request): 9 ... 10 11 def post(self, request): 12 ... 13 14 def get_permissions(self): 15 # SAFE_METHODS : GET, HEAD, OPTIONS 16 if self.request.method in permissions.SAFE_METHODS: 17 self.permission_classes = [permissions.AllowAny] 18 else: 19 self.authentication_classes = [JWTAuthentication] 20 self.permission_classes = [permissions.IsAuthenticated] 21 return super().get_permissions() 22 23 24class PasteDetailView(APIView): 25 26 def get(self, request, pk): 27 ... 28 29 def put(self, request, pk): 30 ... 31 32 def delete(self, request, pk): 33 ... 34 35 def get_permissions(self): 36 # SAFE_METHODS : GET, HEAD, OPTIONS 37 if self.request.method in permissions.SAFE_METHODS: 38 self.permission_classes = [permissions.AllowAny] 39 else: 40 self.authentication_classes = [JWTAuthentication] 41 self.permission_classes = [permissions.IsAuthenticated] 42 return super().get_permissions() ๊ฒฐ๊ณผ TokenObtainPairView๋ฅผ ํตํด access token๊ณผ refresh token์ ๋ฐ๊ธ๋ฐ์ ์ ์๋ค. TokenRefreshView๋ฅผ ํตํด refresh token์ ์ฌ์ฉํ์ฌ access token์ ๊ฐฑ์ ํ ์ ์๋ค. access token๊ณผ refresh token์ settings.py์์ ์ค์ ํ ์ ํจ ๊ธฐ๊ฐ์ ๋ฐ๋ผ ๋ง๋ฃ๋๋ค. Blacklist ์ ์ฉ settings.py 1INSTALLED_APPS = [ 2 ... 3 'rest_framework_simplejwt.token_blacklist', 4] 1SIMPLE_JWT = { 2 ... 3 # ๋ธ๋๋ฆฌ์คํธ์ ํ ํฐ์ ์ถ๊ฐํ ๋ ์ฌ์ฉํ ๋ชจ๋ธ์ ์ค์ 4 'BLACKLIST_AFTER_ROTATION': True, 5} ๊ฒฐ๊ณผ TokenRefreshView๋ฅผ ํตํด ํ ํฐ์ด ์ฌ๋ฐ๊ธ๋ ๋, ์ด์ refresh token์ ๋ธ๋๋ฆฌ์คํธ์ ์ถ๊ฐํ๋ค. ์ํฉ ํ
์ปค ๋ถํธ์บ ํ์์ ํํ๋ก์ ํธ๋ฅผ ์งํ ์ค์ด๋ค. ๋จ์ํ
์คํธ ์ฝ๋๋ ์์ฑ์ด ์๋ฃ๋์๊ณ , ํตํฉํ
์คํธ ์ฝ๋๋ฅผ ์์ฑ ์ค์ด๋ค. sqlite in-memory db๋ฅผ ์ฌ์ฉํด์ ํ
์คํธ ์ค์ธ๋ฐ, ํ
์ด๋ธ์ด ์๋ค๋ ์๋ฌ๊ฐ ๋ฐ์ํ๋ค. ํ
์คํธ ์ ์ ํ
์ด๋ธ์ ์์ฑํ๋ ์ฝ๋๊ฐ ์คํ๋จ์๋ ๋ถ๊ตฌํ๊ณ , ์๋ฌ๊ฐ ๋ฐ์ํ๋ค. ์ธ๋ฉ๋ชจ๋ฆฌ๊ฐ ์๋ ํ์ผ๋ก ์ ์ฅํ๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๋ฉด ์๋ฌ๊ฐ ๋ฐ์ํ์ง ์๋ ๊ฒ์ ๋ณด๊ณ ๋ฌธ์ ์ ์์ธ์ ํ์
ํ ์ ์์๋ค. ์ฝ๋ 1from database import Base, engine 2from fastapi.testclient import TestClient 3 4from main import app 5from models import * 6 7# ํ
์ด๋ธ์ ์์ฑํ๋ ์ฝ๋์ด๋ค 8Base.metadata.create_all(bind=engine) 9 10client = TestClient(app) 11 12 13class TestUserApi: 14 15 def test_create_user(self): 16 test_nickname = "test_nickname" 17 # ์๋ ์์ฒญ์ ์ฒ๋ฆฌํ๋ ์ฝ๋์์ ์ค๋ฅ๊ฐ ๋ฐ์ํ๋ค 18 response = client.post( 19 "/api/users", 20 json={"nickname": test_nickname}, 21 ) 22 assert response.status_code == 200 23 assert response.json()["nickname"] == test_nickname ์์ธ ํ
์ด๋ธ์ ์์ฑํ ๋ ๋ง๋ค์ด์ง๋ ์ธ์
๊ณผ TestClient๊ฐ ์์ฒญ์ ์ฒ๋ฆฌํ ๋ ์ฌ์ฉํ๋ ์ธ์
์ด ๋ค๋ฅด๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ TestClient๋ด์ get_db() ํจ์๋ฅผ ์์๋ก ์ฃผ์
ํ๋ค ๋ฐ์ดํฐ๋ฒ ์ด์ค๋ฅผ ์ฐ๊ฒฐํ ๋, ๋จ์ผ ์ธ์
์ ์ฌ์ฉํ๋๋ก ํ๋ค. 1from database import Base, engine, get_db 2from sqlalchemy.orm import sessionmaker 3from fastapi.testclient import TestClient 4 5from main import app 6from models import * 7 8Base.metadata.create_all(bind=engine) 9 10client = TestClient(app) 11 12# ํ
์คํธ์์ ์ฌ์ฉํ ์ธ์
์ ์์ฑํ๋ค 13TestingSessionLocal = sessionmaker(autocommit=False, autoflush=False, bind=engine) 14 15 16Base.metadata.create_all(bind=engine) 17 18# get_db() ํจ์๋ฅผ ์ฌ์ ์ํ๋ค 19def override_get_db(): 20 try: 21 db = TestingSessionLocal() 22 yield db 23 finally: 24 db.close() 25 26# get_db() ํจ์๋ฅผ ์ฌ์ ์ํ ํจ์๋ฅผ ์ฃผ์
ํ๋ค 27app.dependency_overrides[get_db] = override_get_db 28 29 30class TestUserApi: 31 32 def test_create_user(self): 33 test_nickname = "test_nickname" 34 response = client.post( 35 "/api/users", 36 json={"nickname": test_nickname}, 37 ) 38 assert response.status_code == 201 39 assert response.json()["nickname"] == test_nickname 1engine = create_engine( 2 os.getenv("DATABASE_URL"), 3 # sqlite๋ฅผ ์ฌ์ฉํ ๋, ์ฌ๋ฌ ์ค๋ ๋์์ ์ฐ๊ฒฐ์ด ๊ฐ๋ฅํ๋๋ก ์ค์ ํ๋ค 4 connect_args={"check_same_thread": False}, 5 # ๋จ์ผ ์ธ์
์ ์ฌ์ฉํ๋๋ก ์ค์ ํ๋ค 6 poolclass=StaticPool, 7) ๋ฐฐ๊ฒฝ ํ
์ปค ๋ถํธ์บ ํ ์ต์ข
๋ฐํ ์ ๋ ์ด๋ค. gpt ํ๋กฌํํธ ๋ถ๋ถ ์์ ์ main ๋ธ๋์น์ ๋ฐ์ํ๊ณ , EC2 ์๋ฒ์ ๋ฐฐํฌํ๋ค. ๋ฌธ์ ๋ฐฐํฌํ ์๋ฒ์์ websocket ์ฐ๊ฒฐ์ด 404 ์๋ฌ๋ฅผ ๋ฐํํ๋ค. (๋ด์ผ์ด ์ต์ข
๋ฐํ์ธ๋ฐ,,,) ๋ค๋ฅธ http ์์ฒญ์ ์ ์์ ์ผ๋ก ์ฒ๋ฆฌ๋์ง๋ง ์น์์ผ๋ง ์ฒ๋ฆฌ๋์ง ์๋ ๊ฒ์ ํ์ธํ๋ค. nginx์ log 1{IP์ฃผ์} - - [02/Aug/2024:10:59:04 +0000] "GET /ws/chatrooms/294?user_id=296 HTTP/1.1" 404 22 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/17.5 Safari/605.1.15" 2{IP์ฃผ์} - - [02/Aug/2024:10:59:05 +0000] "GET /ws/chatrooms/294?user_id=296 HTTP/1.1" 404 22 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/17.5 Safari/605.1.15" ์ฌ๊ณ ํ๋ฆ nginx ์ค์ ๋ฌธ์ ์ธ๊ฐ? X nginx ์ค์ ์ ๋ณ๊ฒฝ๋์ง ์์๋ค. ๋ฐฐํฌํ๊ฒฝ์ ๋ฌธ์ ์ธ๊ฐ? X ๋ก์ปฌ์์ ์คํํ ์๋ฒ์์๋ ๋์ผํ ๋ฌธ์ ๊ฐ ๋ฐ์ํ์๋ค. ์ด๋ฒ ๋ฐฐํฌ์์ ๋ณ๊ฒฝ๋ ์์ค์ฝ๋๊ฐ ๋ฌธ์ ์ธ๊ฐ? X ์ก์์ผ๋ก ํ์ธํ์ ๋๋, ๋ณ๊ฒฝ๋ ๋ถ๋ถ์ด ์น์์ผ๊ณผ ๊ด๋ จ์ด ์๋ค. ๋ก์ปฌ์์ ์ด์ ๋ฒ์ ์ผ๋ก reset ํ ์๋ ํด๋ณด์์ง๋ง ๋ฌธ์ ๊ฐ ํด๊ฒฐ๋์ง ์์๋ค. Docker image ๋ฌธ์ ์ธ๊ฐ? X ๋ฐฑ์๋ ์๋ฒ๋ python:slim ์ด๋ฏธ์ง๋ฅผ ์ฌ์ฉํ๊ณ ์์ผ๋ฉฐ, ํด๋น ์ด๋ฏธ์ง๊ฐ ๋ณ๊ฒฝ๋์ด์ ๋ฌธ์ ๊ฐ ๋ฐ์ํ ๊ฐ๋ฅ์ฑ์ด ์๋ค๊ณ ์๊ฐํ๋ค. ๋ก์ปฌ์์ docker image๋ฅผ ์ฌ์ฉํ์ง ์๊ณ ์คํํด๋ณด์์ง๋ง ๋ฌธ์ ๊ฐ ํด๊ฒฐ๋์ง ์์๋ค. ์ด๋, ๋ก๊ทธ์์ warning ๋ฉ์์ง๋ฅผ ํ์ธํ๋ค. WARNING: No supported WebSocket library detected. Please use "pip install 'uvicorn[standard]'", or install 'websockets' or 'wsproto' manually. ์์ธ ๋ชจ์ข
์ ์ด์ ๋ก, ์ด์ ์ ๊ฐ๋ฐ/๋ฐฐํฌํ ๋์๋ ์กด์ฌํ๋ ์น์์ผ ๊ด๋ จ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๊ฐ ์ฌ๋ผ์ง ๊ฒ์ด๋ค. ์ค๋ฅ๋ฅผ ํด๊ฒฐํ๊ณ ์กฐ์ฌํด๋ณธ ๊ฒฐ๊ณผ fastapi ๋ ํฌ์งํ ๋ฆฌ์ 6์๊ฐ ์ merge๋ PR์ ํ์ธํ ์ ์์๋ค. (https://github.com/fastapi/fastapi/pull/11935) ํด๋น PR์์๋ pip install fastapi[standard] ๋ฅผ ํตํด ํ์ค ์ข
์ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ์ค์นํ๋ ๊ธฐ๋ฅ์ด ์ถ๊ฐ๋์๋ค. ์ด๋ก ์ธํด, uvicorn[standard] ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ์ค์นํ์ง ์์์ ๋, ์น์์ผ ๊ด๋ จ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๊ฐ ์ค์น๋์ง ์์ ๋ฐ์ํ ๋ฌธ์ ์๋ค. ํด๊ฒฐ requirements.txt์ websockets๋ฅผ ์ถ๊ฐํด์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์๋ค. ๋ฐฐ์ด ์ ์ค์ํ ํ๋ก์ ํธ๋ฅผ ํ ๋ requirements.txt์ ํญ์ ๊ฐ ๋ผ์ด๋ธ๋ฌ๋ฆฌ์ ๋ฒ์ ์ ๋ช
์ํด์ผ๊ฒ ๋ค๋ ์๊ฐ์ด ๋ค์๋ค. ์ด๋ฒ์๋ ๋ฒ์ ์ ๋ช
์ํ๋ค๋ฉด, ๋ผ์ด๋ธ๋ฌ๋ฆฌ๊ฐ ์
๋ฐ์ดํธ ๋๋๋ผ๋ ๋ฌธ์ ๊ฐ ๋ฐ์ํ์ง ์์์ ๊ฒ์ด๋ค. ๋ํ, ๋ก๊ทธ๋ฅผ ์ ํ์ธํ๊ณ , warning ๋ฉ์์ง๋ฅผ ๋์น์ง ์๋๋ก ์ฃผ์ํด์ผ๊ฒ ๋ค. Unit Test (๋จ์ ํ
์คํธ) ๊ฐ์ฅ ์์ ๋จ์ (ํด๋์ค ๋๋ ๋ฉ์๋)๋ฅผ ๊ณ ๋ฆฝ์์ผ์ ํ
์คํธํ๋ ๋ฐฉ์
๊ด๋ จ ์ฉ์ด SUT (Sytem Under Test) ํ
์คํธํ๊ณ ์ํ๋ ์ฃผ์ ๋์์ด ๋๋ Unit
DOC (Depended On Component) SUT๊ฐ ์์กดํ๋ ๊ฐ์ฒด
Test double DOC๋ฅผ ๋์ ํด ์ค ์ ์๋ ๊ฐ์ฒด
Test double์ ์ข
๋ฅ : Mock, Stub Mock ํ์ ๊ฒ์ฆ (๊ฐ์ฒด๊ฐ ํน์ ๋์์ ์ํํ๋์ง ๊ฒ์ฆ) ์ฌ์ฉ test framework : Mockito, JMock, EasyMock Stub ์ํ ๊ฒ์ฆ (๊ฐ์ฒด์ ์ํ๋ฅผ ํ์ธํ์ฌ ๊ฒ์ ) ์ฌ์ฉ Integration Test (ํตํฉ ํ
์คํธ) ์ฌ๋ฌ ๊ฐ์ Unit์ ํตํฉํด์ ํ
์คํธํ๋ ๋ฐฉ์
JUnit ๋งค ๋จ์ ํ
์คํธ๋ง๋ค ํ
์คํธ ํด๋์ค๊ฐ ์์ฑ -> ๋
๋ฆฝ์ ์ธ ํ
์คํธ ๊ฐ๋ฅ Annotation ์ ๊ณต -> ํ
์คํธ life cycle ๊ด๋ฆฌ assert ๋ฉ์๋ ์ ๊ณต -> ํ
์คํธ ๊ฒฐ๊ณผ ํ๋ณ JUnit5 = JUnit Platform + JUnit Jupiter + JUnit Vintage
JUnit Platform : JVM ๊ธฐ๋ฐ ํ
์คํ
ํ๋ ์์ํฌ๋ฅผ ์คํ์ํค๊ธฐ ์ํ ๊ธฐ๋ฐ ๋ชจ๋ JUnit Jupiter : JUnit5๋ฅผ ์ํ Test Engine API ์ ๊ณต JUnit Vintage : JUnit3, JUnit4๋ฅผ ์ํ Test Engine API ์ ๊ณต org.junit.jupiter.api.Assertions.* assertEquals 1assertEquals(0, 1+1); assertThrows, assertAll org.hamcrest.MatcherAssert.* assertThat 1// assertEquals ๋ณด๋ค ๊ฐ๋
์ฑ์ด ์ข๋ค 2assertThat(1+1, equalTo(2)); org.hamcrest.Matchers.* equalTo, is, not anyOf, everyItem hasSize, containsInAnyOrder, hasItem (collection์ ๋ํด ๊ฐ๋ ฅํ๊ฒ ์ง์ํ๋ค) Design Techniques Contextual Inquiry ์ฌ์ฉ์์ ํ๊ฒฝ์์ ์ฌ์ฉ์์ ํ๋์ ๊ด์ฐฐ Design Funnel ์์ด๋์ด๋ฅผ ํ์ฅํจ๊ณผ ๋์์ ์ถ์ ์ํด์ผ๋ก์ ๊ฒฐ๊ณผ ๋์ถ Double Diamond Discover -> Define -> Develop -> Deliver Storyboarding ์๋๋ฆฌ์ค๋ฅผ ๊ทธ๋ฆผ์ผ๋ก ํํ Prototyping ๋์์ธ์ ํํํ๋ ์ํํธ์จ์ด๋ก ๊ตฌํ ์ข
๋ฅ: Low-fidelity(์ถฉ์ค๋๊ฐ ๋ฎ์), High-fidelity(์ถฉ์ค๋๊ฐ ๋์) User Testing In-lab vs On-site Moderated vs Unmoderated : Exploratory vs Assessment Presentation & Communication Needfinding (์๊ตฌ์ฌํญ ๋์ถ) ์ฉ์ด UI (User Interface) ์ ํ์ ์๊ฐ์ ์ธ ์์
UX (User Experience) ์ ํ์ ์ฌ์ฉํ๋ ์ฌ์ฉ์๊ฐ ๋๋ผ๋ ๊ฒฝํ
CX (Customer Experience) ๊ณ ๊ฐ์ด ์ ํ์ ์ฌ์ฉํ๋ ๊ณผ์ ์์ ๋๋ผ๋ ์ ๋ฐ์ ์ธ ๊ฒฝํ, ์ํ ๋๋ ์๋น์ค์ ๊ตฌ๋งค, ์ฌ์ฉ ์ฌ๋ถ๋ฅผ ๊ฒฐ์ ์ง๋ ์์
SD (Service Design) ์๋น์ค๋ฅผ ๋์์ธํ๋ ๊ฒ
HCI (Human-Computer Interaction) ์ฌ๋ฌ ๊ตฌ์ฑ์์๋ฅผ ์กฐํฉํ์ฌ ์ฌ์ฉ์์๊ฒ ์ต๊ณ ์ ๊ฒฝํ์ ์ ๊ณตํ๊ธฐ ์ํด ์ ํ, ์ ์, ๊ฒฐํฉํ๋ ๊ฒ
SRS (Software Requirement Specification) ์ํํธ์จ์ด ์๊ตฌ์ฌํญ ๋ช
์ธ์
User Requirements, Functional Requirements, Interface Requirements, Performance Requirements… SRS๋ฅผ ๋ฌธ์ํํ๊ธฐ์ ์ ์ฌ์ฉ์๋ฅผ ์ดํดํ๋ ๊ฒ์ด ์ค์ ์ฌ์ฉ์์ ๋ํ ์ดํด ๋ค์ํ ์ฌ์ฉ์์ ํน์ฑ์ ์ดํด : ์ญํ , ๊ฐ์ฑ ์ดํด๊ด๊ณ์(stakeholders)๋ฅผ ๊ณ ๋ ค First degree : ์ง์ ์ ์ผ๋ก ์ ํ์ ์ฌ์ฉํ๋ ์ฌ๋ Second degree : ์ ํ์ ๊ฒฐ๊ณผ์ ์ํฅ์ ๋ฐ๋ ์ฌ๋ Third degree : ์๋น์ค๋ฅผ ์ค์น, ๋ฐฐํฌํ๋ ์ฌ๋ ๋๋ ๊ธฐ๋ฐ ์์คํ
์ฌ์ฉ์ ๋ชฉ์ ํ์
Identify the goals involved in the problem Decompose them into subtasks Abstract into goals Contextual Inquiry (์ํฉ์ ์กฐ์ฌ) Context : ์ฌ์ฉ์์ ํ๊ฒฝ ๊ด์ฐฐ, ์ถ์ํ ๊ธ์ง Partnership : ์ฌ์ฉ์์๊ฒ ๊ณต๊ฐ, ์ฌ์ฉ์์๊ฒ ํ๋๊ณผ ๊ทธ ์ด์ ๋ฅผ ์ง๋ฌธ Interpretation : ์ฌ์ฉ์์ ๋ํ ํด์์ ์ฌ์ฉ์์๊ฒ ๊ณต์ , ์ฌ์ฉ์์ ํผ๋๋ฐฑ์ ๋ฐ์ Focus : ๋ชฉํ์ ์ง์ค The master-apprentice model (๋์ ์ ๋ชจ๋ธ) : ์ฌ์ฉ์(์ ์), ๊ด์ฐฐ์(ํ์)
Contextual Inquiry๊ฐ ์ ์ ํ์ง ์์ ๋
Longidual study : ์ฌ์ฉ์์ ํ๋์ ์ฅ๊ธฐ๊ฐ ๊ด์ฐฐํด์ผํ ๋ Sporadic behavior : ์ฌ์ฉ์์ ํ๋์ด ๋ถ๊ท์นํ ๋ Large target : ์ฌ์ฉ์์ ๋ฒ์๊ฐ ๊ด๋ฒ์ ํ ๋ Diary Study ์ฌ์ฉ์๊ฐ ์ผ์์ ์ผ๋ก ํ๋ ์ผ์ ๊ธฐ๋กํ๋ ๊ฒ
ESM (Experience Sampling Method) ์๊ฐ์ ์ธ ํ๋๊ณผ ๊ฒฝํ์ ์ด์ ์ ๋ง์ถฐ ๊ธฐ๋ก
EMA (Ecological Momentary Assessment) ์ฌ๋ฆฌ์ ํ์์ ๊ถค์ , ๋ถ์ฐ, ๋ณ๋, ์ญํ์ ์ด์ ์ ๋ง์ถฐ ๊ธฐ๋ก
Survey Participatory Design ์ฌ์ฉ์๊ฐ ์ง์ ๋์์ธ์ ์ฐธ์ฌํ๋ ๊ฒ Affinity Diagram (์ ์ฌ๋ ๋ค์ด์ด๊ทธ๋จ) ์์งํ ๋ฐ์ดํฐ๋ฅผ ๋ถ๋ฅํ๋ ๊ฒ
Persona ์ฌ์ฉ์๋ฅผ ๋ํํ๋ ๊ฐ์์ ์ธ๋ฌผ
Learnability ์๋ก์ด UI๋ฅผ ๋ฐฐ์ฐ๋ ๋ฐฉ๋ฒ Learning by Doing Learning by Watching Recognition vs Recall Recognition : ์๊ฐ์ ์์๋ฅผ ๋ณด๊ณ ์ธ์งํ๋ ๊ฒ Recall : ๊ธฐ์ต์ ํตํด ์ธ์งํ๋ ๊ฒ Interaction style Command Language ์ธ๊ณต ์ธ์ด์ ๋ช
๋ น์ด๋ฅผ ์
๋ ฅ
Self Disclosure (์๊ธฐ ๊ณต๊ฐ) : ์ฌ์ฉ ๊ฐ๋ฅํ ๋ช
๋ น์ด๋ฅผ ์๊ฐ์ ์ผ๋ก ํํ Menus and Forms Direct Manipulation ์ฆ๊ฐ์ ์ผ๋ก ๋ฐ์ ์๊ฐ์ ํํ์ ํตํด ์ํธ์์ฉ
Speech Dialog Mental Model ์ฌ๋๋ค์ด ์๊ธฐ ์์ , ๋ค๋ฅธ ์ฌ๋, ํ๊ฒฝ, ์์ ์ด ์ํธ์์ฉํ๋ ์ฌ๋ฌผ๋ค์ ๋ํด ๊ฐ๋ ๋ชจํ
๊ด์ฐฐ, ์ธํฐ๋ทฐ, ์์
๋ถ์์ด ํ์ํ๋ค Conceptual Model ์ ํ์ด ์ด๋ ํ ์๋ฆฌ๋ ๋ฐฉ์์ผ๋ก ์๋ํ๋์ง์ ๋ํ ์ดํด
Content strategy : ๊ฐ ํ์ด์ง์ ๋ํ๋๋ ๋ด์ฉ์ ๊ท์น์ด๋ ๊ฐ๋
์ด ์กด์ฌํ๋๊ฐ? Channel starategy : ์ผ๊ด์ ์ธ ๊ฒฝํ, ์ง์์ ์ธ ๊ฒฝํ, ์ํธ ๋ณด์์ ์ธ ๊ฒฝํ์ ๋ง๋ค์ด๋ด๋๊ฐ? Interaction models : ๋ณดํธ์ ์ธ ํจํด์ ์ฌ์ฉํ๋๊ฐ? 1from collections import defaultdict 2 3def solution(s): 4 count = defaultdict(int) 5 for i in s[1:-1].replace('},{', '} {').split(' '): 6 for j in i[1:-1].split(','): 7 count[j] += 1 8 return [int(i[0]) for i in sorted(count.items(), key=lambda x: x[1], reverse=True)] ๋ฌธ์ ํน์ ํํ์ ํฌํํ๋ ์งํฉ์ด ๋ด๊ธด ๋ฌธ์์ด s๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋ค s๊ฐ ํํํ๋ ํํ์ ๋ฐฐ์ด์ ๋ด์ ๋ฐํํ๋ผ TC input “{{2},{2,1},{2,1,3},{2,1,3,4}}”
ouput [2, 1, 3, 4]
ํด๊ฒฐ๋ฐฉ๋ฒ ๋ฌธ์ ์์ ์ํ๋ ํํ์ ์์๋ ์์์ ๊ฐ์๊ฐ ์์ฃผ ๋ฑ์ฅํ๋ ์์์ด๋ค ๊ฐ ์์์ ๊ฐ์๋ฅผ ์ธ์ด count๋ผ๋ defaultdict์ ๋ฃ๋๋ค count๋ฅผ value ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ์ฌ key๊ฐ์ list์ ํํ๋ก ๋ฐํํ๋ผ 1answer = [0, 0] 2 3def solution(arr): 4 def recursion(sx, sy, k): 5 global answer 6 origin = arr[sy][sx] 7 cnt = 0 8 for i in range(sx, sx+k): 9 for j in range(sy, sy+k): 10 if origin != arr[j][i]: 11 recursion(sx, sy, k//2) 12 recursion(sx+k//2, sy, k//2) 13 recursion(sx, sy+k//2, k//2) 14 recursion(sx+k//2, sy+k//2, k//2) 15 return 16 answer[origin] += 1 17 18 recursion(0, 0, len(arr)) 19 return answer ๋ฌธ์ 0๊ณผ 1๋ก ์ด๋ฃจ์ด์ง 2^n x 2^n ํฌ๊ธฐ์ 2์ฐจ์ ์ ์ ๋ฐฐ์ด arr์ ์์ถํ๋ ค ํ๋ค ์์ถํ๋ ๋ฐฉ๋ฒ์ ๋น์ ์ด ์์ถํ๊ณ ์ ํ๋ ํน์ ์์ญ์ S๋ผ๊ณ ์ ์ํ๋ค ๋ง์ฝ S ๋ด๋ถ์ ์๋ ๋ชจ๋ ์๊ฐ ๊ฐ์ ๊ฐ์ด๋ผ๋ฉด, S๋ฅผ ํด๋น ์ ํ๋๋ก ์์ถ์ํจ๋ค ๊ทธ๋ ์ง ์๋ค๋ฉด, S๋ฅผ ์ ํํ 4๊ฐ์ ๊ท ์ผํ ์ ์ฌ๊ฐํ ์์ญ์ผ๋ก ์ชผ๊ฐ ๋ค, ๊ฐ ์ ์ฌ๊ฐํ ์์ญ์ ๋ํด ๊ฐ์ ๋ฐฉ์์ ์์ถ์ ์๋ํ๋ค TC input [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]
ouput [4,9]
ํด๊ฒฐ๋ฐฉ๋ฒ recursionํจ์๋ฅผ ๋ง๋ค์ด์ ์ฌ๊ท์ ์ผ๋ก ํ์๋ค recursionํจ์ ์ธ์์ k๋ ํ์ฌ ์์ญ์ ๊ธธ์ด๋ฅผ ์๋ฏธํ๋ค 1from itertools import combinations 2from collections import defaultdict 3 4def solution(orders, course): 5 answer = [] 6 7 for i in course: 8 dataset = defaultdict(int) 9 10 for j in orders: 11 for k in combinations(j, i): 12 # ABC, ACB๋ฅผ ๊ฐ์ ๊ฒ์ผ๋ก ์ทจ๊ธํ๊ธฐ ์ํด ์ ๋ ฌ 13 dataset[''.join(sorted(k))] += 1 14 15 if len(dataset) == 0: 16 continue 17 18 max_value = max(dataset.values()) 19 20 # 2๋ฒ ์ด์ ์ฃผ๋ฌธ๋ ๋ฉ๋ด๋ง ์ถ๊ฐ 21 if max_value == 1: 22 continue 23 24 for k, _ in filter(lambda x:x[1] == max_value, dataset.items()): 25 answer.append(''.join(k)) 26 27 return sorted(answer) ๋ฌธ์ ์๋๋ค์ด ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด๋ค์ด ๋ฌธ์์ด ํ์์ผ๋ก ๋ด๊ธด ๋ฐฐ์ด orders, ์ฝ์ค ์๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ๋จํ๋ฉ๋ด๋ค์ ๊ฐฏ์๊ฐ ๋ด๊ธด ๋ฐฐ์ด course๊ฐ ์ฃผ์ด์ง๋ค ์๋๋ค์ด ํจ๊ป ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด๋ค ์ค, ๊ฐ์ฅ ๋ง์ด ํจ๊ป ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด ์กฐํฉ์ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ก ๊ตฌ์ฑํ๋ ค๊ณ ํ๋ค ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ ์ต์ 2๊ฐ์ง ์ด์์ ๋จํ๋ฉ๋ด๋ก ๊ตฌ์ฑ๋์ด์ผํ๋ฉฐ, ์ต์ 2๋ช
์ด์์ ์๋์ผ๋ก๋ถํฐ ์ฃผ๋ฌธ๋ ๋จํ๋ฉ๋ด ์กฐํฉ๋ง์ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด ํ๋ณด์ ํฌํจํ๋ค ์ฝ์ค์๋ฆฌ ๋ฉ๋ด์ ๊ตฌ์ฑ์ ๋ฌธ์์ด ํ์์ผ๋ก ๋ฐฐ์ด์ ๋ด์ ์ฌ์ ์์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ์ฌ returnํ๋ผ TC input orders: [“ABCFG”, “AC”, “CDE”, “ACDE”, “BCFG”, “ACDEH”]
course: [2,3,4]
ouput [“AC”, “ACDE”, “BCFG”, “CDE”]
ํด๊ฒฐ๋ฐฉ๋ฒ combinations๋ฅผ ์ฌ์ฉํ์ฌ ๋ชจ๋ ์กฐํฉ์ ๊ตฌํด์ defaultdict๋ก ๊ฐ์๋ฅผ ์ผ๋ค defaultdict์ value ์ค ์ต๋๊ฐ์ ๊ตฌํ๊ณ , ์ต๋๊ฐ๊ณผ ๊ฐ์ value๋ฅผ ๊ฐ์ง key๋ฅผ answer์ ์ถ๊ฐํ๋ค 1from itertools import combinations 2from collections import defaultdict 3from bisect import bisect_left 4 5def solution(infos, queries): 6 answer = [] 7 dataset = defaultdict(list) 8 9 for info in infos: 10 token = info.split(' ') 11 12 for j in range(5): 13 for case in list(combinations([0,1,2,3], j)): 14 temp = token[:-1] 15 for c in case: 16 temp[c] = '-' 17 dataset[''.join(temp)].append(int(token[-1])) 18 for value in dataset.values(): 19 value.sort() 20 21 for query in queries: 22 query = query.replace(" and", "").split() 23 target_key = ''.join(query[:-1]) 24 target_value = int(query[-1]) 25 count = 0 26 27 if target_key in dataset: 28 target_list = dataset[target_key] 29 idx = bisect_left(target_list, target_value) 30 count = len(target_list)-idx 31 32 answer.append(count) 33 return answer ๋ฌธ์ ์ง์์๊ฐ ์ง์์์ ์์ฑํ 4๊ฐ์ง ์ ๋ณด์, ํน์ ์ง์์์ ์ง์์ ์ ์๊ฐ ๋ฌธ์์ด ๋ฐฐ์ด๋ก ์ฃผ์ด์ง๋ค
๊ฐ๋ฐ์ธ์ด๋ cpp, java, python ์ค ํ๋, ์ง์ ์ง๊ตฐ์๋ backend, frontend ์ค ํ๋,
์ง์ ๊ฒฝ๋ ฅ์๋ junior, senior ์ค ํ๋, ์์ธํธ๋์๋ chicken, pizza ์ค ํ๋๊ฐ ์ฃผ์ด์ง๋ค
๊ฐ๋ฐํ์ด ๊ถ๊ธํดํ๋ ๋ฌธ์ ์กฐ๊ฑด๋ ๋ฌธ์์ด ๋ฐฐ์ด๋ก ์ฃผ์ด์ง๋ค
๊ฐ๋ฐ์ธ์ด์ ์ง๊ตฐ, ๊ฒฝ๋ ฅ, ์์ธํธ๋ ์กฐ๊ฑด์ “and"๋ก ๊ตฌ๋ถ๋์ด ์๋ค
‘-‘ํ์๋ ํด๋น ์กฐ๊ฑด์ ๊ณ ๋ คํ์ง ์๋๋ค๋ ๋ป์ธ๋ฐ, ์ ์๋ฅผ ์ ์ธํ ํญ๋ชฉ์ ์ฃผ์ด์ง ์ ์๋ค
๋ฌธ์์กฐ๊ฑด์ ํด๋นํ๋ ์ฌ๋ ์ค ์ฝ๋ฉํ
์คํธ ์ ์๋ฅผ ๋ง์กฑํ๋ ์ฌ๋์ ์๋ฅผ ๊ตฌํ๋ผ
TC
input info:[“java backend junior pizza 150”,“python frontend senior chicken 210”,“python frontend senior chicken 150”,“cpp backend senior pizza 260”,“java backend junior chicken 80”,“python backend senior chicken 50”]
query:[“java and backend and junior and pizza 100”,“python and frontend and senior and chicken 200”,“cpp and - and senior and pizza 250”,”- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]
ouput [1,1,1,1,2,4]
ํด๊ฒฐ๋ฐฉ๋ฒ ์ธ์ด, ์ง๊ตฐ, ๊ฒฝ๋ ฅ, ์์ธํธ๋๋ฅผ ํ๋ฒ์ ๊ฑฐ๋ฅด๊ธฐ ์ํด dictionary์ key๋ฅผ ๋ง๋ค์ด์ฃผ์ด์ผํ๋ค ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํด์ฃผ๊ธฐ ์ํด ‘-‘๋ ์์ด๊ฐ๋ฉด์ ํด๋น ์ง์์๋ฅผ ์ฐพ์ ์ ์๋ ๋ชจ๋ ์ฟผ๋ฆฌ๋ฅผ ๊ตฌํด์ key๋ก ๋ฑ๋กํ๋ค value์๋ ์ ์๊ฐ ๋ค์ด๊ฐ๋๋ฐ ์ดํ์ ์ด๋ถํ์์ ํ๊ธฐ์ํด ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ค๋ค bisect_left ํจ์๋ฅผ ํตํด ํด๋น ์ ์ ์ด์์ธ ์ฌ๋์ ์๋ฅผ ๊ตฌํ๋ค 1dx = [1, 0, -1, 0] 2dy = [0, 1, 0, -1] 3 4def solution(rows, columns, queries): 5 table = [[(j*columns)+i+1 for i in range(columns)] for j in range(rows)] 6 answer = [] 7 8 for y1, x1, y2, x2 in queries: 9 min_num = 10000 10 x1 -= 1 11 y1 -= 1 12 x2 -= 1 13 y2 -= 1 14 direction = 0 15 curX, curY = x1, y1 16 postNum = table[y1][x1] 17 while True: 18 curX = curX+dx[direction] 19 curY = curY+dy[direction] 20 21 temp = table[curY][curX] 22 table[curY][curX] = postNum 23 postNum = temp 24 25 min_num = min(min_num ,postNum) 26 27 if ((curX == x2 and curY == y1) or 28 (curX == x2 and curY == y2) or 29 (curX == x1 and curY == y2)): 30 direction += 1 31 32 if curX == x1 and curY == y1: 33 break 34 35 answer.append(min_num) 36 37 return answer ๋ฌธ์ rows X columns ํฌ๊ธฐ์ ํ๋ ฌ์ด ์๋ค ํ๋ ฌ์๋ 1๋ถํฐ rows x columns ๊น์ง์ ์๊ฐ ์์๋๋ก ์ ํ์๋ค (x1, y1, x2, y2)์ธ ์ ์ 4๊ฐ๋ก ํํ๋ ํ์ ์ด ์ฃผ์ด์ง๋ค ๊ฐ ํ์ ๋ง๋ค x1 ํ y1 ์ด๋ถํฐ x2 ํ y2 ์ด๊น์ง์ ์์ญ์ ํด๋นํ๋ ์ง์ฌ๊ฐํ์์ ํ
๋๋ฆฌ์ ์๋ ์ซ์๋ค์ ํ ์นธ์ฉ ์๊ณ๋ฐฉํฅ์ผ๋ก ํ์ ์ํจ๋ค ํ์ ์ ์ํด ์์น๊ฐ ๋ฐ๋ ์ซ์๋ค ์ค ๊ฐ์ฅ ์์ ์ซ์๋ค์ ์์๋๋ก ๋ฐฐ์ด์ ๋ด์ return ํ๋ผ TC input rows: 6 columns: 6
queries: [[2,2,5,4],[3,3,6,6],[5,1,6,3]]
ouput [8, 10, 25]
ํด๊ฒฐ๋ฐฉ๋ฒ ๊ผญ์ง์ ์ ๋๋ฌํ ๋๋ง๋ค direction ๋ณ์๋ฅผ 1 ์ฆ๊ฐ์์ผ์ ๋ฐฉํฅ์ ๋ฐ๊ฟ์ฃผ์๋ค 1def solution(numbers): 2 answer = [] 3 for number in numbers: 4 num = list(str(bin(number)).split('b')[1]) 5 6 # ์ฒซ๋ฒ์งธ ์๋ฆฟ์๊ฐ 0์ธ ๊ฒฝ์ฐ 7 if num[-1] == '0': 8 num[-1] = '1' 9 answer.append(int('0b'+''.join(num), 2)) 10 continue 11 12 # ์ฒซ๋ฒ์งธ ์๋ฆฟ์๊ฐ 1์ธ ๊ฒฝ์ฐ 13 num = ['0']+num 14 # ๋๋ฒ์งธ ์๋ฆฌ๋ถํฐ ์ํ 15 for i in range(len(num)-2, -1, -1): 16 # ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ 0์ ์ฐพ์์ ๋ 17 if num[i] == '0': 18 # 0์ ์ค๋ฅธ์ชฝ์ผ๋ก, 1์ ์ผ์ชฝ์ผ๋ก ์ฎ๊ธด๋ค 19 num[i], num[i+1] = num[i+1], num[i] 20 answer.append(int('0b'+''.join(num), 2)) 21 break 22 23 return answer ๋ฌธ์ ์์ ์ ์ x์ ๋ํด์ “x๋ณด๋ค ํฌ๊ณ x์ ๋นํธ๊ฐ 1~2๊ฐ ๋ค๋ฅธ ์๋ค ์ค์์ ์ ์ผ ์์ ์"๋ฅผ ๊ตฌํ๋ผ TC input [2, 7]
ouput [3, 11]
ํด๊ฒฐ๋ฐฉ๋ฒ 2๊ฐ์ง ๊ฒฝ์ฐ๋ก ํ์๋ค, ์ฒซ๋ฒ์งธ ์๋ฆฟ์๊ฐ 0์ธ ๊ฒฝ์ฐ -> ์ฒซ๋ฒ์งธ ์๋ฆฟ์ 1๋ก ๋ฐ๊พผ๋ค ์ฒซ๋ฒ์งธ ์๋ฆฟ์๊ฐ 1์ธ ๊ฒฝ์ฐ -> ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ 0์ ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ฎ๊ธด๋ค 1dx = [-1, 1, 0, 0] 2dy = [0, 0, -1, 1] 3def quest(table): 4 table = [list(line) for line in table] 5 for j in range(5): 6 for i in range(5): 7 if table[i][j] == 'P': 8 flag = [False]*4 9 target = [] 10 for k in range(4): 11 nx = i+dx[k] 12 ny = j+dy[k] 13 if 0 <= nx < 5 and 0 <= ny < 5: 14 target.append((nx, ny)) 15 flag[k] = True 16 17 for x, y in target: 18 if table[x][y] == 'C' or table[x][y] == 'P': 19 return 0 20 if table[x][y] == 'O': 21 table[x][y] = 'C' 22 23 target = [] 24 if flag[0] and flag[2] and table[i-1][j] == 'O' and table[i][j-1] == 'O': 25 target.append((i-1, j-1)) 26 if flag[0] and flag[3] and table[i-1][j] == 'O' and table[i][j+1] == 'O': 27 target.append((i-1, j+1)) 28 if flag[1] and flag[2] and table[i+1][j] == 'O' and table[i][j-1] == 'O': 29 target.append((i+1, j-1)) 30 if flag[1] and flag[3] and table[i+1][j] == 'O' and table[i][j+1] == 'O': 31 target.append((i+1, j+1)) 32 33 for x, y in target: 34 if table[x][y] == 'P': 35 return 0 36 return 1 37 38def solution(places): 39 answer = [] 40 for table in places: 41 answer.append(quest(table)) 42 return answer ๋ฌธ์ ๋๊ธฐ์ค ๊ตฌ์กฐ๋ฅผ ๋๊ธฐ์ค๋ณ๋ก ๋ด์ 2์ฐจ์ ๋ฌธ์์ด ๋ฐฐ์ด places๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋ค ๋๊ธฐ์ค์ 5๊ฐ์ด๋ฉฐ, ๊ฐ ๋๊ธฐ์ค์ 5X5 ํฌ๊ธฐ์ด๋ค ๊ฑฐ๋ฆฌ๋๊ธฐ๋ฅผ ์ํ์ฌ ์์์๋ค ๋ผ๋ฆฌ๋ ๋งจํดํผ ๊ฑฐ๋ฆฌ๊ฐ 2์ดํ๋ก ์์ง ๋ง์์ผ ํ๋ค ๋จ, ์์์๊ฐ ์์์๋ ์๋ฆฌ ์ฌ์ด๊ฐ ํํฐ์
์ผ๋ก ๋งํ ์์ ๊ฒฝ์ฐ์๋ ํ์ฉํ๋ค ‘P’๋ ์์์๊ฐ ์์์๋ ์๋ฆฌ, ‘O’๋ ๋นํ
์ด๋ธ, ‘X’๋ ํํฐ์
์ ์๋ฏธํ๋ค ๊ฐ ๋๊ธฐ์ค๋ณ๋ก ๊ฑฐ๋ฆฌ๋๊ธฐ๋ฅผ ์ ์ง์ผฐ๋์ง ์ฌ๋ถ๋ฅผ 1์ฐจ์ ๋ฐฐ์ด์ ๋ด์ ๋ฐํํ๋ผ TC input [[“POOOP”, “OXXOX”, “OPXPX”, “OOXOX”, “POXXP”], [“POOPX”, “OXPXP”, “PXXXO”, “OXXXO”, “OOOPP”], [“PXOPX”, “OXOXP”, “OXPOX”, “OXXOP”, “PXPOX”], [“OOOXX”, “XOOOX”, “OOOXX”, “OXOOX”, “OOOOO”], [“PXPXP”, “XPXPX”, “PXPXP”, “XPXPX”, “PXPXP”]]
ouput [1, 0, 1, 1, 1]
ํด๊ฒฐ๋ฐฉ๋ฒ ๋จผ์ , ์์์์ ์ํ์ข์ฐ๋ก ‘C’๋ฅผ ํ์ํ๊ณ , ๋ค๋ฅธ ์์์๊ฐ ‘C’๊ณต๊ฐ์ ์นจ๋ฒํ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋๊ธฐ๋ฅผ ์งํค์ง ์์ ๊ฒ์ผ๋ก ํ๋จํ๋ค ๊ทธ ๋ค์, ํํฐ์
์ผ๋ก ๋งํ์์ง ์์ ๋๊ฐ์ ์์น์ ๋ค๋ฅธ ์์์๊ฐ ์๋ค๋ฉด ๊ฑฐ๋ฆฌ๋๊ธฐ๋ฅผ ์งํค์ง ์์ ๊ฒ์ผ๋ก ํ๋จํ๋ค ๊ฑฐ๋ฆฌ๋๊ธฐ ์ฌ๋ถ์ ๋ฐ๋ผ questํจ์๊ฐ 0 ๋๋ 1์ ๋ฐํํ๊ณ , ์ด๋ฅผ answer์ ๋ด์ ๋ฐํํ๋ค 1def solution(word): 2 answer = 0 3 char = ['A', 'E', 'I', 'O', 'U'] 4 cnt = 0 5 6 def traverse(cur): 7 nonlocal char, cnt, word 8 if cur == word: 9 return cnt 10 11 if len(cur) < 5: 12 for ch in char: 13 cnt += 1 14 if traverse(cur+ch) != None: 15 return cnt 16 return traverse('') ๋ฌธ์ ์ฌ์ ์ A,E,I,O,U๋ง ์ฌ์ฉํ์ฌ ๋ง๋ค ์ ์๋ ๊ธธ์ด 5์ดํ์ ๋ชจ๋ ๋จ์ด๊ฐ ์๋ก๋์ด์๋ค ๋จ์ด ํ๋ word๊ฐ ์ฃผ์ด์ง๋ ์ฌ์ ์์ ๋ช๋ฒ์งธ ๋จ์ด์ธ์ง ๊ตฌํ๋ผ TC input ‘I’
ouput 1563
ํด๊ฒฐ๋ฐฉ๋ฒ DFS๋ก ํ์๋ค ๊ทธ๋ฅ ๋ฐ๋ณต๋ฌธ์ผ๋ก ํ๊ฑธ ๊ทธ๋ฌ๋ค๋ ์๊ฐ์ด ๋ ๋ค 1dx = [1, 0, -1, 0] 2dy = [0, 1, 0, -1] 3def solution(grid): 4 N = len(grid) 5 M = len(grid[0]) 6 grid = [list(line) for line in grid] 7 route = [[[False]*4 for _ in range(M)] for _ in range(N)] 8 answer = [] 9 10 for i in range(M): 11 for j in range(N): 12 for k in range(4): 13 cur = [i, j] 14 dir = k 15 cnt = 0 16 while not route[cur[1]][cur[0]][dir]: 17 cnt += 1 18 route[cur[1]][cur[0]][dir] = True 19 cur[0] = (cur[0]+dx[dir]) % M 20 cur[1] = (cur[1]+dy[dir]) % N 21 22 if grid[cur[1]][cur[0]] == 'L': 23 dir = (dir-1) % 4 24 elif grid[cur[1]][cur[0]] == 'R': 25 dir = (dir+1) % 4 26 if cnt != 0: 27 answer.append(cnt) 28 29 return sorted(answer) ๋ฌธ์ ๊ฐ ์นธ๋ง๋ค S, L, ๋๋ R๊ฐ ์จ์ ธ ์๋ ๊ฒฉ์๊ฐ ์๋ค ๊ฒฉ์์ ๋น์ ์๊ณ ์ ํ๋ค ๋น์ด ๋๋ฌํ ์นธ์ด S์นธ์ด๋ฉด ์ง์ง, L์ด๋ฉด ์ผ์ชฝ์ผ๋ก, R์ด๋ฉด ์ค๋ฅธ์ชฝ์ผ๋ก ๊บพ๋๋ค ๋น์ด ๊ฒฉ์๋ฅผ ๋์ด๊ฐ ๊ฒฝ์ฐ, ๋ฐ๋์ชฝ ๋์ผ๋ก ๋ค์ ๋์์จ๋ค ๋น์ด ์ด๋ํ ์ ์๋ ๊ฒฝ๋ก ์ฌ์ดํด์ ๊ธธ์ด๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ๋ฐํํ๋ผ TC input [“SL”,“LR”]
ouput [16]
ํด๊ฒฐ๋ฐฉ๋ฒ route๋ผ๋ ๋ฐฐ์ด์ ๊ฐ ์นธ๋ง๋ค ๋น์ด ์ด๋ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ๋์ง ๊ธฐ๋กํ๋ค ๋๊ฐ์ ๊ฒฝ๋ก๋ก ๋น์ด ์ด๋ํ ๋๊น์ง cnt๋ฅผ ์ฆ๊ฐ์์ผ์ answer์ ๋ฃ๋๋ค ์ ๊ณผ์ ์ ๋น์ ์ ์ ์๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ๋ํด ๋ฐ๋ณตํ๋ค ๋ฐฐ์ด ์ ๋๋จธ์ง ์ฐ์ฐ์ ์ด์ฉํด์ ์์๋ฅผ ์ฒ๋ฆฌํ ์ ์๋ค๋ ๊ฒ์ ์๊ฒ๋์๋ค ex) -1 % 4 = 3 1def solution(n, wires): 2 tower = [[] for _ in range(n)] 3 answer = 100 4 for wire in wires: 5 wire[0] -= 1 6 wire[1] -= 1 7 tower[wire[0]].append(wire[1]) 8 tower[wire[1]].append(wire[0]) 9 10 def traverse(visited, start): 11 visited[start] = True 12 for i in tower[start]: 13 if not visited[i]: 14 traverse(visited, i) 15 for wire in wires: 16 tower[wire[0]].remove(wire[1]) 17 tower[wire[1]].remove(wire[0]) 18 19 visited = [False]*n 20 a = 0 21 traverse(visited, wire[0]) 22 for i in range(n): 23 if visited[i]: 24 a += 1 25 26 visited = [False]*n 27 b = 0 28 traverse(visited, wire[1]) 29 for i in range(n): 30 if visited[i]: 31 b += 1 32 answer = min(answer, abs(a-b)) 33 tower[wire[0]].append(wire[1]) 34 tower[wire[1]].append(wire[0]) 35 return answer ๋ฌธ์ n๊ฐ์ ์ก์ ํ์ด ์ ์ ์ ํตํด ํธ๋ฆฌ ํํ๋ก ์ฐ๊ฒฐ๋์ด ์๋ค ์ ์ ์ค ํ๋๋ฅผ ๋์ด์ ์ ๋ ฅ๋ง ๋คํธ์ํฌ๋ฅผ 2๊ฐ๋ก ๋ถํ ํ์ฌ ๋ ์ ๋ ฅ๋ง์ด ๊ฐ๊ฒ๋๋ ์ก์ ํ์ ๊ฐ์๋ฅผ ์ต๋ํ ๋น์ทํ๊ฒ ๋ง์ถ๊ณ ์ ํ๋ค ์ก์ ํ์ ๊ฐ์ n, ์ ์ ์ ๋ณด๋ฅผ ๋ด์ 2์ฐจ์ ๋ฐฐ์ด wires๊ฐ ์ฃผ์ด์ง๋ค ๋ ์ ๋ ฅ๋ง์ด ๊ฐ์ง๋ ์ก์ ํ์ ๊ฐ์ ์ฐจ์ด์ ์ต์๊ฐ์ ๊ตฌํ๋ผ TC input n:9, wires:[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
ouput 3
ํด๊ฒฐ๋ฐฉ๋ฒ ์ ์ ์ ํ๊ฐ์ฉ ๋์ด๋ณด๋ฉด์ ๋์ด์ง ๋ ์์น๋ฅผ ์์์ผ๋ก dfsํ์์ ํ์ฌ visited ๋ฐฐ์ด์ ๋ง๋ค์๋ค visited ๋ฐฐ์ด์ ์ด์ฉํ์ฌ ๋ ์ ๋ ฅ๋ง์ด ๊ฐ์ง๋ ์ก์ ํ์ ๊ฐ์ ์ฐจ์ด๋ฅผ ๊ตฌํ์๋ค 1def calc(a1, b1, c1, a2, b2, c2): 2 if a1*b2-a2*b1 == 0: 3 return (0.1, 0.1) 4 return ((b1*c2-b2*c1)/(a1*b2-a2*b1), (c1*a2-a1*c2)/(a1*b2-a2*b1)) 5 6def solution(line): 7 answer = [] 8 length = len(line) 9 points = [] 10 size = [1e15, -1e15, 1e15,- 1e15] 11 12 for i in range(length): 13 for j in range(i): 14 point = calc(line[i][0],line[i][1], line[i][2], line[j][0], line[j][1], line[j][2]) 15 if point[0]%1 != 0 or point[1]%1 != 0: 16 continue 17 x = int(point[0]) 18 y = int(point[1]) 19 points.append((x, y)) 20 size[0] = min(size[0], x) 21 size[1] = max(size[1], x) 22 size[2] = min(size[2], y) 23 size[3] = max(size[3], y) 24 25 answer = [['.'] * (size[1]-size[0]+1) for _ in range(size[3]-size[2]+1)] 26 for x, y in points: 27 answer[size[3]-y][x-size[0]] = '*' 28 29 return [''.join(i) for i in answer] ๋ฌธ์ Ax + By + C = 0์ผ๋ก ํํํ ์ ์๋ n๊ฐ์ ์ง์ ์ด ์ฃผ์ด์ง๋ค ์ด ์ง์ ๋ค์ด ๋ง๋๋ ๊ต์ ์ ๋ฌธ์์ด ๋ฐฐ์ด๋ก ํํํ๋ผ ๋น๊ณต๊ฐ์ ‘.’, ์ ์ ‘*‘๋ก ํํํ๋ค TC input [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]
ouput ["….….", “………”, “………”, “…….”, “………”, “………”, “………”, “………”, “…….*”]
ํด๊ฒฐ๋ฐฉ๋ฒ ๊ต์ ์ ๊ตฌํ๋ ๊ณต์์ ๋ฌธ์ ์์ ์ฃผ์ด์ง๋ค Ax + By + E = 0, Cx + Dy + F = 0 ์ผ ๋ $$ x = {BF-ED \over AD-BC}, y = {AF-EC \over AD-BC} $$ ์ด๋ $(AD-BC)$๊ฐ 0์ด๋ฉด ๋ ์ง์ ์ ํํํ๋ฏ๋ก ๊ณ์ฐ์ ํ์ง ๋ง์์ผํ๋ค (๊ทธ๋ฌ์ง ์์ผ๋ฉด DivideByZero ์์ธ๊ฐ ๋ฐ์ํ๋ค) ์ขํํ๋ฉด์ ํฌ๊ธฐ๋ฅผ size๋ผ๋ ๋ฆฌ์คํธ์ ์ ์ฅํ๋๋ฐ, int๊ฐ์ ์ด๊ณผํ ์ ์์ผ๋ฏ๋ก ์ถฉ๋ถํ ํฌ๊ณ ์์ ์๋ก ์ด๊ธฐํํด์ผํ๋ค ์ขํํ๋ฉด์ ์ขํ๋ฅผ 2์ฐจ์ ๋ฐฐ์ด์ธ๋ฑ์ค๋ก ๋ณํํ ๋, ๋ค์๊ณผ ๊ฐ์ด ๊ณ์ฐํ์๋ค 1array[์ต๋๋์ด-y][x-์ต์๋์ด] = '*'